データ構造と 　アルゴリズムⅠ

Transcription

1 算法数理工学 第 5 回 定兼邦彦

2 ハッシュ表 辞書操作 (INSERT, DELETE, SEARCH) を効率よく実現するデータ構造 応用 :C 言語のコンパイラでの記号表の管理 キー : 変数名などの文字列 ハッシュ表は実際的な場面では極めて速い 妥当な仮定の下で,SEARCH の時間の期待値は O() 最悪の場合 () 2

3 チェイン法を用いるハッシュ法の解析 SEARCH は最悪の場合 () 時間 平均時間を解析する スロット m 個, 要素を格納するハッシュ表 T の負荷率 (load factor) = /m と定義 は つのチェインに格納される要素数の平均 解析は を変数として行う (, m が共に無限大に近づくとき, はある定数に留まるとする ) 3

4 ハッシュ法の平均的性能 各要素は m 個のスロットに同じ程度にハッシュされると仮定する ( 単純一様ハッシュの仮定 simple uiform hashig) ハッシュ値 h(k) は O() 時間で計算できると仮定 キー k をもつ要素の探索は, リスト T[h(k)] の長さに比例した時間が必要 4

5 定理 チェイン法を用いるハッシュ表で, 単純一様ハッシュを仮定すると, 失敗に終わる探索にかかる時間の平均は (+ ) 定理 2 チェイン法を用いるハッシュ表で, 単純一様ハッシュを仮定すると, 成功する探索にかかる時間の平均は (+ ) 5

