スキップリスト

コンピュータサイエンスにおいて、スキップリスト（またはスキップリスト）は、確率的データ構造であり、 ${\mathcal {O}}(\log n)$ 検索の平均複雑度と ${\mathcal {O}}(\log n)$ 順序付けられたシーケンス内での挿入の平均複雑度 $n$ 要素。そのため、静的配列では不可能な挿入を可能にするリンクリストのような構造を維持しながら、ソート済み配列の最良の機能（検索用）を取得できます。高速検索は、部分シーケンスのリンク階層を維持することによって可能になり、各部分シーケンスは前の部分シーケンスよりもスキップする要素が少なくなります（下の図を参照）。検索は最も疎な部分シーケンスから開始され、検索対象の要素よりも小さい要素と大きい要素が 2 つ連続して見つかるまで続きます。リンク階層を介して、これら 2 つの要素は、次の最も疎な部分シーケンスの要素にリンクされ、検索は最終的にシーケンス全体で検索されるまで続けられます。スキップされる要素は、確率的に^[²^]または決定論的に^[³^]選択できますが、前者がより一般的です。

説明

スキップリストは階層構造になっています。最下層 $1$ は通常の順序付き連結リストです。上位の各層は下位のリストへの「特急レーン」として機能し、下位の層の要素は下位のリストに渡されます。 $i$ レイヤーに表示されます $i+1$ ある一定の確率で $p$ （一般的に使用される2つの値） $p$ は $1/2$ または $1/4$ 平均すると、各要素は $1/(1-p)$ リストがあり、最も背の高い要素（通常はスキップリストの先頭にある特別なヘッド要素）はすべてのリストに表示されます。スキップリストには、 $\log _{1/p}n\,$ （つまり対数の底） $1/p$ の $n$ ）リスト。

ターゲット要素の検索は、最上位リストの先頭要素から開始され、現在の要素がターゲット以上になるまで水平方向に進み続けます。現在の要素がターゲットと等しい場合、ターゲットが見つかったことになります。現在の要素がターゲットより大きい場合、または検索が連結リストの末尾に達した場合は、前の要素に戻って垂直方向に次の下位リストに移動した後、手順が繰り返されます。各連結リストにおける期待ステップ数は最大で $1/p$ これは、ターゲットから検索パスを逆方向にたどって、次の上位リストに現れる要素に到達するか、現在のリストの先頭に到達するまで追跡することで確認できます。したがって、検索の総期待コストは次のようになります。 ${\tfrac {1}{p}}\log _{1/p}n$ それは ${\mathcal {O}}(\log n)\,$ 、いつ $p$ は定数です。 $p$ 検索コストとストレージコストを交換することが可能です。たとえば、 $p=1/e$ スキップリストの平均検索時間を最小化する一方、その値は $p=1/2$ 実装を簡素化する。

実装の詳細

スキップリストに使用される要素は、複数のリストに参加できるため、複数のポインタを含むことができます。

挿入と削除は、対応するリンクリストの操作とほぼ同じように実装されますが、「背の高い」要素は複数のリンクリストに挿入または削除する必要がある点が異なります。

${\mathcal {O}}(n)$ すべてのノードを昇順で訪問することを強制する操作（リスト全体を出力するなど）は、スキップリストのレベル構造の舞台裏でのデランダム化を最適な方法で実行する機会を提供し、スキップリストを ${\mathcal {O}}(\log n)$ 検索時間。（i 番目の有限ノードのレベルを、i を 2 で繰り返し割っても奇数にならない回数に 1 を加えた値に選択します。また、負の無限ヘッダーの場合は i=0 とします。これは、負または正の無限ノードに対して可能な限り高いレベルを選択するという通常の特殊なケースがあるためです。）ただし、これにより、レベル 1 より高いノードがすべてどこにあるかを知ることができ、それらを削除することもできます。

あるいは、レベル構造を以下のように準ランダムにすることもできる。

すべてのノードをレベル1にする j ← 1 レベル j のノード数が 1 より大きい間、レベル j の各 i 番目のノードに対して、 i が奇数で、かつi がレベル j の最後のノードでない場合、以下の処理を実行する。 レベル j+1 に昇格させるかどうかをランダムに選択する それ以外の場合、 iが偶数で、ノードi-1が昇格しなかった場合 レベル j+1 に昇格させる 繰り返し終了 j ← j + 1 繰り返す

