prog_0003 のバックアップ(No.3) - kiwi-log

[ トップ ] [ 新規 | 一覧 | 単語検索 | 最終更新 | ヘルプ ]

バックアップ一覧
差分を表示
現在との差分を表示
ソースを表示
prog_0003 へ行く。
- 1 (2014-10-14 (火) 12:35:31)
- 2 (2014-10-14 (火) 18:43:02)
- 3 (2014-10-14 (火) 18:43:02)
- 4 (2014-10-26 (日) 02:22:23)
- 5 (2014-10-26 (日) 02:22:23)

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行くらいだったので、結構小さくなっている。

こめんと欄

コメント	お名前	NameLink