スキップリスト

スキップリスト
種類	リスト
考案者	William Pugh
発表年	1989年
計算量（ビッグ・オー記法）
	平均	最悪
空間計算量	${\mathcal {O}}(n)$	${\mathcal {O}}(n\log n)$
探索の時間計算量	${\mathcal {O}}(\log n)$	${\mathcal {O}}(n)$
挿入の時間計算量	${\mathcal {O}}(\log n)$	${\mathcal {O}}(n)$
削除の時間計算量	${\mathcal {O}}(\log n)$	${\mathcal {O}}(n)$

スキップリスト（英: skip list）は、平衡二分探索木と似た用途に使う乱択アルゴリズムのデータ構造。連結リストを並列に連結させて作る。比較により順序づけ可能な要素を挿入し、スキップリスト内ではソートされた状態で保持される。ソートされた連想配列や集合の実装などに使える。挿入と探索と削除は平均O(log n)である。1989年にウィリアム・ピューが発表した。

スキップリストは順序つきの連結リストの前向きの飛び越しのリンクを追加したものである。ノードは幾何分布や負の二項分布にてランダムに高さを設定して追加され（高さ1が確率50%、高さ2が25%、高さ3が12.5%など）、リスト上の探索において連結リストの一部を高速に飛ばすことができる。

スキップリストの例。1〜10を追加し、ソートされた状態で保持されている。

説明

スキップリストはリストの階層になっている。最下層は通常のソートされた連結リストである。それより上の層は、それぞれ下のリストに対する「急行列車」のように働き、層i に存在するリストの要素は層i+1 においては固定の確率p（良く使われる p の値は 1/2 と 1/4）で存在する。各要素は平均で 1/(1-p)個のリストに属し、最も背の高い要素、つまり普通スキップリストの先頭の特別扱いされる要素はすべてのリストに属する。スキップリストは $\log _{1/p}n\,$個の連結リストを含む。

目的の要素を探索するには、まず、最上層の連結リストの先頭の要素から（水平方向に）スキャンして、目的の要素と同じかそれより大きい要素を探し出す。もし、探し出した要素が目的の要素と等しいならば、探索は完了。もし、探し出した要素が目的の要素より大きいならば、あるいは、リストの最後の要素に到達してしまった場合は、一つ前の要素に戻ってから一つ下の層の連結リストに（垂直方向に）降り、そのリストに対して同じ操作を繰り返す。各連結リストにおいてリンクを辿る数の期待値は最大でも 1/p となる。これは目的の要素から逆向きに戻って上層のリストにつながる要素に到達するまでの期待値であることから理解できる。従って探索の総コストは $(\log _{1/p}n)/p\,$で、pを固定すれば${\mathcal {O}}(\log n)\,$である。pにさまざまな値を選ぶことで、探索時間とメモリ使用量のトレードオフをとることが可能である。

実装の詳細

スキップリストで用いられる要素は1つ以上のポインタを含む可能性があるが、それは、1つ以上のリストに属している可能性があるからである。

挿入と削除は、連結リストの対応する操作と同様の実装になるが、"背の高い"要素は2つ以上の連結リストに対して挿入及び削除する必要がある。

また、全てのノードを昇順に訪れるような${\mathcal {O}}(n)$の操作において、裏でスキップリストのレベル構造のランダム性を取り除き、探索時間が${\mathcal {O}}(\log n)$である最適な構造に変えてもよい。（i番目のノードの高さをi=m*2^n（mは奇数）とした場合のnに1加えたものにする。また、i=0 は最大の高さとする。）しかし、この方法では誰かが何処に高い要素があるかを知ってそれをリストから削除することができる。

その代わりに、次のように高さを擬似的にランダマイズすることができる。最初に全てのノードの高さを1にする。次に各i番目のノードについて、奇数ならば高さを2にするかどうかをランダムに決める。偶数ならば直前のノードの高さが2になっていないときのみ高さを2にする。高くなったノードの数が2以上なら高さを上げてこれを繰り返す。 ランダム性の削除と同様に、この擬似的なランダマイズはノードを全て訪れる場合にのみ実行する。

擬似的なランダマイズを行う利点は、ランダム性の無い場合と違い、敵意のあるユーザーに高さに関する情報を漏らさないことである。悪意あるユーザが高さに関する情報を知っていると、レベルの高いノードを削除するだけで性能を悪化させことができるため、この性質は望ましい。(これに対し、BetheaとReiterは、悪意あるユーザが性能劣化を起こすために、確率的タイミング方法を使用できると主張している。) 検索時間については、ランダム性の無い場合と同様、対数時間であることが保証されている。

以下の「最適化」を考えてみよう。「次に, 各i番目のノードに対して・・・」の部分で、各奇数と偶数のペアに対するコイン投げをするのをやめ、その替わり、コインを1回だけ振って、全てのペアに対して偶数番目のノードの高さを上げるか、あるいは奇数の方の高さを上げるかを決める。これで、コイン投げの回数は、${\mathcal {O}}(n\log n)$ でなく ${\mathcal {O}}(\log n)$ に削減できる。この方法では、悪意を持ったユーザが、ある1つのノードの高さを正しく推測できる確率は非常に低いにも関わらず、「全ての偶数番目のノードは高さが1より大きいだろう」という推測が50％の確率で当たってしまう。