非ランダム化バージョンと同様に、準ランダム化は、他の理由がある場合にのみ実行されます。 ${\mathcal {O}}(n)$ （すべてのノードを訪問する）操作。

この準ランダム性の利点は、非ランダム化の場合ほど、レベル構造に関連する情報を敵対的なユーザーに漏らさないことです。これは望ましいことです。なぜなら、どのノードが最下位レベルにないかを知ることができる敵対的なユーザーは、上位レベルのノードを削除するだけでパフォーマンスを悪化させることができるからです。（ただし、BetheaとReiterは、それでもなお、敵対者は確率的およびタイミング的手法を使用してパフォーマンスの低下を強制できると主張しています。^{[ 4 ]}）検索パフォーマンスは依然として対数的であることが保証されています。

次のような「最適化」をしたくなるかもしれません。「次に、各i th について...」の部分で、偶数と奇数のペアごとにコイン投げをするのは忘れてください。偶数だけを昇格させるか奇数だけを昇格させるかを決めるために、コインを一度だけ投げてください。 ${\mathcal {O}}(n\log n)$ コイン投げでは、 ${\mathcal {O}}(\log n)$ それらのうち。残念ながら、これにより、敵対的なユーザーは、偶数番号のノード（レベル 1 以上にあるノードのうち）がすべてレベル 1 より高いと推測した場合に、正解する確率が 50/50 になります。これは、特定のノードが何らかの整数Nに対してレベルNにあると推測する確率が非常に低いという特性にもかかわらずです。

スキップリストは、より伝統的なバランスのとれたツリーデータ構造と同じ絶対的な最悪ケースのパフォーマンス保証を提供するものではありません。なぜなら、スキップリストの構築に使用されるコイン投げによって、バランスの悪い構造が生成される可能性が常にあるからです（ただし、^{その確率は非常に低いですが}[5]）。しかし、スキップリストは実際にはうまく機能し、ランダム化バランス方式は、バランスのとれた二分探索木で使用される決定論的バランス方式よりも実装が容易であると主張されています。スキップリストは並列コンピューティングでも有用であり、データ構造の全体的な再バランスを行うことなく、スキップリストの異なる部分に並列に挿入を行うことができます。このような並列処理は、ランダム化されたスキップリストを単一ノードの損失に対して堅牢にすることができるため、アドホック無線ネットワークでのリソース発見に特に有利です。^{[ 6 ]}

インデックス可能なスキップリスト

前述のように、スキップリストは高速 ${\mathcal {O}}(\log n)$ ソートされたシーケンスへの値の挿入と削除は可能ですが、速度が遅いだけです。 ${\mathcal {O}}(n)$ シーケンス内の特定の位置にある値のルックアップ（つまり、500 番目の値を返す）ですが、わずかな変更を加えることで、ランダムアクセスインデックスルックアップの速度を向上させることができます。 ${\mathcal {O}}(\log n)$ 。

各リンクについて、リンクの幅も保存してください。幅は、上位層の「エクスプレスレーン」リンクのそれぞれが通過する下位層のリンクの数として定義されます。

例えば、ページ上部の例にあるリンクの幅は以下のとおりです。

 1 10 o---> o---------------------------------------------------------> o トップレベル 1 3 2 5 o---> o---------------> o-----------> o----------------------> o レベル 3 1 2 1 2 3 2 o---> o--------> o---> o----------> o-----> o---------> o レベル 2 1 1 1 1 1 1 1 1 1 1 1 o---> o---> o---> o---> o---> o---> o---> o---> o---> o---> o---> o 最下位レベル ヘッド 1位 2位 3位 4位 5位 6位 7位 8位 9位 10位 0位 ノード ノード ノード ノード ノード ノード ノード ノード ノード ノード

上位レベルのリンクの幅は、その下位にある構成要素リンクの幅の合計であることに注意してください（つまり、幅10のリンクは、その直下にある幅3、2、5のリンクをまたいでいます）。したがって、すべてのレベルで幅の合計は同じになります（10 + 1 = 1 + 3 + 2 + 5 = 1 + 2 + 1 + 2 + 3 + 2）。

