Essenの開発メモ#0004
スキップリスト
- いろいろ考えて、Essenの内部ではスキップリストを使いまくることにした。
- つまりcrit-bit-treeはいったん使わない方向で。
- ちなみにこれは内部構造的な話でしかないので、言語仕様には全く影響ないです（笑）。
- 基本構造としてはWikipediaの「Indexable skiplist」を使う。
- それで、ノードの高さは乱数では決め「ない」。リンクの幅が簡単に得られるのを利用して、不自然な長さになったら近くのノードのレベルを上げ下げして調節する。つまりリバランスする。
- もともとのスキップリストでは、リバランスがいらないことがアルゴリズムのシンプルさにつながっていて長所の一つだったが、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がいいかなと思った。
こめんと欄
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
