離散数学

スキップリスト(スキップグラフ)落合 秀也

今日の内容• 連結リスト （復習）
• スキップリスト• スキップグラフ2

連結リスト (復習)
• 「値とnextポインタ」で構成された要素(ノード)を連結して作られる値のリスト
4
値 nextポインタ

struct list_element {int value;
struct list_element* next;};
nil or null (終了)を意味する

開始

4

3

1

7

8

6
3

連結リストにおける検索
値xを持つノードを検索(search)する場合
struct list_element* search(int x){
struct list_element* p=start;
while((p=p->next)!=null){if ( p->value == x ){return p;}
開始点からnextポインタをつたって、その}ノードの値がxと一致するまで探索する
return null;(あるいはnextポインタ=nullで終了する)
}
開始

43

17864

連結リストにおける挿入・削除• 8の後ろに2を入れたい場合: insert(8,2)の操作• 2へのポインタをqとする• 8をsearchした結果をpとする• pp=p->nextと置く• p->next=q, q->next=ppと置く
開始

431nextq2

786next

ppp• 8を削除したい場合: delete(8)の操作• 8をsearchした結果をpとする (8の前をppとする)• pp->next=p->nextと置く
開始

43

17pp

8
next

p6next5

連結リストの計算量
開始431786n• 検索の場合• 検索対象の出現パターンに依存するが、すべて等しい確率で出現すると仮定すると、期待値 n/2回の操作でヒットする。
• ヒットしない場合: n回の操作が必要
いずれにしても O(n)• 挿入・削除の場合• 検索したのちに、ポインタの組換え操作を行う： O(n)• 先頭にだけ挿入する場合は O(1)6

今日の内容• 連結リスト （復習）
• スキップリスト• スキップグラフ

7

連結リストの高速化を考える• 順序関係が定義される値であれば、順序関係に基づいて、ソートしておくことによって、リストでの検索効率を向上させることができる
 具体的には スキップリスト
開始

43

1786

開始

13

4678

昇順にソートされた連結リストの例
8

スキップリストの高速化原理• 通常の連結リストは各駅停車である• スキップリストでは 快速、準急、急行、特急 を用意する

L4

H

1L3

H

1L2

H

1L1H

1L0H

110632310645687810910• 高速化のレベルを L0, L1, L2, L3, … と呼ぶことにする

1211129

スキップリストの階層の作り方• スキップリストでは「レベル Li に属するノードが、確率pで、レベルLi+1に属する」
ように階層を作る。pには1/2や1/4などが使われる。
• Headの直後のノードはすべてのレベルに属する• 平均的に Li+1に属するノード数 = p×Liに属するノード数 となる。
• L0のノード数をnとすると、Li に属するノード数の期待値は npi となる。

L4

H

1L3

H

1L2

H

1L1

H

1L0

H

1

106
3
2

3

10

6
4

5687810910

12111210

スキップリストの検索• x を検索する場合を考える• 上位の階層から検索を始める• Li で pi ≦ x < qi (or nil) となる pi, qiを見つける (pi, qiはLiで直前直後の関係にあるものとする)• Li-1 で piから開始し、pi-1 ≦ x < qi-1となるとなる pi-1, qi-1を見つける (pi-1, qi-1はLi-1で直前直後の関係にあるものとする)• 同様の操作を繰り返す (どこかの時点で、x=pとなればそこで終了。あるいはL0まで検索して見つからなければ終了)

L4
L3

H

1

例： 9の検索1 ≦ 9 < (nil)1 ≦ 9 < 10H

1106 ≦ 9 < 10L2

H

L1

H

1L0

H

1

16108 ≦ 9 < 1032

364568781091012
111211

練習• 以下のスキップリストにおいて• 5の検索• 7の検索• 11の検索• 12の検索を行った際の探索経路をそれぞれ図示せよ (水平移動の操作数も数えてみよ)

L4

H1L3H

1L2H

1L1H

1L0H

11063231064568781091012111212

解1/4: 5の検索

L4H

11 ≦ 5 < (nil)1 ≦ 5 < 10L3H

110
1≦5<6L2H

L1H

1L0H

1

16103≦5<6323645687810910121112

水平移動の操作数: 4回
13解2/4: 7の検索

L4H

1

1 ≦ 5 < (nil)1 ≦ 5 < 10L3H

