第06回： 5月27日

情報システム基礎論２：第 6 回 (担当：古賀)
Skip List
2014 年 5 月 27 日
レジュメ URL: http://sd.is.uec.ac.jp/koga/lecture/IF2/
はじめに
1
スキップリストはリストをベースとしながら、実用的にはバランスが取れた探索木と同様の access ス
ピードを実現するデータ構造である。スキップリストの実装例としては以下のようなものがある。
• IMAP サーバの mailbox データベース管理
マルチレベルリスト
2
2.1
アイデア
線形リストは insert, delete, access にそれぞれ O(n) かかる。これは、リストの要素を 1 つ 1 つ辿りな
がら調べるしかないため。リストをノードを飛ばしつつだどれれば高速な access を実現できる。
• n: 登録データの数
2.2
データ構造
複数 (m ≥ 2) 本のリスト Lm , Lm−1 , . . . , L1 で構成される。これを以下の規則で接続する (図 1)。
• 上から Lm , Lm−1 , . . . , L1 の順で配置する。
• リスト Li では、直下のリスト Li−1 のノード s 個が飛ばされる。図 1 では s = 2。
• 各リスト上でデータは整列されている。
Li に含まれるデータの集合を Si とすると、
Sm ⊆ Sm−1 ⊆ · · · ⊆ S1 = S(データ全体).
リスト Li 上のデータ数 |Si | =
1
n
si−1
.
L3
-inf
L2
-inf
L1
-inf
list
head
15
4
1
37
15
4
9
15
31
23
31
37
35
37
m=3
図 1: マルチレベルリスト
ノードのデータ構造:
struct node {
struct node *next; /* 右方向へのリンク */
struct node *down; /* 下方向へのリンク */
mydata; /* 自分が保持するデータ */
rightdata; /* 右のノードが保持するデータ */
};
access 操作: データ x を access する場合。
1. Lm のリストの-∞ ノードからスタート
2. /* L2 より上にいる場合 */
if (rightdata) ≤ x then 右へ進む /* x が右ノードよりも右に存在 */
else 下へ進む /* x が右ノードよりは左に存在 */
3. /* L1 にいる場合 */
if (rightdata) ≤ x then 右へ進む
else (mydata) と x が一致するか確認。一致すれば x が発見された。
1 回の access の計算量は (横への移動回数) と (下への移動回数) の合計。
1. Lm で横に移動する回数 ≤ Lm 上のデータ数 =
n
sm−1
2. Li (1 ≤ i ≤ m − 1) で横に移動する区間は Li+1 で隣接ノードに挟まれた区間より短い。よって、Li
で横に移動する回数 ≤ s − 1
3. 下に移動する回数: m − 1。
なので、最大で
n
sm−1
+ (m − 1)(s − 1) + (m − 1) =
n
sm−1
+ (m − 1)s.
とくに、s = 2, m = log2 n とすると access の計算量は 2 log2 n となり O(log n) が達成される。
2
l(9)=4
0
-inf
9
-inf
9
37
1
31
37
23
31
37
23
31
1
-inf
4
9
4
9
1
-inf
list
head
1
15
35
37
39
図 2: skiplist
スキップリスト
3
マルチレベルリストは規則的な構成により完全にバランスが取れている。従って、データベースの更新
がなければアクセス効率が非常によい。しかし、insert, delete があると、バランスが崩れ再構成が大変に
なる。
スキップリストは確率的なマルチレベルリストである。データ挿入時に乱数を利用し再構成に頼らずに
バランスをとる。スキップリストでは、s = 2 のマルチレベルリストのバランスを確率的に近似する。
s = 2 のマルチレベルリストでは、Li に存在するデータの半分が Li+1 に存在する。つまり、|Si+1 | = 12 |Si |。
↓
スキップリストでは、Li に存在するデータ数の期待値が Li+1 に存在するデータ数の期待値の半分。つま
り、E[|Si+1 |] = 12 E[|Si |]。
3.1
挿入操作
Definition 1 データ x に対して l(x) = max {i|x ∈ Li } を x のレベルと呼ぶ。
l(x) は x がどのリストに存在するかを定める。具体的には、L1 , L2 , · · · , Ll(x) に x が配置される。
データ x の insert 操作
まず、x のレベル l(x) を計算する。l(x) > m であれば、−∞ ノードをヘッドとする新しいリストを作成す
る。その後、access(x) を行う。この際、
• i > l(x) であるレベル Li ではリンクを辿るのみ。
• i ≤ l(x) であるレベル Li では、下のレベルに移動する前に x を右に挿入する。
3
-inf
9
-inf
9
-inf
1
-inf
list
head
4
9
4
9
37
37
31
15
23
31
23
31
coin=0
33
33
35
coin=1
37
37
39
l(33)=2
図 3: ノード 33 の挿入
l(x) は以下のアルゴリズムで定める。
表になる確率 p =
1
2
のコイントスを最初に裏が出るまで繰り返す。コインを振った回数を l(x) とする。
P [x が Li に存在する] = P [l(x) ≥ i] = P [表が (i − 1) 回連続出る] =
これから、E[|Si+1 |] =
n
2i
=
1
2
·
n
2i−1
1
2i−1
.
= 12 E[|Si |]。
なお、図では、コインが表になることを coin= 1、裏になることを coin= 0 と記述している。
Theorem 2 n 個のデータを挿入した時、m = maxx∈S l(x) は高い確率で O(log n) になる。
Proof: n 個のデータを x1 , x2 , · · · , xn とする。t を 0 以上の整数とし、l(xi ) > t となる確率を考える。xi
挿入時にコインが連続で t 回表になると、xi は Lt+1 上に存在するので、P [l(xi ) > t] = 21t 。
P [m > t] = P [∃i, l(xi ) > t] ≤ n ×
1
n
= t.
2t
2
ここで α を定数として、t = α log2 n とすると
P [m > α log2 n] ≤
3.2
1
n
= α−1 .
n
2α log2 n
access 操作の計算量
計算量は (下への移動回数 + 横への移動回数)。
x への access 操作において、レベル j での横への移動回数を Ij (x) とすると、access 操作の計算量は
(m − 1) +
m
X
j=1
Lemma 3 E[Ij (x)] = 1
4
Ij (x).
access to 35
Z4
-inf
9
-inf
9
15
23
31
4
9
15
23
31
4
9
15
23
31
37
coin=0 coin=0
-inf
-inf
list
head
1
coin=0
Z’4
coin=1
Z3
37
Z’3
37
35
37
39
coin=1
図 4: ノード 35 への access
Proof:
• zj : x へアクセスする時に通る Lj の最右ノード
• zj0 : Lj における zj の右隣のノード
(Lj−1 で横に移動する回数) ≤ (Lj−1 上で zj と zj0 の間にあるノード数)
右辺は以下の事実により決まる。
• zj < y < zj0 なる y に対しては Lj−1 でのコイントスで裏が出た。
• zj0 では Lj−1 でのコイントスで表が出た。
以上から、
(Lj−1 において zj と zj0 の間にあるノード数)=(コインを振ってはじめて表が出るまでの回数)−1.
E[Ij (x)] =
Theorem 4 高い確率で (m − 1) +
Pm
j=1 Ij (x)
1
1
2
− 1 = 2 − 1 = 1.
= O(log n).
E[Ij (x)] = O(1) かつ m が高確率で O(log n) より成立。
5

Download Report