EssenMemo0004 のバックアップ(No.5)

バックアップ一覧
差分を表示
現在との差分を表示
ソースを表示
EssenMemo0004 へ行く。
- 1 (2017-05-08 (月) 17:52:27)
- 2 (2017-05-08 (月) 18:23:47)
- 3 (2017-05-09 (火) 13:54:03)
- 4 (2017-05-09 (火) 13:54:03)
- 5 (2017-05-12 (金) 14:23:04)
- 6 (2017-05-13 (土) 23:31:13)
- 7 (2017-05-15 (月) 16:06:04)
- 8 (2017-05-18 (木) 21:46:32)
- 9 (2017-05-18 (木) 21:46:32)

Essenの開発メモ#0004

(by K, 2017.05.08)

スキップリスト

いろいろ考えて、Essenの内部ではスキップリストを使いまくることにした。
- つまりcrit-bit-treeはいったん使わない方向で。
- ちなみにこれは内部構造的な話でしかないので、言語仕様には全く影響ないです（笑）。
基本構造としてはWikipediaの「Indexable skiplist」を使う。
- https://ja.wikipedia.org/wiki/%E3%82%B9%E3%82%AD%E3%83%83%E3%83%97%E3%83%AA%E3%82%B9%E3%83%88
それで、ノードの高さは乱数では決め「ない」。リンクの幅が簡単に得られるのを利用して、不自然な長さになったら近くのノードのレベルを上げ下げして調節する。つまりリバランスする。
- もともとのスキップリストでは、リバランスがいらないことがアルゴリズムのシンプルさにつながっていて長所の一つだったが、Essen内のスキップリストではその長所は捨てて安定動作を目指したことになる。
pをいくつにするか。1/2か1/4か1/8か1/16か。
- 仮にN=65536のスキップリストがあったとする。リバランスによって、幅は理想値の1/2～2倍に調整されているとする。ポインタの幅はひとまず4バイトを仮定する。
  p 検索時に幅をたどる回数(平均) 1ノードあたりの追加容量(平均)
  1/2 1x16=16 14バイト
  1/4 3x8=24 7.7バイト
  1/8 1+7x5=36 5.7バイト
  1/16 15x4=60 4.8バイト
- こうしてみると、1/4がいいかなと思う。・・・1/16だとさすがに性能が落ちすぎな気がするし、その割に容量がものすごく節約されるというわけではない。かといって1/2はやはり容量を食いすぎる。1/4か1/8かで迷って、7.7バイトと5.7バイトの差をどう思うか。実際には最低でも4バイトのデータがあるだろうから、容量比としては最大でも20%くらい。2割小さくなることと引き換えに、1.5倍の遅さになるのはどうなのか。・・・ということで1/4がいいかなと思った。

比較

	1要素あたりの追加容量	挿入	削除	検索	i番目の要素を得る	この要素は何番目か	キーなしでも並べられるか
川合版 Indexable skiplist (KISL)	7.7バイト	O(logN)	O(logN)	O(logN)	O(logN)	O(logN)	yes
平衡木	8.0バイト以上	O(logN)	O(logN)	O(logN)	O(logN)	O(logN)	no
双方向リスト	8.0バイト	O(1)	O(1)	O(N)	O(N)	O(N)	yes

KISLでは、双方向リストを自由につなぎかえるように要素を並べ替えることができる。この使い方をする場合はデータの中にkeyがなくてもよく、先頭から100番目の位置にこの要素を挿入したい、とか、これこれの要素の隣に入れてほしいとか、そういう希望もすべてO(logN)で実現できる。またいろいろと要素を並べ替えた後で、この要素は現在何番目にいるのか？みたいな問い合わせにもO(logN)で答えられる。
またKISLは乱数を使わないアルゴリズムなので、運が悪いと遅くなるとかそういうこともなく、ワーストケースでO(N)になるとかそういうこともない。

↑

こめんと欄

コメント	お名前	NameLink

p	検索時に幅をたどる回数(平均)	1ノードあたりの追加容量(平均)
1/2	1x16=16	14バイト
1/4	3x8=24	7.7バイト
1/8	1+7x5=36	5.7バイト
1/16	15x4=60	4.8バイト