N i - Researchmap

算法数理工学
第6回
定兼邦彦
1
万能ハッシュ法
• 運が悪いと，n 個のキーが同じスロットにハッシュさ
れ，平均検索時間が (n) になってしまう
• 万能ハッシュ法 (universal hashing) では，ハッシュ
関数をランダムに選択する
• どのように意地悪くキーを選択しても，平均として
良い性能を示す．
2
• 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} からラ
ンダムに選択されたときの衝突確率に等しい
3
定理 h を万能な集合から選択されたハッシュ関数と
する．h を用いて n 個のキーをサイズが m のハッ
シュ表にハッシュする. 衝突はチェイン法で解消す
る．このとき，キー k のハッシュ先のリストの長さの
期待値 E[nh(k)] は
高々α（キーが表に存在しないとき）
高々1+α（キーが表に存在するとき）
期待値の計算は全てハッシュ関数に関して行い，
キーの分布については何も仮定しないことに注意
4
証明:異なるキーのペア k, l に対して，指標確率変数
1 (h(k )  h(l ))
X kl  
を定義する．
0 (h(k )  h(l ))
ハッシュ関数の定義より，1つのキーのペアが衝突を
起こす確率は高々 1/m．つまり Pr{h(k)=h(l)}1/m
よって E[Xkl]  1/m.
キー k に対し，k 以外で k と同じスロットにハッシュさ
れるキーの個数を確率変数 Yk で表す．
Yk   X kl
lT
l k
5


1


EYk   E  X kl   EX kl   
 lT
 lT
lT m
 l  k
 l  k
l k
かつ l : l T and l  k　n
• k  T のとき nh( k )  Yk 従って En   EY   n  
h(k )
k
m
• k  T のとき, キー k はリスト T[h(k)] に存在し，
カウント Yk には k は含まれていないので
nh( k )  Yk  1　かつ l : l T and l  k　 n 1
従って Enh ( k ) 
n 1
 EYk  1 
1  1 
m
6
万能ハッシュ関数族の設計
• どんなキー k も 0 から p-1 までの範囲に入るような
十分大きな素数 p を選ぶ．p > m を仮定．
• ha ,b (k )  (( ak  b) mod p ) mod m と定義
ただし a  {1,2,…,p-1}, b  {0,1,,…,p-1}．
m は素数でなくてもいい．
• 定理: ハッシュ関数のクラス
*
H p,m  ha,b : a  Z p , b  Z p は万能である．
• 証明：相異なるキー k, l  Zp を考える．ハッシュ関
数 ha,b に対し
r = (ak+b) mod p
7
s = (al+b) mod p
と置く．


• 命題：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対応がある．
1



a  (r  s) (k  l ) mod p mod p
b  r  ak  mod p
• (a,b) を一様ランダムに選べば， (r,s) も一様ランダ
ム．
8
• 従って，相異なるキー k と l が衝突する確率は，
法 p の下で相異なる r と s をランダムに選択したと
きに r  s (mod m) となる確率に等しい．
• r を固定すると，r 以外の p1 個の値の中で
r  s (mod m) となる s の個数は高々
p  m 1
p 1
 p
1 
 m   1 
m
m
• よって，s と r が衝突する確率は高々 1/m
• 従って，任意の異なる値 k,l Zp のペアに対し
1
Prha ,b (k )  ha ,b (l ) 
m

つまり H p,m  ha,b : a  Z *p , b  Z p

