スキップリスト

スキップリスト
種類	リスト
考案者	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年にWilliam Pughが発表した。

スキップリストは順序つきの連結リストの前向きの飛び越しのリンクを追加したものである。ノードは幾何分布や負の二項分布にてランダムに高さを設定して追加され（高さ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にさまざまな値を選ぶことで、探索時間とメモリ使用量のトレードオフをとることが可能である。

Implementation details

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

挿入と削除は、連結リストの対応する操作と同様の実装になるが、"背の高い"要素は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番目のノードに対して・・・」の部分で、各奇数と偶数のペアに対するコイン投げをするのをやめ、その替わり、コインを１回だけ振って、全てのペアに対して偶数番目のノードの高さを上げるか、あるいは奇数の方の高さを上げるかを決める。これで、コイン投げの回数は、${\mathcal {O}}(n\log n)$ でなく ${\mathcal {O}}(\log n)$ に削減できる。 しかし残念ながら、この方法では、悪意あるユーザの「全ての偶数番目のノードは高さが１より大きいだろう」という推測が５０％の確率で当たってしまう。悪意あるユーザが、ある１つのノードの高さを正しく推測できる確率は非常に低いにも関わらず。

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

メモリアクセスの局所性の問題やその他の問題のため、スキップリストが実際の性能とメモリ効率においてB木より悪いという証拠が存在する（[1]）。

歴史

スキップリストは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.

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

拡張

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 が追加になっている。