短い道を何段か重ねる
スキップリストは、整列した連結リストの上へ、いくつかの要素を飛び越える参照を重ねるデータ構造です。キー10、20、30、40、50、60が最下段へ並び、上段に10、30、60だけがあれば、55を探すときは10から30へ進み、60を越えそうなところで下段へ降ります。全てのキーは最下段にあり、上段は検索を助ける道です。上段だけに存在するキーを作りません。
木の回転によって高さを整える方式とは異なり、挿入時に乱数でノードの高さを選びます。そのため、毎回同じ形になるとは限りません。固定seedは学習用の図と実行を一致させる手段で、公平な入力や最悪の場合の速さを保証するものではありません。ここでは整数の集合を扱い、同じキーの二重挿入は新しい要素を作らずFalseを返す契約にします。
右へ進めなくなったら、一段降りる
検索では最上段の先頭から始め、次のキーが目的値より小さい間だけ右へ進みます。次が大きいか参照がないなら一段降り、同じ規則を繰り返します。最下段で止まった直後のノードが目的値なら発見です。「より小さい」という比較にしているため、止まる場所は挿入位置の直前でもあります。各段で止まったノードをupdateへ保存すると、挿入と削除にも同じ探索を使えます。
先頭の番兵は全段の参照を持ちますが、通常のキーとは比較しません。掲載コードのNoneは番兵の印と参照の不在に使い、格納するキーは整数へ限定します。参照をたどるノードは、その段へ現れたノードなので、その高さの参照配列を持っています。段を移るときのこの条件を守ることで、存在しない上段の配列要素を読まないようにします。
挿入で変える参照を限定する
25を挿入するなら、各段で25の直前にあるノードを先に求めます。新しいノードが高さ2なら、下の二段で「新ノードの次を旧後続へ」「直前の次を新ノードへ」の順に接続します。それより上の段は変えません。20と30の間へ一つのキーが増えますが、既存の高さを全て引き直す必要はありません。高さは確率1/2で次段へ延ばし、掲載例では最大8段へ制限しています。
最大8段という固定値は、小さな集合を読みやすくするための制限です。要素数を無制限に増やした際の期待O(log n)を、この固定段数の実装へそのまま主張してはいけません。一般の設計では要素数に応じた段数や拡張の規則を考えます。期待値を議論するときは、どの乱数選択とどの高さ制約を仮定したかを明示し、テストで扱う40種類のキーと分けて説明します。
| 高さ2の挿入 | 変更する参照 | そのほか |
|---|---|---|
| 段0 | update[0]と新ノードのnext[0] | キー順を維持 |
| 段1 | update[1]と新ノードのnext[1] | キー順を維持 |
| 段2以上 | 変更しない | 新ノードは参加しない |
削除と重複の検査を実行する
削除もupdateを求め、最下段の後続が対象キーかを確認します。存在しなければFalseです。対象ノードが参加する段だけ、直前の参照を対象の後続へつなぎ直します。今回のPython例は単一スレッドで、解放されたノードを並行して読んでいる相手はいません。参照を外す操作が短いからといって、そのまま並行処理へ持ち込めるわけではありません。別記事の安全なメモリ回収へ接続します。
付属コードでは固定した乱数で挿入と削除を1,000回選び、毎回Pythonのsetと全キーの所属を照合します。挿入や削除の戻り値も、集合が実際に変わったかと比較します。高さを選ぶ乱数と操作列の乱数のseedを別々に保存するので、形と操作のどちらが変わったかを追えます。空集合からの削除や同じキーの再挿入も、操作列の中で確認できます。
導入の上段の並びは、探索を説明するための例です。掲載コードで10から60を順に挿入した実際のseed7の段は、表のようになります。段3から5には40だけがあり、段6と7は空です。乱数の結果と、手で選んだ説明用の高さを区別できます。
import random
class Node:
def __init__(self,key,height):self.key=key;self.next=[None]*height
class SkipList:
def __init__(self,seed=7):self.head=Node(None,8);self.rng=random.Random(seed)
def previous(self,key):
update=[self.head]*8;node=self.head
for level in range(7,-1,-1):
while node.next[level] is not None and node.next[level].key<key:node=node.next[level]
update[level]=node
return update
def contains(self,key):
node=self.previous(key)[0].next[0]
return node is not None and node.key==key
def insert(self,key):
update=self.previous(key)
if update[0].next[0] is not None and update[0].next[0].key==key:return False
height=1
while height<8 and self.rng.random()<0.5:height+=1
node=Node(key,height)
for level in range(height):node.next[level]=update[level].next[level];update[level].next[level]=node
return True
def discard(self,key):
update=self.previous(key);node=update[0].next[0]
if node is None or node.key!=key:return False
for level in range(len(node.next)):update[level].next[level]=node.next[level]
return True
if __name__=='__main__':
demo=SkipList(seed=7)
for key in [10,20,30,40,50,60]:demo.insert(key)
for level in range(7,-1,-1):
keys=[];node=demo.head.next[level]
while node is not None:keys.append(node.key);node=node.next[level]
if keys:print('demo level=',level,'keys=',keys)
s=SkipList();reference=set();rng=random.Random(11)
for _ in range(1000):
key=rng.randrange(40)
if rng.randrange(2):assert s.insert(key)==(key not in reference);reference.add(key)
else:assert s.discard(key)==(key in reference);reference.discard(key)
assert [x for x in range(40) if s.contains(x)]==sorted(reference)
print('seed=7/11 operations=1000 reference=set passed')
| 段(0が最下段) | seed7で10〜60を挿入した結果 |
|---|---|
| 5 | 40 |
| 4 | 40 |
| 3 | 40 |
| 2 | 10,30,40,50 |
| 1 | 10,20,30,40,50 |
| 0 | 10,20,30,40,50,60 |
期待する高さと、実際の領域を分ける
上へ延びる確率を1/2とすると、制限を設けない高さの期待値は1+1/2+1/4+…=2です。各ノードが平均して定数本の参照を持つという説明から、全参照の期待量はO(n)になります。ただしこれは参照の本数で、Pythonのオブジェクトヘッダー、リストの領域、整数の格納まで正確なバイト数へ換算した値ではありません。実装の容量を測る場合は、論理的な本数と実オブジェクトを区別します。
全てのノードが最下段だけになれば、検索は通常の連結リストと同じ線形時間です。乱数で良い形を期待できることと、どんな場合も対数時間を保証することは異なります。決定的な最悪時間が必要な場合、既存の平衡木との比較が役立ちます。範囲走査では最下段を順に進める利点もありますが、一点検索の時間だけでなく、操作の組合せと保持する参照の費用から選択してください。
範囲走査では最下段へ戻る
30以上55未満の全キーを返すなら、まず30の直前まで通常の探索を行い、その後は最下段を進んで55未満のキーを出します。上段だけをたどると、そこへ現れないキーを落とします。検索で使う近道と、全要素を列挙する道の役割が違うからです。範囲の始点と終点を含むかも、比較演算へ対応させます。
返すキーがr個なら、探索の費用に加えてr個を出力する仕事が必要です。期待O(log n)という検索の説明だけで、長い範囲の列挙も同じ時間とは言えません。今回の固定8段の小実装では、なお段数の制限の注意が残ります。最下段の全キーを参照集合と照合する検査は、上段が変わっても集合の意味が保存されているかを確認する助けになります。
高さの乱数を変更する課題
昇格確率を1/2から1/4へ変えると、平均の参照本数は減る方向ですが、上段の点も少なくなります。どちらの方が速いかを、参照本数だけから断定しません。検索で右へ何回進み、何段降りたかを数え、同じキー列と問合せ集合で比較する実験を考えます。期待高さの式は1+p+p²+…=1/(1−p)です。
乱数列を変えても所属するキーの集合は同じであるべきです。したがって形の比較の前に、両方が同じ参照解の答えを返すことを検査します。段数の上限、確率、seed、操作列を保存すれば、機能の差と配置の差を分けて再現できます。短いリストの見た目だけで、全ての入力へ同じ速度差を広げないようにします。
高さを見ながら手で更新する課題
課題では、下段が10、20、30、40、上段が10、30であるリストへ、高さ2の25を挿入します。解答は、下段の20→30を20→25→30へ、上段の10→30を10→25→30へ変えることです。30や40の高さは変えません。次に25を削除すれば、この二つの参照を元の後続へ戻します。updateが段ごとに違う前任者を持つ理由を、図の矢印へ対応させてください。
追加課題は、同じ25をもう一度挿入する操作です。集合という契約では新しいノードを作らずFalseです。多重集合へ変更するなら、ノードに個数を持つか同値ノードを並べるか、削除が一個か全個かも設計し直します。コードが動くことだけでなく、検索の停止位置、参照の変更範囲、乱数による期待値、固定上限の限界をそれぞれ説明できれば到達点です。