スキップリスト

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動先: 案内検索
スキップリスト
種類 リスト
考案者 William Pugh
発表年 1989年
計算量ビッグ・オー記法
平均 最悪
空間計算量
探索の時間計算量
挿入の時間計算量
削除の時間計算量

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

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

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

説明[編集]

スキップリストはリストの階層になっている。最下層は通常のソートされた連結リストである。上層はそれぞれ下記のリストに示すように「急行列車」のように働き、層iに存在するリストの要素は層i+1においては固定の確率p(通常は0.5を使用)で存在する。平均すると、それぞれの要素は1/(1-p)の高さとなり、最も高い要素、つまり普通スキップリストの先頭の特別扱いされる要素はO(log1/p n)の高さである。

目的の要素を探すために、最上層のリストの先頭の要素から始めて、目的の要素と同じかそれ以下の要素のうち最後のものまでスキャンする。各連結リストのリンクを辿る数の期待値は1/pとなる。これは目的の要素から後ろに戻って上層のリストにつながる要素に到達するまでの期待値であることから理解できる。従って探索の総コストはO(log1/p n / p)で、pを固定すればO(log n)である。pにさまざまな値を選ぶことで、探索時間とメモリ使用量のトレードオフをとることが可能である。

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

また、昇順にそれぞれのノードを訪れるようなO(n)の操作において、裏でスキップリストの構造を最適化することもできる。i番目のノードの高さをi=m*2^n(mは奇数)とした場合のnに1加えたものにする。しかし、この方法では誰かが何処に高い要素があるかを知ってそれをリストから削除することでアルゴリズムの効率を低下させることができる。

その代わりに、次のように高さを擬似的にランダムにすることができる。最初に全てのノードの高さを1にする。次にi番目のノードについて、奇数ならば高さを2にするかどうかをランダムに決める。偶数ならば直前のノードの高さが2になっていないときのみ高さを2にする。高くなったノードの数が2以上なら高さを上げてこれを繰り返す。ランダマイズを行わないアルゴリズムと同様、ノードを全て訪れる場合にのみ高さを擬似的にランダマイズすればよい。ランダマイズを行わない方法に対する、擬似的なランダマイズを行う方法の利点は、高さに関する情報を敵意のあるユーザーにあまり知られないということである。検索時間については、ランダマイズを行わないものと同様対数時間であることが保証されている。

これらの2つの主張を説明しよう。まず、検索が対数時間で終わることを示す。高さが1以上である全てのノードの中でn番目のノードを見つけることを考える。nが偶数であれば、その高さが1より大きい確率は1/2であるが、もしノードの高さが1であるならばn-1番目のノードの高さは1より大きいことが保証される。nが奇数であれば、その高さが1より大きい確率は1/2である。このときn番目のノードの高さが1でかつn-1番目のノードの高さも1であるとすると、n-2番目のノードの高さは1より大きいことが保証される。この解析を高さが2以上のノード、3以上のノード……と繰り返していく。それぞれの解析でnは高さがk以上であるようなノードの中で何番目であるかということを注意しておく。以上から、検索時間はランダマイズされていないスキップリストと比べて最良の場合(探しているノードが考えうる限り最も高さが高いとき)は同じで、最悪でも2倍となる(左に1回ではなく2回動かなければならないため)。

次に、敵意のあるユーザがどの程度の正確さでノードが高さk以上であるという想定ができるかを示す。まず、敵意のあるユーザはある特定のノードが高さ2以上であるかどうかを1/2の確率で当てることができる。もしそのユーザが2つの連続する高さが2以上のノードの位置を知っており、その2つのうち左側のノードが高さが2以上のノードの中で奇数番目であることがわかれば、そのユーザがどのノードが高さが3以上であるかを当てられる確率は1/2になる。したがって、高さが3以上のノードについてそのユーザの想定が正しいかどうかは1/4となる。この解析を帰納的に適用すると、ある特定のノードが高さk以上であるかどうかを当てることができる確率は1/(2^(k-1))である。

スキップリストは上述のバランスとりを最近行っている場合でも、伝統的な平衡木と同じ最悪の場合のパフォーマンスを保証しない。なぜなら、確率はとても低いがバランスの悪い構造になる場合が常にあるからである。しかし実際にはよく動作し、ランダム化されたバランスとりの仕組みは平衡二分探索木の決定論的なバランスとりの仕組みより実装が容易であることが示されている。スキップリストは並列計算においても有用で、それは挿入において全体のリバランスが不要でスキップリストの違う場所において並列に行われるからである。

メモリアクセスの局所性の問題やその他の問題のため、スキップリストが実際の性能とメモリ効率において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[4] にて下記の拡張を書いている。

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

スキップ四分木[編集]

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

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

スキップグラフ[編集]

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

実装[編集]

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

参照[編集]

  1. ^ Pugh, William (August 1989). “Skip lists: a probabilistic alternative to balanced trees”. Proceedings of the Workshop on Algorithms and Data Structures, Ottawa Canada. 
  2. ^ Pugh, William (June 1990). “Skip lists: a probabilistic alternative to balanced trees”. Communications of the ACM 33: 668-676. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.17.9380. 
  3. ^ Pugh, William (1990). “Concurrent Maintenance of Skip Lists”. Univ. of Maryland Institute for Advanced Computer Studies Report No. UMIACS-TR-90-80 (University of Maryland at College Park). http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.17.8201. 
  4. ^ a b Pugh, William (1990). “A Skip List Cookbook”. Univ. of Maryland Institute for Advanced Computer Studies Report No. UMIACS-TR-89-72.1 (University of Maryland at College Park). http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.17.524. 
  5. ^ J. R. Woodwark (1984). “Compressed Quad Trees”. Computer journal 27 (3): 225-229. http://comjnl.oxfordjournals.org/content/27/3/225.full.pdf. 
  6. ^ David Eppstein; Michael T. Goodrich; Jonathan Z. Sun (2005). “The Skip Quadtree: A Simple Dynamic Data Structure for Multidimensional Data”. SCG '05 Proceedings of the twenty-first annual symposium on Computational geometry: 296-305. doi:10.1145/1064092.1064138. http://arxiv.org/abs/cs/0507049. 
  7. ^ James Aspnes; Gauri Shah (2003). “Skip graphs”. Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms: 384–393. http://arxiv.org/abs/cs/0306043. 
  8. ^ ConcurrentSkipListSet (Java Platform SE 8 )
  9. ^ ConcurrentSkipListMap (Java Platform SE 8 )