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

算法数理工学

第5回

定兼 邦彦

ハッシュ表

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

3

チェイン法を用いるハッシュ法の解析

• SEARCHは最悪の場合 (n) 時間 • 平均時間を解析する • スロット m 個, n 要素を格納するハッシュ表 T の 負荷率 (load factor)



= n/m と定義 •



は1つのチェインに格納される要素数の平均 • 解析は



を変数として行う (n, m が共に無限大 に近づくとき，



_{はある定数に留まるとする)}

ハッシュ法の平均的性能

• 各要素は m 個のスロットに同じ程度にハッシュさ れると仮定する (単純一様ハッシュの仮定

simple uniform hashing)

• ハッシュ値 h(k) は O(1) 時間で計算できると仮定 • キー k をもつ要素の探索は，リスト T[h(k)] の長

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



₎ 定理2 チェイン法を用いるハッシュ表で，単純一様 ハッシュを仮定すると，成功する探索にかかる時間の 平均は (1+



)

ハッシュ関数

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



 m j m k P j k h k 

7

除算法

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

例

• n = 2000 個の文字列を格納する場合 • 負荷率



を 3 に近くするには, m = 701 にすれ ばいい • 701 は素数で，2のべき乗には近くない • h(k) = k mod 701 とすればいい • このハッシュ関数が実際のデータでうまく働くこ とを確かめるべき

9

乗算法

• まず，キー k にある定数 A (0 < A < 1) を掛け，そ の小数部分 kAkA を取り出す • 次に，その値に m を掛け，小数部分を切り捨てる • m の値はあまり重要ではない – 2のべき乗にすると計算が簡単 • が良いと言われる

 







m

kA

kA



k

h

(

)







5 1



/ 2  0.6180339887  A

オープンアドレス指定法

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

11

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

要素の挿入

int HASH_SEARCH(data *T, data k) { int i, j; i = 0; // i: 探査番号 do { j = h(k,i); if (T[j] = k) return j; // k を発見 i++;

} while (T[j] != NIL && i != m); // スロットが空か，m 回探索した return NIL; // k は見つからなかった

}

13

要素の削除

• 削除したい要素のあるスロットを NIL にすると，他 の要素が検索できなくなる – NIL スロットが見つかると検索は終了するため • 削除するときは NIL でなく特別な値 DELETED を 格納する • SEARCHではDELETEDが現れても探索を続ける • INSERTではNILまたはDELETEDの場所に挿入 • 問題点: 探索時間が負荷率



で表せない • 要素を削除する必要がある場合はチェイン法が好 まれる

衝突回避の方法

• 一様ハッシュ (uniform hashing) を仮定: 各キ ーに対する探査列として， {0,1,...,m1} の m! 通りの順列のどれもが同程度に現れる • 近似的な一様ハッシュを用いる – 線形探査 – 2次関数探査 – ダブルハッシュ法

15

線形探査

• 通常のハッシュ関数 h’: U  {0,1,...,m1} に対し

h(k,i) = (h’(k)+i) mod m (i=0,1,...,m1) を用いる

• 探査されるスロット: T[h’(k)], T[h’(k)+1],..., T[m1], T[0], T[1],..., T[h’(k)1] • 異なる探査列は m 通りしかない (開始位置で決定) • 問題点: 主クラスタ化 (primary clustering) が起きる • 直前の i 個のスロットが使用中である空きスロット が選択される確率は (i+1)/m であるため，連続す る使用中のスロットは常に大きくなる

2次関数探査

• 2次関数探査 (quadratic probing) では h(k,i) = (h’(k)+c₁i+c₂i2) mod m (i=0,1,...,m1) を用いる

• c₁, c₂, m は適切に選ぶ必要がある

• h(k₁,0) = h(k₂,0) の場合は h(k₁,i) = h(k₂,i) となって しまう (副クラスタ化, secondary clustering)

17

ダブルハッシュ法

• h(k,i) = (h₁(k)+i h₂(k)) mod m

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

オープンアドレスハッシュ法の解析

• ハッシュ表の負荷率



をパラメータとして解析 • 一様ハッシュを用いると仮定する 定理 負荷率



