スキップリスト

スキップリスト
タイプ	リスト
発明された	1989
発明者	W. ピュー
ビッグO記法による時間計算量 手術 平均 最悪の場合 検索 ${\displaystyle {\mathcal {O}}(\log n)}$ ${\displaystyle {\mathcal {O}}(n)}$ [ 1 ] 入れる ${\displaystyle {\mathcal {O}}(\log n)}$ ${\displaystyle {\mathcal {O}}(n)}$ 消去 ${\displaystyle {\mathcal {O}}(\log n)}$ ${\displaystyle {\mathcal {O}}(n)}$ 空間複雑性 空間 ${\displaystyle {\mathcal {O}}(n)}$ ${\displaystyle {\mathcal {O}}(n\log n)}$ [ 1 ]

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

説明

スキップリストデータ構造の概略図。矢印の付いた各ボックスはポインタを表し、行は疎な部分列を表すリンクリストです。下部の番号付きボックス（黄色）は順序付けられたデータ列を表します。検索は、最上部の最も疎な部分列から下方向へ進み、検索要素を囲む連続する要素が見つかるまで続きます。

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

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

実装の詳細

スキップリストに要素を挿入する

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

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

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

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

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

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

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

次のような「最適化」を行うのは魅力的です。「次に、各i番目…」の部分では、偶数と奇数のペアごとにコインを投げる必要はありません。コインを1回投げて、偶数ノードのみを昇格させるか、奇数ノードのみを昇格させるかを決定します。コインを投げる代わりに、奇数ノードのみを昇格させます。残念ながら、これでは敵対的なユーザーが、レベル1以上のノードのうち、すべての偶数ノードがレベル1よりも高いと推測した場合、50/50の確率で正解してしまいます。これは、ある整数Nに対して特定のノードがレベルNにあると推測する確率が非常に低いという性質があるにもかかわらずです。 ${\displaystyle {\mathcal {O}}(n\log n)}$ ${\displaystyle {\mathcal {O}}(\log n)}$

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

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

上で説明したように、スキップ リストはソートされたシーケンスから値を高速に挿入および削除できますが、シーケンス内の特定の位置にある値の検索は低速です(つまり、500 番目の値を返します)。ただし、小さな変更を加えることで、ランダム アクセスインデックス検索の速度を まで向上できます 。 ${\displaystyle {\mathcal {O}}(\log n)}$ ${\displaystyle {\mathcal {O}}(n)}$ ${\displaystyle {\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）に到達します。

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

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

参照

• ブルームフィルタ
• スキップグラフ

参考文献

1. パパダキス、トーマス (1993).スキップリストとアルゴリズムの確率的分析(PDF) (Ph.D.). ウォータールー大学.
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). 「決定論的スキップリスト」(PDF) .第3回ACM-SIAM離散アルゴリズムシンポジウム (SODA '92) の議事録. 米国フロリダ州オーランド：Society for Industrial and Applied Mathematics, 米国ペンシルベニア州フィラデルフィア. pp.  367– 375. S2CID 7477119 . 
4. ベシア、ダレル、ライター、マイケル・K. (2009年9月21～23日).予測不可能なタイミングを持つデータ構造(PDF) . ESORICS 2009, 第14回ヨーロッパコンピュータセキュリティ研究シンポジウム. サン＝マロ、フランス. pp. 456–471, §4「スキップリスト」. doi : 10.1007/978-3-642-04444-1_28 . ISBN 978-3-642-04443-4。
5. セン、サンディープ (1991). 「スキップリストに関するいくつかの考察」.情報処理レター. 39 (4): 173– 176. doi : 10.1016/0020-0190(91)90175-H .
6. Shah, Gauri (2003).ピアツーピアシステムのための分散データ構造(PDF) (博士論文). イェール大学.
7. William Pugh. 「スキップリストのクックブック」 1990年. セクション3.4 線形リスト操作.
8. Pugh, William (1989年4月).スキップリストの同時メンテナンス(PS, PDF) (技術レポート). メリーランド大学コンピュータサイエンス学部. CS-TR-2222.
9. Apache ポータブル ランタイム APR 1.6 ドキュメント
10. LWNの 記事
11. 「LKML: Con Kolivas: [ANNOUNCE] Multiple Queue Skiplist Scheduler version 0.120」lkml.org . 2017年5月11日閲覧。
12. Cyrus IMAP サーバー。 スキップリスト ソース ファイル
13. Qマップ
14. 「Redis 順序付きセットの実装」。GitHub 。
15. Nowack, Matt. 「Rustを使用してElixirを1100万人の同時ユーザー向けに拡張」 Discordブログ2023年7月23日閲覧。
16. "MemTable" . GitHub . 2023年12月12日閲覧。
17. Shavit, N.; Lotan, I. (2000). 「スキップリストベースの並行優先キュー」(PDF) . Proceedings 14th International Parallel and Distributed Processing Symposium. 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 国際並列分散処理シンポジウム. 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 Symposium on Applied Computing - SAC '04 の議事録. p. 1438. doi : 10.1145/967900.968188 . ISBN 978-1581138122. S2CID  10393486 .
22. 米国特許 7937378 

外部リンク

• アルゴリズムとデータ構造の辞書の「スキップリスト」の項目
• スキップリストの講義（MIT OpenCourseWare：アルゴリズム入門）
• オープンデータ構造 - 第4章 - スキップリスト、Pat Morin
• スキップツリーの分散バージョンであるスキップツリーグラフ
• スキップツリーの分散バージョンであるスキップツリーグラフの詳細