6 ハッシュ関数 良いハッシュの条件 = 単純一様ハッシュ 各キーは U から確率分布 P に従って独立に取り出されると仮定すると, 条件は と書ける k: h( k ) j P( k) m ただし, 一般に P は未知 ) キーがランダムな実数 k (0k) で一様独立のとき, h(k) = km は上の条件を満たす ( j 0,,, m 6

7 除算法 キー k を m で割った剰余をハッシュ値とする h(k) = k mod m 利点 : ハッシュ関数の計算が高速 m は 2 のべき乗に近くない素数がいい m = 2 p のとき,h(k) は k の最下位 p ビット m = 2 p で k が基数 2 p の文字列のとき, 文字を並び替えてもハッシュ値は同じ 7

8 例 = 2000 個の文字列を格納する場合 負荷率 を 3 に近くするには, m = 70 にすればいい 70 は素数で,2 のべき乗には近くない h(k) = k mod 70 とすればいい このハッシュ関数が実際のデータでうまく働くことを確かめるべき 8

9 乗算法 まず, キー k にある定数 A (0 < A < ) を掛け, その小数部分 kaka を取り出す 次に, その値に m を掛け, 小数部分を切り捨てる h( k) m ka ka m の値はあまり重要ではない 2 のべき乗にすると計算が簡単 A 5 / が良いと言われる 9

10 オープンアドレス指定法 オープンアドレス指定法 (ope addressig) では, 要素は連結リストではなくハッシュ表の中に格納される. ハッシュ表が埋まるとそれ以上挿入できない 負荷率は 以下 連結リストを用いないため, スペースが小さい ハッシュ関数を拡張して衝突を回避する 引数 : キーと探査番号 h: U {0,,...,m} {0,,...,m} 探査列 h(k,0), h(k,),..., h(k,m) は 0,,...,m の順列でなければならない 0

11 要素の挿入 it HASH_INSERT(data *T, data k) { it i, j; i = 0; // i: 探査番号 do { j = h(k,i); if (T[j] == NIL) { // スロットが空なら T[j] = k; // 新しいデータを挿入 retur j; } else { i++; // 探査番号を 増やす } } while (i!= m); // m 回試す pritf( ハッシュ表オーバーフロー ); }

12 要素の検索 it HASH_SEARCH(data *T, data k) { it i, j; i = 0; // i: 探査番号 do { j = h(k,i); if (T[j] = k) retur j; // k を発見 i++; } while (T[j]!= NIL && i!= m); // スロットが空か,m 回探索した retur NIL; // k は見つからなかった } 2

13 要素の削除 削除したい要素のあるスロットを NIL にすると, 他の要素が検索できなくなる NIL スロットが見つかると検索は終了するため 削除するときは NIL でなく特別な値 DELETED を格納する SEARCH では DELETED が現れても探索を続ける INSERT では NIL または DELETED の場所に挿入 問題点 : 探索時間が負荷率 で表せない 要素を削除する必要がある場合はチェイン法が好まれる 3

14 衝突回避の方法 一様ハッシュ (uiform hashig) を仮定 : 各キーに対する探査列として, {0,,...,m} の m! 通りの順列のどれもが同程度に現れる 近似的な一様ハッシュを用いる 線形探査 2 次関数探査 ダブルハッシュ法 4

15 線形探査 通常のハッシュ関数 h : U {0,,...,m} に対し h(k,i) = (h (k)+i) mod m (i=0,,...,m) を用いる 探査されるスロット : T[h (k)], T[h (k)+],..., T[m], T[0], T[],..., T[h (k)] 異なる探査列は m 通りしかない ( 開始位置で決定 ) 問題点 : 主クラスタ化 (primary clusterig) が起きる 直前の i 個のスロットが使用中である空きスロットが選択される確率は (i+)/m であるため, 連続する使用中のスロットは常に大きくなる 5

16 2 次関数探査 2 次関数探査 (quadratic probig) では h(k,i) = (h (k)+c i+c 2 i 2 ) mod m (i=0,,...,m) を用いる c, c 2, m は適切に選ぶ必要がある h(k,0) = h(k 2,0) の場合は h(k,i) = h(k 2,i) となってしまう ( 副クラスタ化, secodary clusterig) 異なる探査列は m 通りしかない ( 開始位置で決定 ) 6

17 ダブルハッシュ法 h(k,i) = (h (k)+i h 2 (k)) mod m 探査列は, 初期位置と次に探査する位置までの距離の両方が k に依存している h 2 (k) の値は m と互いに素である必要がある h 2 (k) と m の最大公約数が d のとき, ハッシュ表の /d しか検査しない 例 : m を 2 のべき乗,h 2 は常に奇数 例 2: m を素数, h 2 は m 未満の非負整数 h 2 (k)=+(k mod m ) (m 2 ) 個の探査列が利用できる 7

18 オープンアドレスハッシュ法の解析 ハッシュ表の負荷率 をパラメータとして解析 一様ハッシュを用いると仮定する 定理負荷率 =/m< のオープンアドレスハッシュ表において, 失敗に終わる探索に必要な探査数の期待値は /() 以下 証明失敗に終わる探索では, 最後の探査を除いて, 毎回の探査では異なるキーを格納しているスロットにアクセスし, 最後に未使用のスロットにアクセスする. 8

19 i = 0,,... に対して, p i = Pr{ 未使用のスロットを見つけるまでちょうど i 回の探査を行った } q i = Pr{ 未使用のスロットを見つけるまで少なくとも i 回の探査を行った } と定義する. 探査回数の期待値は i0 ip q i i 最初の探査が使用中のスロットにアクセスする確率は /m であるから q m i 9

20 20 一様ハッシュ法では,2 回目の探査は残りの m 個のスロットの つに対して行われ, その中には 個の使用中のスロットがあるため一般に 2 m m q i i i m i m i m m q

21 2 失敗に終わる探索に必要な探査回数の期待値は が定数なら O() 時間で実行できる = 0.5 なら 2 回以下 = 0.9 なら 0 回以下 i i i ip i q

22 系一様ハッシュを仮定すると, 負荷率 のオープンアドレスハッシュ表に, ある要素を挿入するために必要な探査回数の平均は /() 以下 証明キーを挿入するには未使用スロットを発見する必要がある. その探査回数の期待値は失敗に終わる探索での探査回数の期待値に等しい. 22

23 定理一様ハッシュを仮定し, 表内の各キーは等確率で探索の対象になるとする. 負荷率 のオープンアドレスハッシュ表において, 成功に至る探索に必要な探査回数の期待値は l 証明キー k の探索は, それを挿入したときと同じ探査列を探査する. 系より,k がハッシュ表に i+ 番目に挿入されたキーならば, 探索に必要な探査回数の期待値は /(i/m) = m/(mi) 以下 23

24 24 ハッシュ表に存在する 個のキーについて平均を取ると, 成功に至る探索に必要な探査回数の平均が得られる. =0.5 のとき 回以下 =0.9 のとき 回以下 l ) l( l 0 0 m m H H i m m i m m m m i i

25 万能ハッシュ法 運が悪いと, 個のキーが同じスロットにハッシュされ, 平均検索時間が () になってしまう 万能ハッシュ法 (uiversal hashig) では, ハッシュ関数をランダムに選択する どのように意地悪くキーを選択しても, 平均として良い性能を示す. 25

26 H: キーの普遍集合 U から値域 {0,,...,m} へのハッシュ関数の有限集合 H が万能 (uiversal) 全ての異なるキーの組 x, y U に対し,h(x) = h(y) となるハッシュ関数 h H の個数がちょうど H /m ハッシュ関数を万能な H の中からランダムに選んだときに,x と y が衝突する確率が /m これは h(x) と h(y) が値域 {0,,...,m} からランダムに選択されたときの衝突確率に等しい 26

27 定理 h を万能な集合から選択されたハッシュ関数とする.h を用いて 個のキーをサイズが m のハッシュ表にハッシュする. 衝突はチェイン法で解消する. このとき, キー k のハッシュ先のリストの長さの期待値 E[ h(k) ] は 高々 α( キーが表に存在しないとき ) 高々 +α( キーが表に存在するとき ) 期待値の計算は全てハッシュ関数に関して行い, キーの分布については何も仮定しないことに注意 27

28 証明 : 異なるキーのペア k, l に対して, 指標確率変数 X kl 0 ( h( k) ( h( k) h( l)) h( l)) を定義する. ハッシュ関数の定義より, つのキーのペアが衝突を起こす確率は高々 /m. つまり Pr{h(k)=h(l)}/m よって E[X kl ] /m. キー k に対し,k 以外で k と同じスロットにハッシュされるキーの個数を確率変数 Y k で表す. Y k X kl lt lk 28

29 29 k T のとき従って k T のとき, キー k はリスト T[h(k)] に存在し, カウント Y k には k は含まれていないので従って k l T l k l T l kl k l T l kl k m X X Y E E E k l T l l Y k k h かつ ad : ) ( m Y k k h E E ) ( ad : ) ( k l T l l Y k k h かつ E E ) ( m Y k k h

30 万能ハッシュ関数族の設計 どんなキー k も 0 から p- までの範囲に入るような十分大きな素数 p を選ぶ.p > m を仮定. h a, b ( k) (( ak b)mod p) mod m と定義ただし a {,2,,p-}, b {0,,,,p-}. m は素数でなくてもいい. 定理 : ハッシュ関数のクラス H p, m a, b * p h : a Z, b は万能である. 証明 : 相異なるキー k, l Z p を考える. ハッシュ関数 h a,b に対し r = (ak+b) mod p 30 s = (al+b) mod p と置く. Z p

31 命題 :r s rs a(kl) (mod p) である. a も kl も法 p の下で 0 ではない. p は素数だから右辺の積も 0 ではない. (k,l) を固定する.p(p) 個存在するハッシュ関数のパラメタのペア (a,b) は, (k,l) を異なるペア (r,s) に写像する. r s であるペアは p(p) 個存在するので, (a,b) と (r,s) には 対 対応がある. a ( r s) ( k l) mod p mod b r akmod p (a,b) を一様ランダムに選べば, (r,s) も一様ランダム. p 3

32 従って, 相異なるキー k と l が衝突する確率は, 法 p の下で相異なる r と s をランダムに選択したときに r s (mod m) となる確率に等しい. r を固定すると,r 以外の p 個の値の中で r s (mod m) となる s の個数は高々 p p m p m m m よって,s と r が衝突する確率は高々 /m 従って, 任意の異なる値 k,l Z p のペアに対し h k h l a, b( ) a b( ) m Pr, つまり H p, m a, b * p h : a Z, b Z p は万能 32

33 線形時間のソーティング 今までのソートアルゴリズム 入力要素の比較のみに基づく 比較ソート (compariso sort) と呼ぶ 例 : マージソート, ヒープソート, クイックソート 計算量 :( lg ) この節でのソートアルゴリズム 比較以外の演算を用いる 例 : 計数ソート, 基数ソート, バケットソート 計算量 :O() ( 線形時間 ) 33

34 計数ソート (coutig sort) 個の各入力要素が から k の範囲の整数であると仮定 (k: ある整数 ) k = O() のとき, 計数ソートは O() 時間 基本的なアイデア 各入力要素 x に対し,x より小さい要素の数を決定 その要素数から x の出力配列での位置が決まる 例 : x より小さい数が 7 個 x の出力位置は 8 複数の要素が同じ値を持つ場合に対応する必要あり 34

35 計数ソートのプログラム A[..], B[..]: 入出力配列 C[..k]: 補助的な配列 void COUNTING_SORT(it *A, it *B, it *C, it, it k) { it i,j; for (i=; i<=k; i++) C[i] = 0; for (j=; j<=; j++) C[A[j]] = C[A[j]] + ; // C[i] は i に等しい要素の個数を含む for (i=2; i<=k; i++) C[i] = C[i] + C[i-]; // C[i] は i 以下の要素の個数を含む for (j=; j>=; j--) { B[C[A[j]]] = A[j]; C[A[j]] = C[A[j]] - ; } } 35

36 A C for (j=; j<=; j++) C[A[j]] = C[A[j]] + ; // C[i] は i に等しい要素の個数を含む C for (i=2; i<=k; i++) C[i] = C[i] + C[i-]; // C[i] は i 以下の要素の個数を含む B for (j=; j>=; j--) { B[C[A[j]]] = A[j]; // A[j] 以下が C[A[j]] 個 C[A[j]] = C[A[j]] - ; } 36

37 計数ソートの計算時間 C の初期化 : O(k) 時間 頻度の計算 : O() 時間 累積頻度の計算 : O(k) 時間 出力配列の計算 : O() 時間 全体で O(k + ) 時間 k = O() のとき, 全体で O() 時間 比較ソートの下限 ( lg ) を下回る 37

38 安定なソート 同一の値は入力と出力で同じ順序になる 付属データをキーに従ってソートする場合に重要 A B

39 基数ソート (radix sort) 数の集合をある桁に従って分割する機械がある この機械を用いて d 桁の数 個をソートしたい

40 まず最上位桁でソート ( 分割 ) し, それぞれを再帰的にソートすることを考える 大量の部分問題が生成される 解 : 最下位桁からソートする 基数ソート まず最下位桁に従ってソート 次に下から2 桁目に従ってソート d 桁目まで繰り返す 40

41 基数ソートでは各桁のソートは安定である必要がある 4

42 基数ソートの擬似コード RADIX_SORT(A,d). for (i=; i<=d; i++) 2. 安定ソートを用いて i 桁目に関して配列をソート 実行時間の解析 各桁が から k の範囲として計数ソートを使用 d パスあるので (d(+k)) 時間 d が定数で k = O() ならば, 全体で O() 時間 42

43 = 00 万個の 64 ビットの数をソートするとする 比較ソートでは つの数あたりほぼ lg = 20 回の操作が必要となる 基数ソートでは, これらの数を 4 桁の 2 6 進数と思うと,4 回のパスでソートできる 計数ソートを用いる基数ソートは i-place ではない メモリが高価な場合はクイックソートなどの方が良い 43

44 バケットソート (bucket sort) 入力 : [0,) の実数 個. 一様分布と仮定 アイデア 区間を 個の同じサイズの部分区間 ( バケット ) に分割 個の入力をバケットに分配 各バケットを独立にソート [0,.2) [.2,.4) [.4,.6) [.6,.8)[.8,.0) 44

45 バケットソートの動作 A[..]: 入力配列 B[0..]: バケット ( リストの配列 ) BUCKET_SORT(A,). for (i = ; i ; i++) 2. A[i] をリスト B[A[i]] に挿入する 3. for (i = 0; i ; i++) 4. リスト B[i] を挿入ソートでソートする 5. リスト B[0], B[],...,B[] を順に連接する 45

46 A B 各リストを挿入ソートでソート

47 アルゴリズムの正当性 A[i] と A[j] が同じバケットに入る場合 各バケットは挿入ソートでソートされるので OK A[i] と A[j] が異なるバケットに入る場合 バケット B[i ], B[j ] (i j ) に入るとする アルゴリズムの最後で B のリストは結合される B[i ] の要素は B[j ] の要素よりも前に現れる よって, 出力中で A[i] は A[j] よりも前に現れる つまり, A[i] A[j] を示せばよい 47

48 A[i] A[j] と仮定して矛盾を導く. i A[ i] A[ j] j となり,i j に矛盾する 48

49 実行時間の解析 挿入ソート以外の部分は O() 時間 N i : バケット B[i] に入れられる要素数を表す確率変数 バケット B[i] の要素をソートするのに必要な平均時間 = E[O(N i2 )] = O(E[N i2 ]) 全てのバケット中の要素をソートする時間は 2 2 O(E[ N i ]) O E[ Ni ] i0 i0 49

50 確率変数 N i の分布 要素数 = バケット数 = ある要素が B[i] に入る確率は p = / N i = k となる確率は2 項分布 B(k;,p) に従う E[N i ] = p =, Var[N i ] = p(p) = / E[N i2 ] = Var[N i ] + E 2 [N i ] = 2/ = () 以上より, 挿入ソートに必要な時間は O() バケットソートは線形時間で動作する 50

51 中央値と順序統計量 要素の集合の i 番目の順序統計量 (order statistic): その集合で i 番目に小さい要素 最小値 (miimum): i = 最大値 (maximum): i = 中央値 (media): が奇数のとき i = (+)/2 が偶数のとき i ( ) / 2 とi ( ) / 2 いずれの場合も i ( ) / 2 5

52 選択問題 (selectio problem) 入力 : 個の異なる数の集合 A, 整数 i ( i ) 出力 : A 中のちょうど i 個の他の要素より大きい要素 x A 選択問題は O( lg ) 時間で解ける A の要素をソートする 出力配列の i 番目の要素を返す 選択問題は O() 時間で解ける 52

53 最大と最小 要素の集合の最小値を決定するために必要な比較回数を考える 上限 : 回 data MINUMUM(it, data *A) { it i; data MIN; MIN = A[]; for (i=2; i<=; i++) { if (A[i] < MIN) MIN = A[i]; } retur MIN; } 53

54 比較回数の下限 命題 : 2 回の比較では最小値は決定できない 要素間のトーナメントによって最小値を決定する 回の比較はトーナメントの試合に相当する 値の小さいほうが試合に勝つ 最小値 ( 優勝者 ) が決まる それ以外が負ける 個が負けるには 試合必要 アルゴリズム MINIMUM は比較回数の点で最適 54

55 平均線形時間の選択法 順序統計量は () 時間で求まるが複雑 まず, 平均的に O() 時間のアルゴリズムを考える data RANDOMIZED_SELECT(data *A, it p, it r, it i) // A[p..r] の中で i 番目に小さい要素を返す { it q, k; if (p == r) retur A[p]; q = RANDOMIZED_PARTITION(A,p,r); // q: 分割の位置 k = q p + ; // k: 左部分の要素数 if (i <= k) retur RANDOMIZED_SELECT(A,p,q,i); else retur RANDOMIZED_SELECT(A,q+,r,ik); } 55

56 q = RANDOMIZED_PARTITION(A,p,r); の実行後 2つの空でない部分配列 A[p..q], A[q+..r] に分かれる 左側の各要素は右側よりも小さい k = q p + ; は左側の要素数 i k ならば i 番目の要素は左側の i 番目 i k ならば i 番目の要素は右側の i k 番目 部分配列のサイズが になるまで繰り返す 56

57 57 平均実行時間の上界 T(): 要素の集合での選択問題の平均時間 分割の左側のサイズが になる確率 = 2/ i になる確率 = / (i = 2,3,...,) T() は単調増加と仮定する ) O( 2 ) O( 2 ) O(, max max, 2 / 2 / k T k T T k k T T T k k k

58 58 RANDOMIZED_SELECT の最悪実行時間は ( 2 ) よって / T() = O() T() c と仮定すると d c c d c d c c d c d k k c d ck T k k k 2) / 4 / ( if / 2 /

59 最悪線形時間の 選択アルゴリズム アルゴリズム SELECT: i 番目に小さい要素を返す. 入力配列の 要素をグループに分割 5 要素のグループ /5 個 mod 5 要素のグループ高々 個 2. /5 個の各グループを ( 挿入ソート等で ) ソートし, それぞれの中央値を求める 3. SELECT を再帰的に用いてステップ 2 で求めた /5 個の値の中央値 x を求める 59

60 4. PARTITION を修正したものを用い, 入力配列を x によって分割する. 左側の要素数を k とする. 5. i k ならば, 左側で i 番目に小さい要素を再帰的に見つける. i k ならば, 右側で ik 番目に小さい要素を再帰的に見つける. 60

61 SELECT の実行時間の解析 分割に用いた x より大きい要素数の下界を求める ステップ 2 で求めた中央値の少なくとも半分は x ( 中央値の中央値 ) 以上 中央値が x 以上のグループには,x 以上の値が 3 個以上ある x 以上となる要素数は少なくとも

62 同様に,x 以下となる要素数も少なくとも 3/06 ステップ 5 で再帰的に呼ばれる SELECT の部分問題のサイズは高々 7/0+6 ステップ,4: O() 時間 ステップ 2: 5 要素のソートを /5 回 O() 時間 ステップ 3: T(/5) 時間 T( ) T / 5 T7 /0 6 O () 80のとき 80のとき 62

63 80 に対して T() c と仮定する. c を十分大きくとれば T ( ) c / 5 c7 /0 6 O / 5 7c /0 6c O c /0 7c O c 9 c よって,SELECTの最悪実行時間は線形 これは比較しか用いていない 63