_{=n/m<1 のオープンアドレスハッシュ} 表において，失敗に終わる探索に必要な探査数の 期待値は 1/(1



) 以下 証明 失敗に終わる探索では，最後の探査を除いて， 毎回の探査では異なるキーを格納しているスロット にアクセスし，最後に未使用のスロットにアクセス

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





   







1 0

1

1

i i i i

q

ip

m

n

q 

₁

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

1

1

2









m

n

m

n

q

i i i

m

n

i

m

i

n

m

n

m

n

q







































1

1

1

1



21 失敗に終わる探索に必要な探査回数の期待値は



が定数なら O(1) 時間で実行できる



= 0.5 なら 2回 以下



= 0.9 なら 10回 以下

































   

1

1

1

1

1

3 2 1 0



i i i i

q

ip

系 一様ハッシュを仮定すると，負荷率



のオープン アドレスハッシュ表に，ある要素を挿入するために 必要な探査回数の平均は1/(1



) 以下 証明 キーを挿入するには未使用スロットを発見する 必要がある．その探査回数の期待値は失敗に終 わる探索での探査回数の期待値に等しい．

23 定理 一様ハッシュを仮定し，表内の各キーは等確率 で探索の対象になるとする．負荷率



のオープン アドレスハッシュ表において，成功に至る探索に必 要な探査回数の期待値は 証明 キー k の探索は，それを挿入したときと同じ探 査列を探査する．系より，k がハッシュ表に i+1 番 目に挿入されたキーならば，探索に必要な探査回 数の期待値は 1/(1i/m) = m/(mi)以下







1

1

1

ln

1





ハッシュ表に存在する n 個のキーについて平均を 取ると，成功に至る探索に必要な探査回数の平 均が得られる．



