なにこれ
前回の続き。
今回はスキップリストを用いて、SSetインターフェースとListインターフェースを実装します。
SSetインターフェース
Setインターフェースとは、重複がない要素の集まりを指します。 ここで要素に順序付けない場合をUSet、順序付ける場合をSSetとします。
スキップリスト
2・3章で扱った配列や連結リストは、いずれも各ノードを順に辿るという処理が必要でした。
そこで、①1つ1つ辿らずにスキップできるようにする②スキップ具合はランダムに任せるとしたのがスキップリストです。
底辺はSLListのように単方向にポインタを持った構造ですが、ポインタに高さという概念が入ります。
そして同じ高さ同士は単方向に繋がります。
最初にある番兵(sentinel)は最大の高さを持っており、各ノードは追加される際に高さをランダムに選びます。
高さを決めるランダム性
裏が出るまでコインを投げ続けた回数を高さにします。
1/2で0, 1/4で1...となり、高さの期待値は1になります。
実装上はどうするかというと、2進数で32桁の値をランダムに取得し、先頭から1が連続する回数を数えています。
(自分で実装したらrandom.random() <= 0.5を32回繰り返すと書いちゃいそう。学び。)
z = random.getrandbits(32) k = 0 while z & 1: k += 1 z = z // 2 return k
通常1つ1つ辿ればO(n)かかっていたところが、O(logn)で済むようになります。
SkiplistSSet
探索では、「sentinelの一番高いところから辿り、同じ高さのnextの値を見て、行き過ぎた!となったら1段低く下がり、そうでないならそのノードに進む」ことを繰り返します。
(順序付けられたSSetだから実現できることです)
- ランダム性のところで書いた通り、addやremoveなどの各処理がO(logn)で済みます
SkiplistList
Listインターフェースの場合は、SSetインターフェースのように値比較で進むべきかを判断できません。
そこで高さ同士のインデックス距離を別途管理します。