は万能
9
線形時間のソーティング
• 今までのソートアルゴリズム
–
–
–
–
入力要素の比較のみに基づく
比較ソート (comparison sort) と呼ぶ
例：マージソート，ヒープソート，クイックソート
計算量：(n lg n)
• この節でのソートアルゴリズム
– 比較以外の演算を用いる
– 例：計数ソート，基数ソート，バケットソート
– 計算量：O(n) (線形時間)
10
計数ソート (counting sort)
• n 個の各入力要素が 1 から k の範囲の整数で
あると仮定 (k: ある整数)
• k = O(n) のとき，計数ソートは O(n) 時間
• 基本的なアイデア
–
–
–
–
各入力要素 x に対し，x より小さい要素の数を決定
その要素数から x の出力配列での位置が決まる
例： x より小さい数が17個 ⇒ x の出力位置は18
複数の要素が同じ値を持つ場合に対応する必要あり
11
計数ソートのプログラム
• 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;
}
}
12
1 2 3 4 5 6 7 8
A 3 6 4 1 3 4 1 4
1 2 3 4 5 6
C 2 0 2 3 0 1
1 2 3 4 5 6
C 120 2 423 7546 7 87
1 2 3 4 5 6 7 8
B 1 1 3 3 4 4 4 6
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]; // A[j]以下がC[A[j]]個
C[A[j]] = C[A[j]] - 1;
}
13
計数ソートの計算時間
•
•
•
•
C の初期化: O(k) 時間
頻度の計算: O(n) 時間
累積頻度の計算: O(k) 時間
出力配列の計算: O(n) 時間
• 全体で O(k + n) 時間
• k = O(n) のとき，全体で O(n) 時間
• 比較ソートの下限 (n lg n) を下回る
14
安定なソート
• 同一の値は入力と出力で同じ順序になる
• 付属データをキーに従ってソートする場合に重要
1 2 3 4 5 6 7 8
A 3 6 4 1 3 4 1 4
B 1 1 3 3 4 4 4 6
15
基数ソート (radix sort)
• 数の集合をある桁に従って分割する機械がある
• この機械を用いて d 桁の数 n 個をソートしたい
329
457
657
839
436
720
355
329
355
457
436
657
720
839
16
• まず最上位桁でソート (分割) し，それぞれを
再帰的にソートすることを考える
• 大量の部分問題が生成される
• 解：最下位桁からソートする⇒基数ソート
– まず最下位桁に従ってソート
– 次に下から2桁目に従ってソート
– d 桁目まで繰り返す
17
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
基数ソートでは各桁のソートは安定である必要がある
18
基数ソートの擬似コード
RADIX_SORT(A,d)
1. for (i=1; i<=d; i++)
2. 安定ソートを用いて i 桁目に関して配列をソート
実行時間の解析
• 各桁が 1 から k の範囲として計数ソートを使用
• d パスあるので (d(n+k)) 時間
• d が定数で k = O(n) ならば，全体で O(n) 時間
19
• n = 100万個の64ビットの数をソートするとする
• 比較ソートでは1つの数あたりほぼ lg n = 20 回の
操作が必要となる
• 基数ソートでは，これらの数を4桁の216進数と思う
と，4回のパスでソートできる
• 計数ソートを用いる基数ソートはin-placeではない
– メモリが高価な場合はクイックソートなどの方が良い
20
バケットソート (bucket sort)
• 入力： [0,1) の実数 n 個．一様分布と仮定
• アイデア
– 区間を n 個の同じサイズの部分区間 (バケット) に分割
– n 個の入力をバケットに分配
– 各バケットを独立にソート
0.15
0.51 0.45 0.75 0.80
[0,.2) [.2,.4) [.4,.6) [.6,.8) [.8,1.0)
21
バケットソートの動作
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] を順に連接する
22
1
2
3
4
5
6
7
8
9
10
A
.78
.17
.39
.26
.72
.94
.21
.12
.23
.68
.12
B
0
1
2
3
.12
.17
.21
.26
.23
.39
.17
.23
.26
.21
.26
4
5
6
7
.68
.72
.78
.78
8
9
.94
.17 各リストを挿入ソートでソート
.21
.23
.26
.39
.68
.72
.78
.94
23
アルゴリズムの正当性
• 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] を示せばよい
24
• A[i]  A[j] と仮定して矛盾を導く．
i  nA[i ]
 nA[ j ]
 j
• となり，i’ j’ に矛盾する
25
実行時間の解析
• 挿入ソート以外の部分は O(n) 時間
• Ni: バケット B[i] に入れられる要素数を表す
確率変数
• バケット B[i] の要素をソートするのに必要な
平均時間 = E[O(Ni2)] = O(E[Ni2])
• 全てのバケット中の要素をソートする時間は
n 1
n 1

2
2 
O(E[ N i ])  O  E[ N i ] 

i 0
 i 0