1

106 ≦ 7 < 10L2H

16106≦7<8L1H

1L0H

1323645687810910121112水平移動の操作数: 3回
14

解3/4: 11の検索

L4H

L3

H

1

1 ≦ 11 < (nil)
10 ≦ 11 < (nil)11010 ≦ 11 < (nil)L2

H161010 ≦ 11 < 12L1H

1L0H

132

3645687810910121112

水平移動の操作数: 3回
15

解4/4: 12の検索

L4H

L3

H

1

1 ≦ 12 < (nil)
10 ≦ 12 < (nil)11010 ≦ 12 < (nil)L2

H161012 = 12L1

H

1L0H

1323645687810910121112

水平移動の操作数: 3回
16スキップリストへのノードの挿入
6 を挿入する場合： insert(6)(1) 6がどのレベルにまで入るかを乱数を用いて確率的に選ぶ  以下の例では L2まで(2) p<6<q となるp, qを該当する各レベルで求め、p.next = &6; 6.next = q とする

L4

H

1

1 ≦ 6 < (nil)1 ≦ 6 < 10L3L2

H

1106

1 ≦ 6 < 10H

1

103≦6<8L1

H

1

63

8

10126L0

H

1

2

3

4

5

7

5≦6<78910111217

スキップリストからのノードの削除
6 を削除する場合： delete(6)p<6<q となるp, qを該当する各レベルで求め、p.next = q とする

L4L3

H

1

1 ≦ 6 < (nil)1 ≦ 6 < 10H

1

106 < 10

1<6L2H166<83<6L1H1365<6L0H

1231045810126<7678910111218

スキップリストの計算量• スキップリストは、確率的に作られる。そのため、期待値で考えることにする (以下、nはリスト長, pは確率)• まず、階層の高さN は npN = 1 より (1/p)N=n∴ N= log1/p n• 各レベルでのホップ数は、オーダーで 1/p

Li+1

3

Li31261012

確率pで選出: ノード数は p倍になる
Li+1での１区間あたりのLiでのノード数は 1/p 個になる

• よって、探索の数は• N×1/p = ( log1/p n ) / p• 通常 pは定数なので O(log n) となる

19

スキップリストの強み• 各ノードをインターネット上のPCとして考えてみよう= 分散環境を考える• 検索は、広域に渡って行われるが、ノードの追加・削除の操作は、各レベルでの隣接ノードとの関係で行われる
 平衡二分探索木の場合は、広域ロックをする必要がある。

L4L3L2L1L0H

1H

1H

1H

1H

11063231064568781091012111220

今日の内容• 連結リスト （復習）
• スキップリスト• スキップグラフ

21

スキップグラフ• スキップリストをベースに（分散環境への応用を目的に）開発されたデータ構造• 完全な自律分散を実現• 耐障害性を向上• スキップグラフの特徴• 双方向連結リスト• どのノードからでも検索を開始できる• 各レベルに複数の双方向連結リストが存在 スキップリストの特徴• 単方向連結リスト。探索開始ノードが決まっていた。各レベ
ルには一つの連結リスト• 障害性に強くない (1ノードが消えると、修復が難しい)
22

スキップリストの耐障害性
L4L3L2L1L0H

1H

1H

1

H

1

H

1

10632

310645687810910121112

障害発生！！

L4L3L2L1L0H

1

H

1

H

1

H

1

H

15を検索できなくなる
3から5への接続をどう修復する？
10
6
3
2

3

106？

568
78

10910

12111223

スキップグラフ• 双方向連結リスト• どのノードからでも検索を開始できる• 各レベルに複数の連結リストが存在

L3
L2

L1
L0

完全に分散
耐障害性の向上

1

11
3

10

1

73
164

2

3

1073
1

1164569878111091012111224

スキップグラフでの検索方法
スキップリストと同じように考えれば良い
例: ノード10 から ノード4を検索する場合

L3L2L1L0

111310173
164

23107311164569878111091012111225

スキップグラフの耐障害性• 特定のノードが消失して、ある探索パスで到達できなくても、別の探索パス（=バックアップパス）が存在すれば、耐障害性がある、と言える
例: ノード4の検索

L3
L2

L1L0

1

11310

173

164

23107311164

569878111091012111226

今日の内容• 連結リスト （復習）
• スキップリスト• スキップグラフ27