|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。
スキップリスト（）は、平衡二分探索木と似た用途に使う乱択アルゴリズムのデータ構造。連結リストを並列に連結させて作る。比較により順序づけ可能な要素を挿入し、スキップリスト内ではソートされた状態で保持される。ソートされた連想配列や集合の実装などに使える。挿入と探索と削除は平均O(log ''n'')である。1989年にWilliam Pughが発表した。 スキップリストは順序つきの連結リストの前向きの飛び越しのリンクを追加したものである。ノードは幾何分布や負の二項分布にてランダムに高さを設定して追加され（高さ1が確率50%、高さ2が25%、高さ3が12.5%など）、リスト上の探索において連結リストの一部を高速に飛ばすことができる。 == 説明 == スキップリストはリストの階層になっている。最下層は通常のソートされた連結リストである。上層はそれぞれ下記のリストに示すように「急行列車」のように働き、層''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木より悪いという証拠が存在する（）。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「スキップリスト」の詳細全文を読む スポンサード リンク
|