x - Researchmap

情報工学概論
(アルゴリズムとデータ構造)
第8回
オープンアドレスハッシュ法の解析
• ハッシュ表の負荷率  をパラメータとして解析
• 一様ハッシュを用いると仮定する
定理 11.6 負荷率  =n/m<1 のオープンアドレスハッ
シュ表において，失敗に終わる探索に必要な探査
数の期待値は 1/(1) 以下
証明失敗に終わる探索では，最後の探査を除いて，
毎回の探査では異なるキーを格納しているスロット
にアクセスし，最後に未使用のスロットにアクセス
する．
2
i = 0,1,... に対して，
pi = Pr{未使用のスロットを見つけるまでちょうど i 回
の探査を行った}
qi = Pr{未使用のスロットを見つけるまで少なくとも
i 回の探査を行った}
と定義する．探査回数の期待値は


i 0
i 1
1   ipi  1   qi
最初の探査が使用中のスロットにアクセスする確率
は n/m であるから
n
q1 
m
3
一様ハッシュ法では，2回目の探査は残りの m1
個のスロットの1つに対して行われ，その中には
n1 個の使用中のスロットがあるため
n n 1
q2  
m m 1
n
n

1
n

i

1
一般に qi  
 
m m 1
m  i 1
n
 
m
i

i
4
失敗に終わる探索に必要な探査回数の期待値は


i 0
i 1
1   ipi  1   qi
 1      
2
3
1

1
が定数なら O(1) 時間で実行できる
 = 0.5 なら 2回以下
 = 0.9 なら 10回以下
5
系12.6 一様ハッシュを仮定すると，負荷率のオー
プンアドレスハッシュ表に，ある要素を挿入するた
めに必要な探査回数の平均は1/(1) 以下
証明キーを挿入するには未使用スロットを発見する
必要がある．その探査回数の期待値は失敗に終
わる探索での探査回数の期待値に等しい．
6
定理 12.7 一様ハッシュを仮定し，表内の各キーは
等確率で探索の対象になるとする．負荷率  の
オープンアドレスハッシュ表において，成功に至る
探索に必要な探査回数の期待値は
1
1
1
ln

 1 
証明キー k の探索は，それを挿入したときと同じ探
査列を探査する．系12.6 より，k がハッシュ表に
i+1 番目に挿入されたキーならば，探索に必要な
探査回数の期待値は 1/(1i/m) = m/(mi)以下
7
ハッシュ表に存在する n 個のキーについて平均を
取ると，成功に至る探索に必要な探査回数の平
均が得られる．
1 n 1 m
m n 1 1
 

n i 0 m  i n i 0 m  i
1
 H m  H m  n 


1

ln m  1  ln( m  n) 
1
1
1
 ln

 1 
=0.5 のとき 3.387回以下
=0.9 のとき 3.670回以下
8
11.3.3 万能ハッシュ法
• 運が悪いと，n 個のキーが同じスロットにハッシュさ
れ，平均検索時間が (n) になってしまう
• 万能ハッシュ法 (universal hashing) では，ハッ
シュ関数をランダムに選択する
• どのように意地悪くキーを選択しても，平均として
良い性能を示す．
9
• 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} からラ
ンダムに選択されたときの衝突確率に等しい
10
定理 11.3 h を万能な集合から選択されたハッシュ関
数とする．h を用いて n 個のキーをサイズが m の
ハッシュ表にハッシュする. 衝突はチェイン法で解
消する．このとき，キー k のハッシュ先のリストの長
さの期待値 E[nh(k)] は
高々α（キーが表に存在しないとき）
高々1+α（キーが表に存在するとき）
期待値の計算は全てハッシュ関数に関して行い，
キーの分布については何も仮定しないことに注意
11
証明:異なるキーのペア 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
12


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
13
万能ハッシュ関数族の設計
• どんなキー 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 は素数でなくてもいい．
• 定理11.5: ハッシュ関数のクラス
*
H p,m  ha,b : a  Z p , b  Z p は万能である．
• 証明：相異なるキー k, l  Zp を考える．ハッシュ関
数 ha,b に対し
r = (ak+b) mod p
14
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)
に写像する．



