prog_0003

crit-bit tree

• (by K, 2014.10.14)

(0)

• 今回は crit-bit tree の話。

(1)

• crit-bit tree は、スキップリスト（参考：prog_0002）と同様に、基本操作(a)～(g)をO(logN)程度で実行できて、(h)もO(MlogN)くらいで実行できて、でも乱数は使わないし、アルゴリズムはより簡単。ただし代償として消費メモリはスキップリストよりも多い。
  • 省メモリ志向でも実装できそうだけど、それをやると少し速度が落ちそうな気がする。
  • http://cr.yp.to/critbit.html
  • 厳密にいうと演算量はlogNに比例するのではなく、演算量の上限がキーのビット長に比例する。
• 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