スキップリスト

スキップリスト
スキップリスト
タイプ	リスト
発明された	1989
発明者	W. ピュー
手術
ビッグO記法による時間計算量
手術	平均
検索	お（ログ ⁡ n ） {\displaystyle {\mathcal {O}}(\log n)}
入れる	お（ログ ⁡ n ） {\displaystyle {\mathcal {O}}(\log n)}
消去	お（ログ ⁡ n ） {\displaystyle {\mathcal {O}}(\log n)}
空間複雑性
空間	お（ n ） {\displaystyle {\mathcal {O}}(n)}

確率的データ構造

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

説明

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

実装の詳細

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

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

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

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

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

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

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

上で説明したように、スキップリストはソートされたシーケンスから値を高速に挿入および削除できますが、シーケンス内の特定の位置にある値の検索は低速です(つまり、500 番目の値を返します)。ただし、小さな変更を加えることで、ランダムアクセスインデックス検索の速度をまで向上できます。 ${\mathcal {O}}(\log n)$ ${\mathcal {O}}(n)$ ${\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 Portable Runtimeはスキップリストを実装しています。^[9]
MemSQL は、データベーステクノロジの主要なインデックス構造として、ロックフリーのスキップリストを使用します。
Linuxカーネル用のMuQSSは、スキップリスト上に構築されたCPUスケジューラです。 ^[10]^[11]
Cyrus IMAPサーバーは「スキップリスト」バックエンドDB実装を提供する^[12]
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]

参照

参考文献

^ ab パパダキス, トーマス (1993). スキップリストとアルゴリズムの確率的分析(PDF) (Ph.D.). ウォータールー大学.
^ 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). 「決定論的スキップリスト」(PDF) .第3回ACM-SIAM離散アルゴリズムシンポジウム (SODA '92) の議事録. 米国フロリダ州オーランド：Society for Industrial and Applied Mathematics, 米国ペンシルベニア州フィラデルフィア. pp. 367– 375. S2CID 7477119.
^ ベシア・ダレル、ライター・マイケル・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。
^ セン、サンディープ (1991). 「スキップリストに関するいくつかの考察」.情報処理レター. 39 (4): 173– 176. doi :10.1016/0020-0190(91)90175-H.
^ Shah, Gauri (2003). ピアツーピアシステムのための分散データ構造(PDF) (博士論文). イェール大学.
^ William Pugh. 「スキップリストのクックブック」 1990年. セクション3.4 線形リスト操作.
^ Pugh, William (1989年4月). スキップリストの同時メンテナンス(PS, PDF) (技術レポート). メリーランド大学コンピュータサイエンス学部. CS-TR-2222.
^ Apache ポータブルランタイム APR 1.6 ドキュメント
^ LWNの記事
^ 「LKML: Con Kolivas: [ANNOUNCE] Multiple Queue Skiplist Scheduler version 0.120」。lkml.org 。 2017年5月11日閲覧。
^ Cyrus IMAP サーバー。スキップリストソースファイル
^ Qマップ
^ 「Redis 順序付きセットの実装」。GitHub。
^ Nowack, Matt. 「Rustを使用してElixirを1100万人の同時ユーザー向けにスケールさせる」Discordブログ. 2023年7月23日閲覧。
^ “MemTable”. GitHub . 2023年12月12日閲覧。
^ 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。
^ 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 国際並列分散処理シンポジウム. p. 215. doi :10.1109/ISPA.2008.90. ISBN 978-0-7695-3471-8. S2CID 15677922。
^ 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。
^ 米国特許 7937378

外部リンク

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

[cs.uwaterloo-1] パパダキス, トーマス (1993). スキップリストとアルゴリズムの確率的分析(PDF) (Ph.D.). ウォータールー大学.

[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). 「決定論的スキップリスト」(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