a  (r  s) (k  l ) 1 mod p mod p
b  r  ak  mod p
• r  s であるペアは p(p1) 個存在するので， (a,b)
と (r,s) には1対1対応がある．
• (a,b) を一様ランダムに選べば， (r,s) も一様ランダ
ム．
15
• 従って，相異なるキー 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

は万能
16
乱数発生法
• {0, 1, …, p1} の整数を一様ランダムに生成
– C言語
int x;
x = rand() % p; // 整数乱数を p で割った余り
– Fortran
real r
integer x
call RANDOM_NUMBER(r) ! 0 <= r < 1 の実数乱数
x = INT(r * p)
17
乱数の種の設定
• 現在時刻を乱数の種にする
• C言語
srand((int)clock());
srand((int)time(NULL));
• Fortran
call random_seed()
18
12. 2分探索木
• 探索木: SEARCH, MINIMUM, MAXIMUM,
PREDECESSOR, SUCCESSOR, INSERT,
DELETE等が利用できる動的集合用データ構造
• 辞書やプライオリティーキューとして利用できる
• 基本操作は木の高さに比例した時間がかかる
– ランダムに構成された2分探索木の高さ: O(lg n)
– 最悪時: O(n)
• 最悪時でも O(lg n) に改良できる (2色木)
19
12.1 2分探索木とは何か?
• 各節点は key, left, right, p フィールドを持つ
• 2分探索木条件 (binary-search-tree property)
– 節点 y が x の左部分木に属する⇒ key[y]key[x]
– 節点 y が x の右部分木に属する⇒ key[x]key[y]
2
3
5
7
3
2
7
5
5
8
5
8
20
木の中間順巡回
• 木の中間順巡回 (通りがけ順, inorder tree walk
– 根の左部分木に出現するキー集合
– 根のキー
– 右部分木に出現するキー集合の順にキーを出力
• 木の根から辿ると，全てのキーをソートされた順
序で出力できる
5
• (n) 時間
INORDER_TREE_WALK(node x)
{
if (x != NIL) {
INORDER_TREE_WALK(left(x));
print(key(x));
INORDER_TREE_WALK(right(x));
}
}
3
2
3
2
5
5
5
7
7
8
8 21
その他の巡回法
• 先行順巡回 (行きがけ順, preorder tree walk):
根節点を先に出力し，次に左右の部分木を出力
• 後行順巡回 (帰りがけ順, postorder tree walk):
先に左右の部分木を出力し，最後に根節点を出力
POSTORDER_TREE_WALK(node x)
PREORDER_TREE_WALK(node x)
{
{
if (x != NIL) {
if (x != NIL) {
POSTORDER_TREE_WALK(left(x));
print(key(x));
POSTORDER_TREE_WALK(right(x));
PREORDER_TREE_WALK(left(x));
PREORDER_TREE_WALK(right(x)); print(key(x));
}
}
}
}
22
12.2 2分探索木に対する質問操作
• 質問操作は高さに比例した時間で終了する
• 探索: 2分探索木の中から，ある与えられたキーを
持つ節点のポインタを求める(存在しなければNIL)
TREE_SEARCH(node x, data k)
{
if (x == NIL || k == key(x)) return x;
if (k < key(x)) return TREE_SEARCH(left(x),k);
else return TREE_SEARCH(right(x),k);
}
23
探索の正当性
• キー k が見つかったら探索を終了する
• k が key(x) より小さい場合
– 2分探索木条件より，k は x の右部分木にはない
– 左部分木に対して探索を続行する
• k が key(x) より大きい場合
– 右部分木に対して探索を続行する
• 探索する節点は根からのパスになる
– 実行時間は O(h) (h: 木の高さ)
24
• 再帰はwhileループにすることができる
ITERATIVE_TREE_SEARCH(node x, data k)
{
while (x != NIL && k != key(x)) {
if (k < key(x)) x = left(x);
else x = right(x);
}
return x;
}
25
最小値と最大値
• 最小/最大のキーを持つ要素のポインタを
返す
• O(h) 時間
TREE_MINIMUM(node x)
{
while (left(x) != NIL) {
x = left(x);
}
return x;
}
TREE_MAXIMUM(node x)
{
while (right(x) != NIL) {
x = right(x);
}
return x;
}
26
次節点と前節点
• 2分探索木のある節点が与えられたとき，木
の中間順 (inorder) で次/前の節点を求める
• O(h) 時間
TREE_SUCCESSOR(node x)
{
node y;
if (right(x) != NIL) return TREE_MINIMUM(right(x));
y = p(x);
while (y != NIL && x == right(y)) {
x = y;
y = p(y);
}
return y;
}
27
x が右部分木を持つ場合
• x の次節点は，x 以上の要素で最小
⇒ x の次節点は， x の右部分木の最小要素
= TREE_MINIMUM(right(x))
x
2
7
8
5
5
次節点
28
x が右部分木を持たない場合
• x の親を y とする
• x が，x の親の右の子ならば，親は x 以下
• y は，x を左部分木に持つ x の祖先で最も
x に近いもの
次節点
y = p(x);
while (y != NIL && x == right(y)) {
x = y;
y = p(y);
}
return y;
2
9 y
5 yx
3
7
5
yx
8 x
29
定理 12.2 高さ h の2分探索木上の動的集合演
算 SEARCH, MAXIMUM, MINIMUM,
SUCCESSOR, PREDECESSOR は O(h)
時間で実行できる
30
12.3 挿入と削除
• 要素を挿入/削除したあとも2分探索木条件が
満たされる必要がある
• 挿入は比較的簡単
• 削除は複雑
• どちらも O(h) 時間
31
5
挿入
3
z 6
7 y
TREE_INSERT(tree T, node z)
x
{
2
5 z 6
8
node x,y;
y = NIL;
x = root(T);
while (x != NIL) {
// z を挿入する場所 x を決める
y = x;
if (key(z) < key(x)) x = left(x);
挿入場所は必ず葉
else x = right(x);
}
// y は x の親
p(z) = y;
// z の親を y にする
if (y == NIL) root(T) = z;
// T が空なら z が根節点
else if (key(z) < key(y)) left(y) = z; // y の子を z にする
else right(y) = z;
32
}
削除
• 探索木から節点 z を削除する
• z が子を持たない場合
– z の親と z の子を結ぶ
3
z
– z の親 p(z) を変更する
• z が子を1つ持つ場合
3
2
2
5
5
5
7 z
8
8
33
削除: z が子を2つ持つ場合
• z の次節点は左の子を持たない
• z の場所に y を入れ，元の y を削除する
15
z
15
5
6
3
3
12
10
y
6
12
13
10
13
7
7
34
TREE_DELETE(tree T, node z)
{
node x, y;
if (left(z) == NIL || right(z) == NIL) y = z; // z の子の数が1以下
else y = TREE_SUCCESSOR(z);
// z は2つの子を持つ
if (left(y) != NIL) x = left(y); else x = right(y); // x は y の子
if (x != NIL) p(x) = p(y);
// y を削除する
if (p(y) == NIL) root(T) = x;
// y が根なら x を根に
else if (y == left(p(y))) left(p(y)) = x;
// y の親と子をつなぐ
else right(p(y)) = x;
if (y != z) {
key(z) = key(y);
// y の内容を z に移動
// y の付属データを z にコピー
}
return y;
// 不必要な y を回収
35
}

Download Report