ジャンプテーブル

変換元:https://lotabout.me/2018/skip-list/
ジャンプリスト(skip list)のペアは、バランスツリー(AVL Tree)であり、挿入/削除/検索がO(log n)のデータ構造である.その最大の利点は、原理が簡単で、実現しやすく、拡張しやすく、効率が高いことです.そのため、redis、leveldbなどのバランスツリーの代わりに人気のあるプロジェクトで使われています.
時計を踊る基本思想
まず、ジャンプテーブルは秩序あるチェーンテーブル(一般的には双方向チェーンテーブルであり、下図は双方向を示さない)を処理し、以下のようにする.
このチェーンテーブルでは、1つの数を検索するには、各要素が一致するかどうかを最初から最後まで比較する必要があります.すなわち、時間複雑度はO(n)O(n)です.同様に,数を挿入してチェーンテーブルを秩序化するには,まず適切な挿入位置を見つけてから挿入を実行する必要があり,合計もO(n)O(n)の時間である.
では、検索の速度を向上させるにはどうすればいいのでしょうか.簡単です.インデックスを作成します.
上記の図のように、前のチェーンテーブルの偶数要素を含むチェーンテーブルを新しく作成しました.これにより、要素を検索するときは、まず上位チェーンテーブルで検索し、要素が見つからない場合は下位チェーンテーブルで検索します.例えば、数字19を検索した場合のパスは、次の図のようになります.
まず上位レベルで検索し、ノード17に到達すると、次のノードが21であり、19より大きくなっていることが判明し、次のレベルの検索に移行し、見つかったターゲット番号19.
上位層のノード数はn/2 n/2であることを知っているので,このインデックスがあれば,探索の時間的複雑度はO(n/2)O(n/2)に低下する.同様に、検索時間を短縮するために、層数を増やし続けることができます.
上の4層のチェーンテーブルで25を検索すると、最上位層の検索時に21以前のすべてのノードを直接スキップできるので、非常に効率的です.
より一般的に、kk層があれば、我々が必要とする探索回数は、この背後にある原理は,二叉探索ツリーや二分探索とよく似ており,インデックスによって大量のノードをスキップし,探索効率を向上させる.
ジャンプテーブル
前節の構造は「静的」で、チェーンテーブルを1つ持ってから、上に多層インデックスを構築しました.しかし,実際の使用では,我々のチェーンテーブルは複数回の挿入/削除によって形成され,言い換えれば「動的」である.前節の構成では,上位隣接ノードと対応する下位ノードとの間の個数比が1:2であることが要求され,1つのノードを任意に挿入/削除するという要求が破壊される.
したがって、ジャンプテーブル(skip list)は、1:2を強制的に要求しないことを示しています.1つのノードがインデックスされるかどうか、いくつかの層のインデックスを構築するかは、ノードが挿入されるときにコインを投げて決定されます.もちろん,インデックスのノード,インデックスの層数はランダムであるが,検索の効率を保証するためには,各層のノード数が前節の構造に相当することを大まかに保証する.次に、ランダムに生成されたジャンプテーブルを示します.
各層のノード数は上節の構造とそれほど差がないが,上下層のノードの対応関係は完全に破られていることがわかる.
次に、ノード17が最後に挿入されたと仮定し、挿入前に挿入された位置を検索する必要がある.
次に、コインを投げて何層のインデックスを作成するかを決定し、偽コードは以下の通りです.

randomLevel()
    lvl := 1
    -- random() that returns a random value in [0...1)
    while random() < p and lvl < MaxLevel do
        lvl := lvl + 1
    return lvl

