Skip Lists

Skip Lists は 1990年に William Pugh によって開発されたリスト構造体の一種である。 オリジナルの論文は
William Pugh, "Skip Lists: A Probablistic Alternative to Balanced Trees", Communications of the ACM, June 1990
となっている。

この論文は ftp://ftp.cs.umd.edu/pub/skipLists/skiplists.pdf からコピーを入手可能である。 また、Unix Magazine 1999年 1月号 を入手できれば、 そこには日本語で書かれた解説があるが、 これはほとんど論文丸写しに近いので、きっと重宝するだろう。


数多くの、要素が増減しなおかつ入れ替わるようなデータ構造で、 さらにランダムアクセスが多く、 検索も頻発するようなデータを管理する必要があるとしよう。 一応、「データの各要素はソートすることができる」ともしよう。

通常、こういう場合は tree 構造、特に平衡木を使う。

平衡木とは、木構造の一種で root から leaf まで到達するのに必要な node の数がほぼ均等(だいたい1段か2段ぐらいの違いしかないよう)に 構築するものを言う。 当然この平衡木のキーポイントは
「どうやって木の不均衡を検出し、是正するか」
というポイントにあるのだが、これがやたらめったら難しい。 この平衡木の一種である AVL Tree は 『tcsh と実習でしか使わない』 と言われるほどの困難さで、 大抵の場合バグがある。

このため一般には「おおざっぱに、かついい加減に」平衡化する、 イージーな解法に逃げることが多い。

Skip List は
「多少メモリを多く消費するが、簡単に実装できる」
AVL と確率的に等価な状態を作れるデータ構造で、 基本的には「リスト構造」の一種である。


通常、単方向リストは1つだけポインターを持っていて、 自分の次の node を指している。 このため、このリストを手繰らないと node 間を移動することはできず、 結果移動には O(n) の時間が必要となる。

Skip Lists はその名の通り、複数のリストを使ったリンクリストである。


Skip Lists そのものを理解する前に Multi Lists というリンクリストを 理解しよう。

Multi Lists も自分の隣接する node を覚えるための ポインターを持っている。 これを Level 0 Pointer と呼ぼう。 また、この Pointer で実装される、 全 node を手繰ることができるリンクリストを Level 0 List と呼ぼう。

Level 0 List 上の最初の node から始まって、 一つ飛びに node を選び、 それらを順にポインターでつないでリンクリストをつくろう。 これを Level 1 List と呼び、そのためのポインターを Level 1 Pointer と呼ぼう。 当然、どの node も Level 0 と 1 の両方の Pointer を保持するための 領域を保持しているものとする。

同様に、Level 2 List, Level 3 List …とどんどん高いレベルの リンクリストをつくることができる。 Level n+1 List は常に Level n List の node を 1つ飛びにつないだものである。 そしてその実現のために n+2 個の Pointer を各 node は保持する。

Multi Lists はこれらのリンクリスト全てを記憶できるだけの ポインターが準備され、値が設定された node からなる、 複数のリンクリストが同時に実装されたものである。 仮に Level k までの Pointer が Non-NULL で信頼できる場合、 その node を Level k node と呼ぶことにしよう。

こうしてできた Multi Lists は、 node がソートされていることが保証されているならば、 目的の値を持った node へは O( log n ) で到達できることが 保証される。 ただし、1 node の挿入や削除は、 挿入ポイントや削除ポイントの関係で Level 1 以上のリンクリストに対して多大な影響を与える。 このため、Multi Lists というリスト構造は、 任意のポイントへの挿入・削除を頻繁に必要とするリストに使うと、 破滅的にパフォーマンスが悪くなる。 唯一の例外は常に「末尾への追加」「末尾からの削除」だけから なる場合…例えばファイルシステムの 間接ブロック管理だけである。


Skip Lists は基本的なデータ構造は Multi Lists と全く同じである。 唯一違うのは、node の挿入に際して、 その node の Level を「乱数で」決めるところにある。 この乱数は

  1. その Skip Lists で利用できる最大のレベルを Max とし、 0 を Min とする整数を返す。
  2. 0 を返す確率は 1/2 + (1/2)(Max+1) である。
  3. k を返す確率は (1/2)(k+1) である。

という条件を満すものとする。

この条件下で node を挿入していくと、 確率的に Level k node の数は理想的な Multi Lists と同じ数に 近づいていく。 このため、node 数が増えるにつれて Multi Lists に近い性質を持ったリスト群を保有するリスト構造が 構築される確率が高くなり、 逆に性質の悪いリストになる確率は下がる。

削除の場合は、削除する node の Level k までのリストから、 その node を順次削除すれば良い。 この場合、その node が理想的な配置に近いと、 この削除によって Skip Lists 全体は理想的な状態から離れてしまうが、 そうじゃない場合は逆に理想的な状態に近づく可能性が高い。 結局、 Skip Lists 全体としては、確率的にある品質範囲内に 収まるようになる。

挿入、削除とも、操作するべき Pointer の数は k に比例している。 k は最大で log n であり、 全 Level のリンクリスト操作のために O(log n) の処理を必要とする ので、挿入、削除とも平均して O(log n) で実行できることになる。

確率論的な検証はオリジナルの論文を参照して欲しい。


Skip Lists の最大の魅力は「リンクリストがいっぱいあるだけ」なので、 実装がすばらしく簡単だ、という点にある。 平衡木をうめきながら実装するよりも、 乱数に問題を押し付けた方が簡単なのだ。

平衡木を作るよりも Skip Lists を使う方が、大抵の場合、得だろう。 Skip Lists の場合、 挿入と削除が頻繁に行われている間は乱数にお任せでコスト的に十分 釣り合う。

リストを長時間保持する必要があるなら、 検索の度に必要だったリストの「手繰り数」を数えて、 それが log( n ) より大幅に大きければ、 一旦 Multi Lists に構築し直せば良い。

もし、リストを長時間保持する必要がないなら、 「運が悪かった」と諦めれば良い。 世の中そんなものだ。