スキップリストは、より伝統的な平衡木と同じ最悪時のパフォーマンスを保証しない。なぜなら、（確率はとても低いが）バランスの悪い構造になる場合が常にあるからである。しかし実際にはよく動作し、ランダム化されたバランスとりの仕組みは平衡二分探索木の決定論的なバランスとりの仕組みより実装が容易であることが示されている。スキップリストは並列計算においても有用で、挿入はスキップリストのいくつかの部分で並列に実施でき、全体のリバランスが不要である。この並列化は、アドホック無線ネットワークでのリソース探索において特に有用となりうる。なぜなら、ランダム性のあるスキップリストは単一ノード損失に対して堅牢にすることができるからである。

Indexable skiplist

上で述べられているように、スキップリストでは、データ系列への値の挿入や削除は高速に（${\mathcal {O}}(\log n)$で）可能であるが、系列の中のある指定した場所の値の取り出し（例えば、500番目の値を返す）は遅く、${\mathcal {O}}(n)$ の時間がかかる。しかし、少し変更を加えることで、ランダムアクセス の実行時間は${\mathcal {O}}(\log n)$にまで改良することができる。

すべてのリンクに対し、リンクの「幅」も格納することにする。ここでリンクの「幅」とは、「急行列車」のリンクが飛ばす（最下層での）リンクの数である。

例として、上で挙げた例のリンクの幅を次に示す。

   1                               10
 o---> o---------------------------------------------------------> o    最上層
   1           3              2                    5
 o---> o---------------> o---------> o---------------------------> o    第3層
   1        2        1        2              3              2
 o---> o---------> o---> o---------> o---------------> o---------> o    第2層
   1     1     1     1     1     1     1     1     1     1     1
 o---> o---> o---> o---> o---> o---> o---> o---> o---> o---> o---> o    最下層
                                         
Head  1st   2nd   3rd   4th   5th   6th   7th   8th   9th   10th  NIL
      Node  Node  Node  Node  Node  Node  Node  Node  Node  Node

第2層以上のリンクの幅は、そのリンクの下にある、下位層のリンク幅の和に等しいことに注意。（例えば、最上位層のリンク幅10は、そのすぐ下にある3つのリンクの幅 3、2、5の和になっている。）したがって、すべての層において、すべてのリンクの幅の和は等しい (10 + 1 = 1 + 3 + 2 + 5 = 1 + 2 + 1 + 2 + 5)。

スキップリストにインデクスをつけて i 番目の値を探すには、スキップリスト内を、進んだリンクの幅の分だけ必要ステップ数を減らしながら、リンクを辿っていけばよい。次のリンク幅が大きすぎる場合には、下の層へ降りる。

例えば、上の例で5番目の値を得たい場合には、まず最上位層の幅1のリンクを進む。残りの必要ステップ数は 4=5-1 であるが、次のステップ幅は10であり大きすぎるので、第3層へ降りる。この層で、幅3のリンクを進む。 残りの必要ステップ数は1で、次のリンク幅は2のため大きすぎ、下の層へ降りる。第2層の次のリンクも幅が2で大きすぎるため、最下層に降りる。最後に幅1のリンクを1つ進めば、5(=1+3+1)ステップ進んだことになり、目的のノードにたどり着く。

 function lookupByPositionIndex(i)
     node ← head
     i ← i + 1                           # don't count the head as a step
     for level from top to bottom do
          while i ? node.width[level] do # if next step is not too far
              i ← i - node.width[level]  # subtract the current width
              node ← node.next[level]    # traverse forward at the current level
          repeat
     repeat
     return node.value
 end function

このインデクス付けの実装方法については、Section 3.4 Linear List Operations in "A skip list cookbook" by William Pughに詳細がある。

歴史

スキップリストはWillam Pughによって発明され、下記の参照に示される論文に詳細が記載されている。下記の外部リンクを辿って原著論文を読むこともできる。

著者の言を引用すればこうである。

Skip lists are a probabilistic data structure that seem likely to supplant balanced trees as the implementation method of choice for many applications. Skip list algorithms have the same asymptotic expected time bounds as balanced trees and are simpler, faster and use less space.

しかし、速度と使用メモリの利点についてはその後に議論があるようだ[1]。

拡張

1990年に William Pugh は論文 A Skip List Cookbook にて下記の拡張を書いている。

• 検索指 - 指定した要素から距離 k 以内を O(log k) で検索
• スキップリストの分割・結合
• インデックスを指定して要素を取得 - O(log n)
• キーの比較回数の削減の改良
• キーの重複の許可
• ノードの高さの確率分布に他の物を使用

スキップ四分木

スキップリストはリストのため1次元だが、これを2次元やそれ以上に拡張した物をスキップ四分木（英: skip quadtree）・スキップ八分木（英: skip octree）という。一番下の階層は連結リストに相当する部分に圧縮四分木を使い、要素にランダムに高さをふり、各高さで圧縮四分木を作る。四分木の同じ分割点に当たる部分は隣の高さの四分木の分割点同士でリンクを張りたどれるようにする。探索・挿入・削除の計算量はスキップリスト同様に平均 O(log n)。圧縮四分木を使った事により空間計算量は平均 O(n)。2005年に David Eppstein らが発表した。

なお、kd木でも類似の事が出来る。

スキップグラフ

スキップグラフとは、スキップリストを元に、P2Pネットワーク環境を想定した分散データ構造。スキップリスト上の1つのノードが1つのマシンに対応し、連結を双方向連結リストにする。2003年に James Aspnes らが発表した。

実装

Java では Java 6 より標準ライブラリに java.util.concurrent.ConcurrentSkipListSet や ConcurrentSkipListMap が追加になっている。