上の疑似コードはコイン投げに相当し、正面(random() < p)であれば層数を反対側に投げ出すまで加算する.このうちMaxLevelは、運が良ければ層数が高すぎることを防止し、高すぎる層数は追加の性能を提供しないことが多い.一般的にMaxLevel=log 1/pnMaxLevel=log 1/p次に、randomLevelが返す結果が2であると仮定すると、以下の結果が得られる.
ノードを削除する場合は、ノードと対応するすべてのインデックスノードをすべて削除します.もちろん、ノードを削除するには、まずそのノードを検索する必要があります.検索中にパスを記録することができます.これにより、インデックスレイヤノードを削除するときに何度も検索する必要はありません.
最悪の場合,すべてのノードにインデックスが作成されず,時間的複雑度はO(n)O(n)であることは明らかであるが,平均的に検索の時間的複雑度はO(logn)O(log
単純なパフォーマンス分析
いくつかの厳密な証明は比較的複雑な確率統計学知識に関連するので,ここでは簡単に説明するだけである.
レイヤあたりのノード数
以上、MaxLevelについて述べたが、原版論文ではL(n)で表され、L(n)層に1/p個のノードがあり、検索時にL(n)よりも高い層数を無視してL(n)層から直接検索を開始することができ、このような効率が最も高い.
1を直感的に見ると、第ll層のノードにおいても第l+1 l+1層にインデックスがある個数はnl+1=nlpnl+1=nlpであるため、第ll層のノード個数は以下のようになる.
 
nl=npl−1nl=npl−1
そこでnL(n)=1/pnL(n)=1/pを代入してL(n)=log 1/pnL(n)=log 1/p⁡nを得る.
さいこうそうすう
上から各層のノード数を導いたが,直観的に,ある層のノード数が1以下であれば最上位層と考えられ,npl−1=1 npl−1=1を代入して層数Lmax=log 1/pn+1=L(n)+1=O(logn)Lmax=log 1/p⁡n+1=L(n)+1=O(log⁡n)となる.
実際にはこの問題は直接的な解析解はなく、nnが十分大きい場合、最大到達可能な層数はO(logn)O(log
検索時間の複雑さ
検索の時間的複雑さを計算するために、検索のプロセスを逆さまにして、最後のノードを検索してから、最上位まで左または上に移動することができます.次の図では、パス上の各点について、2つの場合があります.

ノードには上階のノードがあり、上へ.このような状況が発生する確率はpである.

ノードには上のレイヤのノードがなく、左に向かいます.出現する確率は1-pです.

そこで、C(k)を第k階までの平均経路長を逆探索とすると、

C(0) = 0
C(k) = p * (  1) + (1-p) * (  2)

2つのケースもCで代入されます.

C(k) = p*(1 + C(k–1)) + (1–p)*(1 + C(k))
C(k) = C(k–1) + 1/p
C(k) = k/p

上式は,探索時に各層で平均探索が必要な経路長が1/p 1/pであり,平均の観点から我々の第1の小節構造の「静的」構造と同じであることを示している(pは1/2をとる).
また,前節ではジャンプテーブルの最大層数がO(logn)O(log
P.S.ここでは最大層数を用い,原論文ではL(n)L(n)を用いたことを証明し,L(n)L(n)層から最上位層までの平均ノード数を考慮する.ここでは理解の便宜上詳しく証明しない.
小結

の種々の探索構造が効率を向上させる方法は,空間変換時間によって得られる.

ホップテーブルは最終的に形成された構造と探索ツリーに似ている.

ホップテーブルは、新しい挿入ノードをランダムに決定することによってインデックスのレイヤ数を決定する.

ホップテーブル検索の時間複雑度はO(logn)O(log⁡n)であり,挿入/削除も同様である.

高速配列(quick sort)と他の並べ替えアルゴリズム(例えば、集計並べ替え/スタック並べ替え)は、時間的複雑度は同じであるが、複雑度の定数項は小さいと考えられる.ジャンプテーブルの原論文もジャンプテーブルが定数項の速度向上を提供することができると言っているので、定数項が小さいのはランダムアルゴリズムの特徴ではないかと思っています.これも彼らが異彩を放つ重要な要素だろう.
リファレンス

ftp://ftp.cs.umd.edu/pub/skipLists/skiplists.pdf原論文

https://ticki.github.io/blog/skip-lists-done-right/skip listのいくつかの変種、最適化

https://eugene-eeo.github.io/blog/skip-lists.htmlskip listのいくつかの関連複雑度分析

http://cglab.ca/~morin/teaching/5408/refs/p90b.pdf skip list cookbook、skip list各方面のまとめ

秩序要素で高速クエリーを実現できるデータ構造skip listを含むC++実装

Redis内部データ構造の詳細(6)--skiplist図文並茂はskip listを説明し、本論文と交差して

を対照することができる.

https://www.youtube.com/watch?v=2g9OSRKJuzMMIT skip listに関するレッスン

https://courses.csail.mit.edu/6.046/spring04/handouts/skiplists.pdfMITカリキュラム

1.あるノードは、第ll層にインデックスがあり、二項分布B(n,pl−1)B(n,pl−1)を満たすので、第ll層のノード数は、npl−1 npl−1であることが望ましい. ↩