スキップリストをインデックス付けして i 番目の値を見つけるには、スキップリストを走査しながら、走査した各リンクの幅をカウントダウンします。次のリンクの幅が大きすぎる場合は、レベルを1つ下げます。

例えば、5 番目の位置にあるノード (ノード 5) を見つけるには、最上位レベルで幅 1 のリンクをたどります。これでさらに 4 歩必要ですが、このレベルの次の幅は 10 で大きすぎるため、1 レベル下げます。幅 3 のリンクを 1 つたどります。幅 2 のもう 1 つのステップは遠すぎるため、最下位レベルまで下げます。最後に幅 1 のリンクをたどって、目標の合計 5 (1+3+1) に到達します。

function lookupByPositionIndex(i) ノード ← ヘッド i ← i + 1 #上から下へのレベルのステップとしてヘッドをカウントしないdo while i ≥ node.width[level] do # 次のステップが遠すぎない場合 i ← i - node.width[level] # 現在の幅を減算 node ← node.next[level] # 現在のレベルで前方にトラバースするrepeat repeat return node.value end function

このインデックス作成の実装方法は、ウィリアム・ピュー著「スキップリストクックブック」^{[ 7 ]に詳しく記載されています。}

歴史

スキップリストは、1989年にウィリアム・ピューによって初めて記述された。^{[ 8 ]}

著者の言葉を引用すると：

スキップリストは確率的データ構造であり、多くのアプリケーションにおいて、バランスツリーに代わる実装方法として有力視されています。スキップリストアルゴリズムは、バランスツリーと同じ漸近的な期待時間範囲を持ちながら、よりシンプルで高速、かつメモリ使用量も少なくて済みます。

—ウィリアム・ピュー著『スキップリストの同時保守』（1989年）

使用例

スキップリストを使用するアプリケーションとフレームワークの一覧：

Apache Portable Runtime はスキップリストを実装しています。^{[ 9 ]}
MemSQLは、データベース技術における主要なインデックス構造として、ロックフリーのスキップリストを採用しています。
Linuxカーネル用のMuQSSは、スキップリストに基づいて構築された CPUスケジューラです。^{[ 10 ]}^{[ 11 ]}
Cyrus IMAPサーバーは「スキップリスト」バックエンドDB実装を提供します^{[ 12 ]}
IBM DOORSは、DOORS/DXL（DOORS拡張言語）スクリプト言語において、スキップリストをデータ型として提供しています。
Luceneはスキップリストを使用して、デルタエンコードされた投稿リストを対数時間で検索します。
Qtの「QMap」キー/値辞書（Qt 4 まで）テンプレートクラスは、スキップリストを使用して実装されています。^{[ 13 ]}
Redisは、POSIXシステム向けのANSI-Cオープンソースの永続キー/バリューストアであり、順序付きセットの実装にスキップリストを使用しています。^{[ 14 ]}
Discordは、サーバー内のメンバーリストの保存と更新を処理するためにスキップリストを使用します。^{[ 15 ]}
RocksDBはデフォルトのMemtable実装にスキップリストを使用しています。^{[ 16 ]}
Java はConcurrentSkipListSetとConcurrentSkipListMapにスキップリストを使用します。

スキップリストは、分散アプリケーション（ノードが物理コンピュータを表し、ポインタがネットワーク接続を表す）や、ロック競合が少ない、あるいはロックなしの、拡張性の高い並行優先度キューの実装にも使用されます。 ^{[ 17 ]}^[¹⁸^]^[¹⁹^]^[²⁰^]また、ロックフリーの並行辞書にも使用されます。 ^[²¹^]スキップリストを使用して（ロックレス）優先度キューと並行辞書を実装するための米国特許もいくつかあります。^[²²^]

参考文献

