スキップリスト

スキップリストとは

スキップリストは、平衡二分探索木のように、データの挿入、検索、削除を効率的に行うためのデータ構造です。連結リストを多層化することで、検索速度を向上させています。このデータ構造は、1989年にウィリアム・ピューによって発表されました。

基本構造

スキップリストは、複数の層から構成されています。最下層は通常のソートされた連結リストであり、その上の層は下層のリストを「急行列車」のようにショートカットします。各要素は、幾何分布や負の二項分布に基づいてランダムに高さを決定され、複数のリストに属します。

例えば、高さ1の要素は確率50%、高さ2の要素は25%といったように、高さが高くなるほど確率は低くなります。これにより、リストの探索時に一部を高速にスキップすることが可能になります。

平均的に、各要素は1/(1-p)個のリストに属し、最も高い要素はすべてのリストに含まれます。スキップリストは、およそlog(1/p)n個の連結リストで構成されます。

探索方法

スキップリストで要素を探索する際には、まず最上層の連結リストの先頭から、目的の要素と同じかそれより大きい要素を探します。もし目的の要素が見つかれば探索は完了です。そうでなければ、一つ下の層に降りて同じ操作を繰り返します。

各リストにおけるリンクを辿る数の期待値は最大で1/pとなり、探索全体のコストは(log(1/p)n)/pとなります。pを固定した場合、探索時間はO(log n)となります。pの値を調整することで、探索時間とメモリ使用量のトレードオフを考慮できます。

実装の詳細

スキップリストでは、各要素が複数のポインタを持ち、複数のリストに属することが可能です。要素の挿入と削除は、連結リストと同様に行われますが、「背の高い」要素は複数のリストに対して操作する必要があります。

高さのランダム化

スキップリストの性能を保証するためには、要素の高さをランダムに決定する必要があります。しかし、完全にランダムな高さ設定は、敵対的なユーザーに高さ情報を漏らす可能性があります。

そこで、擬似的なランダム化が用いられます。まず、全てのノードの高さを1とし、各ノードについて、奇数番目のノードはランダムに高さを2にするかどうかを決定し、偶数番目のノードは直前のノードの高さが2になっていない場合のみ高さを2にします。この操作を、ノードの高さが2以上になるまで繰り返します。

この擬似ランダム化は、ノードをすべて訪問する場合にのみ実行し、敵意のあるユーザーに高さ情報を漏らさない利点があります。

最適化

さらに、コイン投げの回数を削減する最適化も可能です。奇数と偶数のペアに対してコイン投げを行う代わりに、コインを1回だけ振って、偶数番目または奇数番目のノードの高さを上げるかを決めます。これにより、コイン投げの回数をO(n log n)からO(log n)に削減できます。ただし、この方法では「全ての偶数番目のノードは高さが1より大きい」という推測が50%の確率で当たってしまう可能性があります。

スキップリストの利点と欠点

スキップリストは、平衡木と同じ最悪時性能を保証するわけではありませんが、実際には良好に動作します。ランダム化されたバランス調整は、決定論的なバランス調整よりも実装が容易であるという利点があります。

また、スキップリストは並列計算にも適しており、複数の箇所で同時に挿入操作を行うことが可能です。この並列化は、アドホック無線ネットワークでのリソース探索において特に有用です。

インデックス付きスキップリスト

通常のスキップリストでは、値の挿入や削除はO(log n)で可能ですが、系列中の特定の位置の値を取得する操作はO(n)の時間がかかります。しかし、少し変更を加えることで、ランダムアクセスをO(log n)に改善できます。

幅の概念

各リンクに「幅」の情報を追加します。ここでいう「幅」とは、そのリンクが最下層でいくつ分のリンクを飛ばすかを表します。例えば、ある層のリンクが、その下の層のリンク３つ分をショートカットする場合、そのリンクの幅は３となります。

上の層のリンクの幅は、その下の層のリンク幅の和と等しくなります。

インデックスによるアクセス

スキップリストでi番目の値を探すには、スキップリスト内を、進むリンクの幅だけ必要ステップ数を減らしながらたどります。もし次のリンク幅が大きすぎる場合は、一つ下の層に降りて同じ操作を繰り返します。

この方法により、指定されたインデックスの値を効率的に取得できます。

歴史

スキップリストは、ウィリアム・ピューによって発明され、彼の論文に詳細が記載されています。著者は、スキップリストは平衡木に代わる有力な実装手法であると述べています。しかし、速度とメモリの使用量に関しては、議論が続いています。

拡張機能

ウィリアム・ピューは、論文「A Skip List Cookbook」で以下の拡張機能を提案しました。

• - 検索指: 指定した要素から距離k以内の要素をO(log k)で検索。
• - スキップリストの分割・結合。
• - インデックスを指定して要素を取得する（O(log n)）。
• - キーの比較回数の削減。
• - キーの重複許可。
• - ノードの高さの確率分布を他のものに変更。

スキップ四分木とスキップ八分木

スキップリストを2次元やそれ以上に拡張したものがスキップ四分木やスキップ八分木です。一番下の階層は圧縮四分木で構成され、要素にランダムな高さが割り当てられます。探索・挿入・削除の計算量はスキップリストと同様に平均O(log n)で、空間計算量は平均O(n)です。

スキップグラフ

スキップグラフは、P2Pネットワーク環境を想定した分散データ構造で、スキップリストを基にしています。各ノードが1つのマシンに対応し、双方向連結リストを形成します。

実装

Javaでは、Java 6以降、標準ライブラリに`java.util.concurrent.ConcurrentSkipListSet`や`ConcurrentSkipListMap`が追加されています。

参照

• - William Pugh, Skip Lists: A Probabilistic Alternative to Balanced Trees.

もう一度検索