26
中央値と順序統計量
• n 要素の集合の i 番目の順序統計量 (order
statistic): その集合で i 番目に小さい要素
• 最小値 (minimum): i = 1
• 最大値 (maximum): i = n
• 中央値 (median):
– n が奇数のとき i = (n+1)/2
– n が偶数のとき i  (n  1) / 2とi  (n  1) / 2
– いずれの場合も i  (n  1) / 2
27
選択問題 (selection problem)
• 入力: n 個の異なる数の集合 A, 整数 i (1  i  n)
• 出力: A 中のちょうど i 1 個の他の要素より大きい
要素 x  A
• 選択問題は O(n lg n) 時間で解ける
– A の要素をソートする
– 出力配列の i 番目の要素を返す
• 選択問題は O(n) 時間で解ける
28
最大と最小
• 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;
}
29
比較回数の下限
命題: n2 回の比較では最小値は決定できない
• 要素間のトーナメントによって最小値を決定する
• 1回の比較はトーナメントの試合に相当する
• 値の小さいほうが試合に勝つ
• 最小値 (優勝者) が決まる⇔それ以外が負ける
• n1 個が負けるには n1 試合必要
アルゴリズムMINIMUMは比較回数の点で最適
30
平均線形時間の選択法
• 順序統計量は (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);
31
}
• 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 になるまで繰り返す
32
平均実行時間の上界
• T(n): n 要素の集合での選択問題の平均時間
• 分割の左側のサイズが
– 1 になる確率 = 2/n
– i になる確率 = 1/n (i = 2,3,...,n1)
• T(n) は単調増加と仮定する
n 1
1

T n    T max 1, n  1   T max k , n  k   O(n)
n
k 1

n 1

1
  T n  1  2  T k   O(n)
n
k  n / 2 

2 n 1

T k   O(n)

n k  n / 2 
33
• RANDOMIZED_SELECTの最悪実行時間は(n2)
よって 1/n T(n1) = O(n)
• T(n)  cn と仮定すると
2 n 1
T n  
 ck  dn
n k  n / 2 
n / 2 1 
2c  n 1
   k   k   dn
n  k 1
k 1 
2c  1
1   n   n  
  n  1n      1     dn
n 2
2   2   2  
cn n
 cn  1    1  dn
n2 2
1
3
 c n    dn
2
4
if c(n / 4  1 / 2)  dn 
 cn
34
最悪線形時間の
選択アルゴリズム
アルゴリズム SELECT: i 番目に小さい要素を返す
1. 入力配列の n 要素をグループに分割
–
–
5要素のグループ n/5 個
n mod 5 要素のグループ高々1個
2. n/5 個の各グループを(挿入ソート等で)ソートし
，それぞれの中央値を求める
3. SELECTを再帰的に用いてステップ2で求めた
n/5 個の値の中央値 x を求める
35
4. PARTITIONを修正したものを用い，入力配列を
x によって分割する．左側の要素数を k とする.
5. i  k ならば，左側で i 番目に小さい要素を再帰
的に見つける．
i  k ならば，右側で ik 番目に小さい要素を再帰
的に見つける．
36
SELECTの実行時間の解析
• 分割に用いた x より大きい要素数の下界を求める
• ステップ 2 で求めた中央値の少なくとも半分は x (
中央値の中央値) 以上
• 中央値が x 以上のグループには，x 以上の値が 3
個以上ある
• x 以上となる要素数は少なくとも
  1  n    3n
3      2  
6
  2  5    10
37
• 同様に，x 以下となる要素数も少なくとも 3n/106
• ステップ 5 で再帰的に呼ばれる SELECT の部分
問題のサイズは高々 7n/10+6
• ステップ 1,4: O(n) 時間
• ステップ 2: 5 要素のソートを n/5 回⇒ O(n)時間
• ステップ 3: T(n/5) 時間
(1)
n  80のとき

T ( n)  
T n / 5  T 7n / 10  6  On  n  80のとき
38
• n  80 に対して T(n)  cn と仮定する.
c を十分大きくとれば
T (n)  c n / 5  c7n / 10  6  On 
 cn / 5  7cn / 10  6c  On 
 9cn / 10  7c  On 
 cn
• よって，SELECTの最悪実行時間は線形
• これは比較しか用いていない
39

Download Report