スキップリスト

スキップリスト︵skip list︶は確率的アルゴリズムのためのデータ構造であり、並列な連結リストに基づいている。効率は平衡2分探索木と同等である。大半の操作について平均O(log n)である。

基本的にスキップリストは順序つきの連結リストの前向きのリンクを追加したものである。Pughによる原著論文によると、前向きのリンクはGeometric/Negative Binomial distributionという乱数を用いた手法で追加されていて、リスト上の探索においてリストの一部を高速に飛ばすことができる。挿入と探索と削除は対数の乱数時間で行われる。

1990年にWilliam Pughによって発明されたスキップリストは計算機科学における重要なアルゴリズムのうち最も年代の浅いものである。

説明

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

1
1-----4---6
1---3-4---6-----9
1-2-3-4-5-6-7-8-9-10

目的の要素を探すために、最上層のリストの先頭の要素から始めて、目的の要素と同じかそれ以下の要素のうち最後のものまでスキャンする。各連結リストのリンクを辿る数の期待値は1/pとなる。これは目的の要素から後ろに戻って上層のリストにつながる要素に到達するまでの期待値であることから理解できる。従って探索の総コストはO(log_1/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)).

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

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

参考資料

• Pugh, William (June 1990). “Skip lists: a probabilistic alternative to balanced trees”. Communications of the ACM 33: 668-676. 

外部リンク

• William Pughによる原著論文