crit-bit tree
(0)
(1)
- crit-bit tree は、スキップリスト（参考：prog_0002）と同様に、基本操作(a)～(g)をO(logN)程度で実行できて、(h)もO(MlogN)くらいで実行できて、でも乱数は使わないし、アルゴリズムはより簡単。ただし代償として消費メモリはスキップリストよりも多い。
- crit-bit tree では、2つの要素を比較する際に、大小関係ではなく、どのビットで不一致になったのかを返す必要がある。また、キーのiビット目を取り出す関数も必要となる。
- 実装したら速度重視でも280行くらいになった。スキップリストが350行くらいだったので、結構小さくなっている。
こめんと欄
- p=1/4のスキップリストと crit-bit tree をベンチマークで比較してみたところ、 crit-bit tree のほうがメモリはたくさん使ってしまうけれど、速度は速かった。ただし、スキップリストのほうで「ずる」をして、乱数を使わずに理想的なlevelが設定できるようにしてやると（つまり正確に4個おきに上のレベルでつながっているようにすると）、スキップリストのほうが性能もよくなった。 -- K 2014-10-26 (日) 02:20:03
- ということで運がよければスキップリストのほうが高性能なんだけど、実用上は crit-bit tree のほうがいいのではないかと思う、メモリが余裕があるのなら。乱数を使わないアルゴリズムは、結果が安定するというメリットもある。 -- K 2014-10-26 (日) 02:22:23
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