1 2パパダキス、トーマス (1993)。スキップリストとアルゴリズムの確率的分析(PDF) (博士論文)。ウォータールー大学。
↑ Pugh, W. (1990). "スキップリスト: バランスツリーの確率的代替案" (PDF) . Communications of the ACM . 33 (6): 668– 676. doi : 10.1145/78973.78977 . S2CID 207691558 .
↑Munro, J. Ian; Papadakis, Thomas; Sedgewick, Robert (1992). "Deterministic skip lists"(PDF). Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms (SODA '92). Orlando, Florida, USA: Society for Industrial and Applied Mathematics, Philadelphia, PA, USA. pp. 367–375. S2CID 7477119.
↑Bethea, Darrell; Reiter, Michael K. (September 21–23, 2009). Data Structures with Unpredictable Timing(PDF). ESORICS 2009, 14th European Symposium on Research in Computer Security. Saint-Malo, France. pp. 456–471, §4 "Skip Lists". doi:10.1007/978-3-642-04444-1_28. ISBN 978-3-642-04443-4.
↑Sen, Sandeep (1991). "Some observations on skip lists". Information Processing Letters. 39 (4): 173–176. doi:10.1016/0020-0190(91)90175-H.
↑Shah, Gauri (2003). Distributed Data Structures for Peer-to-Peer Systems(PDF) (Ph.D. thesis). Yale University.
↑ William Pugh. "A skip list cookbook". 1990. Section 3.4 Linear List Operations .
↑Pugh, William (April 1989). Concurrent Maintenance of Skip Lists(PS, PDF) (Technical report). Dept. of Computer Science, U. Maryland. CS-TR-2222.
↑Apache Portable Runtime APR 1.6 documentation
↑ LWN's article
↑"LKML: Con Kolivas: [ANNOUNCE] Multiple Queue Skiplist Scheduler version 0.120". lkml.org. Retrieved 2017-05-11.
↑ Cyrus IMAP server. skiplist source file
↑QMap
↑"Redis ordered set implementation". GitHub.
↑Nowack, Matt. "Using Rust to Scale Elixir for 11 Million Concurrent Users". Discord Blog. Retrieved 23 July 2023.
↑"MemTable". GitHub. Retrieved 2023-12-12.
↑ Shavit, N.; Lotan, I. (2000). "スキップリストベースの並行優先度キュー" (PDF) .第14回国際並列分散処理シンポジウム議事録。IPDPS 2000 . p. 263. CiteSeerX 10.1.1.116.3489 . doi : 10.1109/IPDPS.2000.845994 . ISBN 978-0-7695-0574-9. S2CID 8664407 .
↑ Sundell, H.; Tsigas, P. (2003). "マルチスレッドシステム向け高速かつロックフリーな並行優先度キュー". Proceedings International Parallel and Distributed Processing Symposium . p. 11. CiteSeerX 10.1.1.113.4552 . doi : 10.1109/IPDPS.2003.1213189 . ISBN 978-0-7695-1926-5. S2CID 20995116 .
↑ Fomitchev, Mikhail; Ruppert, Eric (2004).ロックフリーのリンクリストとスキップリスト(PDF) . Proc. Annual ACM Symp. on Principles of Distributed Computing (PODC). pp. 50–59 . doi : 10.1145/1011767.1011776 . ISBN 1581138024。
↑ Bajpai, R.; Dhara, KK; Krishnaswamy, V. (2008). "QPID: アイテム局所性を持つ分散優先度キュー". 2008 IEEE International Symposium on Parallel and Distributed Processing with Applications . p. 215. doi : 10.1109/ISPA.2008.90 . ISBN 978-0-7695-3471-8. S2CID 15677922 .
↑ Sundell, HK; Tsigas, P. (2004). "スケーラブルでロックフリーな並行辞書" (PDF) . 2004年ACM応用コンピューティングシンポジウム - SAC '04 論文集. p. 1438. doi : 10.1145/967900.968188 . ISBN 978-1581138122. S2CID 10393486 .
↑米国特許第7937378号

外部リンク

アルゴリズムとデータ構造の辞書における「スキップリスト」の項目
スキップリストに関する講義（MITオープンコースウェア：アルゴリズム入門）
オープンデータ構造 - 第4章 - スキップリスト、パット・モリン
スキップツリーグラフ、スキップツリーの分散バージョン
スキップツリーグラフ（スキップツリーの分散バージョン）についてさらに詳しく

[cs.uwaterloo-1] 1 2パパダキス、トーマス (1993)。スキップリストとアルゴリズムの確率的分析(PDF) (博士論文)。ウォータールー大学。

[pugh-2] Pugh, W. (1990). "スキップリスト: バランスツリーの確率的代替案" (PDF) . Communications of the ACM . 33 (6): 668– 676. doi : 10.1145/78973.78977 . S2CID 207691558 .

[3] Munro, J. Ian; Papadakis, Thomas; Sedgewick, Robert (1992). "Deterministic skip lists"(PDF). Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms (SODA '92). Orlando, Florida, USA: Society for Industrial and Applied Mathematics, Philadelphia, PA, USA. pp. 367–375. S2CID 7477119.

[4] Bethea, Darrell; Reiter, Michael K. (September 21–23, 2009). Data Structures with Unpredictable Timing(PDF). ESORICS 2009, 14th European Symposium on Research in Computer Security. Saint-Malo, France. pp. 456–471, §4 "Skip Lists". doi:10.1007/978-3-642-04444-1_28. ISBN 978-3-642-04443-4.

[5] Sen, Sandeep (1991). "Some observations on skip lists". Information Processing Letters. 39 (4): 173–176. doi:10.1016/0020-0190(91)90175-H.

[6] Shah, Gauri (2003). Distributed Data Structures for Peer-to-Peer Systems(PDF) (Ph.D. thesis). Yale University.

[7] William Pugh. "A skip list cookbook". 1990. Section 3.4 Linear List Operations .

[8] Pugh, William (April 1989). Concurrent Maintenance of Skip Lists(PS, PDF) (Technical report). Dept. of Computer Science, U. Maryland. CS-TR-2222.

[9] Apache Portable Runtime APR 1.6 documentation

[10] LWN's article

[11] "LKML: Con Kolivas: [ANNOUNCE] Multiple Queue Skiplist Scheduler version 0.120". lkml.org. Retrieved 2017-05-11.

[12] Cyrus IMAP server. skiplist source file

[13] QMap

[14] "Redis ordered set implementation". GitHub.

[15] Nowack, Matt. "Using Rust to Scale Elixir for 11 Million Concurrent Users". Discord Blog. Retrieved 23 July 2023.

[16] "MemTable". GitHub. Retrieved 2023-12-12.

[17] Shavit, N.; Lotan, I. (2000). "スキップリストベースの並行優先度キュー" (PDF) .第14回国際並列分散処理シンポジウム議事録。IPDPS 2000 . p. 263. CiteSeerX 10.1.1.116.3489 . doi : 10.1109/IPDPS.2000.845994 . ISBN 978-0-7695-0574-9. S2CID 8664407 .

[18] Sundell, H.; Tsigas, P. (2003). "マルチスレッドシステム向け高速かつロックフリーな並行優先度キュー". Proceedings International Parallel and Distributed Processing Symposium . p. 11. CiteSeerX 10.1.1.113.4552 . doi : 10.1109/IPDPS.2003.1213189 . ISBN 978-0-7695-1926-5. S2CID 20995116 .

[19] Fomitchev, Mikhail; Ruppert, Eric (2004).ロックフリーのリンクリストとスキップリスト(PDF) . Proc. Annual ACM Symp. on Principles of Distributed Computing (PODC). pp. 50–59 . doi : 10.1145/1011767.1011776 . ISBN 1581138024。

[20] Bajpai, R.; Dhara, KK; Krishnaswamy, V. (2008). "QPID: アイテム局所性を持つ分散優先度キュー". 2008 IEEE International Symposium on Parallel and Distributed Processing with Applications . p. 215. doi : 10.1109/ISPA.2008.90 . ISBN 978-0-7695-3471-8. S2CID 15677922 .

[21] Sundell, HK; Tsigas, P. (2004). "スケーラブルでロックフリーな並行辞書" (PDF) . 2004年ACM応用コンピューティングシンポジウム - SAC '04 論文集. p. 1438. doi : 10.1145/967900.968188 . ISBN 978-1581138122. S2CID 10393486 .

[22] 米国特許第7937378号

[

[

[ 4 ]

その確率は非常に低いですが

[ 6 ]

[ 7 ]に詳しく記載されています。

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[

[

[

[

[

スキップリスト

説明

実装の詳細

インデックス可能なスキップリスト

歴史

使用例

関連項目

参考文献

外部リンク

関連するトピック

コンピュータサイエンス

確率的

データ構造

検索の平均複雑度