=0.5 のとき 3.387回 以下









     1 1 1 ln 1 ) ln( 1 ln 1 1 1 1 1 0 1 0                 





n m m H H i m n m i m m n n m m n i n i

25

万能ハッシュ法

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

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

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

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



   k l T l kl k X Y

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 1 E



l l T l k



n Y n_h(k)  _k　　かつ :  and  　

 



 

   m n Y n_{h k} E _k E _{( )}



: and



1 1 ) (  Y  l l T l  k  n  n_{h k k} 　　かつ 　

 

 E



1



 1 11 E _{( )} m n Y n_{h k k}

万能ハッシュ関数族の設計

• どんなキー k も 0 から p-1 までの範囲に入るような 十分大きな素数 p を選ぶ．p > m を仮定． • と定義 ただし a  {1,2,…,p-1}, b  {0,1,,…,p-1}． m は素数でなくてもいい． • 定理: ハッシュ関数のクラス は万能である． • 証明：相異なるキー k, l  Z_p を考える．ハッシュ関 数 h_a,b に対し r = (ak+b) mod p

m

p

b

ak

k

h

_a,b

(

)



((



)

mod

)

mod



a b p p



m p

h

a

Z

b

Z

H

_,



_,

:



*

,



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









r ak p b p p l k s r a mod mod mod ) ( ) ( 1      

• 従って，相異なるキー k と l が衝突する確率は， 法 p の下で相異なる r と s をランダムに選択したと きに r  s (mod m) となる確率に等しい． • r を固定すると，r 以外の p1 個の値の中で r  s (mod m) となる s の個数は高々 • よって，s と r が衝突する確率は高々 1/m • 従って，任意の異なる値 k,l Z_p のペアに対し つまり は万能 m p m m p m p 1 1 1 1          





m l h k h_{a b}( ) _{a b}( ) 1 Pr _,  _, 



h

a

Z

b

Z



H



:



*

,



33

線形時間のソーティング

• 今までのソートアルゴリズム – 入力要素の比較のみに基づく – 比較ソート (comparison sort) と呼ぶ – 例：マージソート，ヒープソート，クイックソート – 計算量：(n lg n) • この節でのソートアルゴリズム – 比較以外の演算を用いる – 例：計数ソート，基数ソート，バケットソート – 計算量：O(n) (線形時間)

計数ソート (counting sort)

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

35

計数ソートのプログラム

• A[1..n], B[1..n]: 入出力配列 • C[1..k]: 補助的な配列

void COUNTING_SORT(int *A, int *B, int *C, int n, int k) {

int i,j;

for (i=1; i<=k; i++) C[i] = 0;

for (j=1; j<=n; j++) C[A[j]] = C[A[j]] + 1; // C[i] は i に等しい要素の個数を含む

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

3 6 4 1 3 4 1 4 1 2 3 4 5 6 7 8 A 2 0 2 3 0 1 1 2 3 4 5 6 C

for (j=1; j<=n; j++) C[A[j]] = C[A[j]] + 1; // C[i] は i に等しい要素の個数を含む

for (i=2; i<=k; i++) C[i] = C[i] + C[i-1]; // C[i] は i 以下の要素の個数を含む 2 2 4 7 7 8

1 2 3 4 5 6

C

for (j=n; j>=1; j--) {

B[C[A[j]]] = A[j]; // A[j]以下がC[A[j]]個 C[A[j]] = C[A[j]] - 1; 1 2 3 4 5 6 7 8 B 4 6 4 5 1 1 3 3 1 0 4 4 6 7 3 2

37

計数ソートの計算時間

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

安定なソート

• 同一の値は入力と出力で同じ順序になる • 付属データをキーに従ってソートする場合に重要 A B _{1 1} 3 ₃ 4 4 4 6 1 2 3 4 5 6 7 8 1 4 6 1 3 4 3 4

39

基数ソート (radix sort)

• 数の集合をある桁に従って分割する機械がある • この機械を用いて d 桁の数 n 個をソートしたい 329 457 657 839 436 720 355 329 355 457 436 657 720 839

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

41

329

457

657

839

436

720

355

720

355

436

457

657

329

839

720

329

436

839

355

457

657

329

355

436

457

657

720

839

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

基数ソートの擬似コード

RADIX_SORT(A,d) 1. for (i=1; i<=d; i++)

2. 安定ソートを用いて i 桁目に関して配列をソート

実行時間の解析

• 各桁が 1 から k の範囲として計数ソートを使用

• d パスあるので (d(n+k)) 時間

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

バケットソート (bucket sort)

• 入力： [0,1) の実数 n 個．一様分布と仮定 • アイデア – 区間を n 個の同じサイズの部分区間 (バケット) に分割 – n 個の入力をバケットに分配 – 各バケットを独立にソート 0.15 0.51 0.45 0.75 0.80

45

バケットソートの動作

A[1..n]: 入力配列 B[0..n1]: バケット (リストの配列) BUCKET_SORT(A,n) 1. for (i = 1; i  n; i++) 2. A[i] をリスト B[nA[i]] に挿入する 3. for (i = 0; i  n



1; i++) 4. リスト B[i] を挿入ソートでソートする 5. リスト B[0], B[1],...,B[n1] を順に連接する

.78 .26 .17 .39 .72 .94 .21 .12 .23 .68 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 0 A B .78 .17 .39 .26 .78 .72 .94 .26 .21 .17 .12 .26 .21 .23 .68 各リストを挿入ソートでソート .26 .23 .21 .12 .17 .21 .23 .26

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] を示せばよい

• A[i]  A[j] と仮定して矛盾を導く． • となり，i’ j’ に矛盾する









j j nA i nA i      ] [ ] [

49

実行時間の解析

• 挿入ソート以外の部分は O(n) 時間 • N_i: バケット B[i] に入れられる要素数を表す 確率変数 • バケット B[i] の要素をソートするのに必要な 平均時間 = E[O(N_i2_{)] = O(E[N} i2]) • 全てのバケット中の要素をソートする時間は       





    1 0 2 1 0 2 ] [ E O ]) [ E ( O n i i n i i N N

確率変数 N

_i

の分布

• 要素数 = バケット数 = n • ある要素が B[i] に入る確率は p = 1/n • N_i = k となる確率は2項分布 B(k;n,p) に従う • E[N_i] = np = 1, Var[N_i] = np(1p) = 11/n • E[N_i2_{] = Var[N} i] + E2[Ni] = 21/n = (1) 以上より，挿入ソートに必要な時間は O(n) バケットソートは線形時間で動作する

51

中央値と順序統計量

• n 要素の集合の i 番目の順序統計量 (order statistic): その集合で i 番目に小さい要素 • 最小値 (minimum): i = 1 • 最大値 (maximum): i = n • 中央値 (median): – n が奇数のとき i = (n+1)/2 – n が偶数のとき – いずれの場合も ( 1)/ 2  ( 1)/ 2  n i n i と ( 1)/ 2  n i

選択問題 (selection problem)

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

53

最大と最小

• n 要素の集合の最小値を決定するために 必要な比較回数を考える

• 上限： n1 回

data MINUMUM(int n, data *A) {

int i;

data MIN; MIN = A[1];

for (i=2; i<=n; i++) {

if (A[i] < MIN) MIN = A[i]; }

return MIN; }

比較回数の下限

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

55

平均線形時間の選択法

• 順序統計量は (n) 時間で求まるが複雑

• まず，平均的に O(n) 時間のアルゴリズムを考える

data RANDOMIZED_SELECT(data *A, int p, int r, int i) // A[p..r] の中で i 番目に小さい要素を返す { int q, k; if (p == r) return A[p]; q = RANDOMIZED_PARTITION(A,p,r); // q: 分割の位置 k = q – p + 1; // k: 左部分の要素数 if (i <= k) return RANDOMIZED_SELECT(A,p,q,i);

else return RANDOMIZED_SELECT(A,q+1,r,ik); }

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

57

平均実行時間の上界

• T(n): n 要素の集合での選択問題の平均時間 • 分割の左側のサイズが – 1 になる確率 = 2/n – i になる確率 = 1/n (i = 2,3,...,n1) • T(n) は単調増加と仮定する

 





















 

 

 

  ) ( O 2 ) ( O 2 1 1 ) ( O , max 1 , 1 max 1 1 2 / 1 2 / 1 1 n k T n n k T n T n n k n k T n T n n T n n k n n k n k                    _{  } 







     

• RANDOMIZED_SELECTの最悪実行時間は(n2₎ よって 1/n T(n



1) = O(n) • T(n)  cn と仮定すると

 

   









dn n c dn n n n c n c dn n n n n n c dn k k n c dn ck n n T n k n k n n k        _                              _                  







      2 1 4 3 2 1 2 1 2 1 2 2 1 1 2 1 2 2 2 1 2 / 1 1 1 1 2 /

59

最悪線形時間の

選択アルゴリズム

アルゴリズム SELECT: i 番目に小さい要素を返す 1. 入力配列の n 要素をグループに分割 – 5要素のグループ n/5 個 – n mod 5 要素のグループ 高々1個 2. n/5 個の各グループを(挿入ソート等で)ソートし ，それぞれの中央値を求める 3. SELECTを再帰的に用いてステップ2で求めた n/5 個の値の中央値 x を求める

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

61

SELECTの実行時間の解析

• 分割に用いた x より大きい要素数の下界を求める • ステップ 2 で求めた中央値の少なくとも半分は x ( 中央値の中央値) 以上 • 中央値が x 以上のグループには，x 以上の値が 3 個以上ある • x 以上となる要素数は少なくとも 6 10 3 2 5 2 1 3 _                  n n

• 同様に，x 以下となる要素数も少なくとも 3n/106 • ステップ 5 で再帰的に呼ばれる SELECT の部分 問題のサイズは高々 7n/10+6 • ステップ 1,4: O(n) 時間 • ステップ 2: 5 要素のソートを n/5 回⇒ O(n)時間 • ステップ 3: T(n/5) 時間







 

  

          のとき のとき 80 O 6 10 / 7 5 / 80 ) 1 ( ) ( n n n T n T n n T

63 • n  80 に対して T(n)  cn と仮定する. c を十分大きくとれば • よって，SELECTの最悪実行時間は線形 • これは比較しか用いていない







  

 

 

cn n c cn n c cn cn n n c n c n T             O 7 10 / 9 O 6 10 / 7 5 / O 6 10 / 7 5 / ) (