スキップリスト

出典: フリー百科事典『ウィキペディア(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以上なら高さを上げてこれを繰り返す。ランダマイズを行わないアルゴリズムと同様、ノードを全て訪れる場合にのみ高さを擬似的にランダマイズすればよい。ランダマイズを行わない方法に対する、擬似的なランダマイズを行う方法の利点は、高さに関する情報を敵意のあるユーザーにあまり知られないということである。検索時間については、ランダマイズを行わないものと同様対数時間であることが保証されている。

Let us prove these two claims. First, to prove that the search time is guaranteed to be logarithmic. Suppose we search for and find node n where n is the position of the found node among the nodes of level 1 or higher. If n is even, then there is a 50/50 chance that it is higher than level 1. This time, though, if it is not higher than level 1 then node n-1 is guaranteed to be higher than level 1. If n is odd, then there is a 50/50 chance that it is higher than level 1. Given that it is not, there is a 50/50 chance that node n-1 is higher than level 1. Given that this is not either, we are guaranteed that node n-2 is higher than level 1. We repeat the analysis for nodes of level 2 or higher, level 3 or higher, etc. always keeping in mind that n is the position of the node among the ones of level k or higher for integer k. So the search time if constant in the best case (if the found node is the highest possible level) and 2 times the worst case for the search time for the totally derandomized skip-list (because we have to keep moving left twice rather than keep moving left once).

Next, let's prove something about the probability of an adversarial user's guess of a node being level k or higher being correct. First, the adversarial user has a 50/50 chance of correctly guessing that a particular node is level 2 or higher. If he/she knows the positions of two consecutive nodes of level 2 or higher, and knows that the one on the left is in an odd numbered position among the nodes of level 2 or higher, he/she has a 50/50 chance of correctly guessing which one is of level 3 or higher. So, his/her probibility of being correct, when guessing that a node is level 3 or higher, is 1/4. Inductively continuing this analysis, we see that his/her probability of guessing that a particular node is level k or higher is 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 )