探索アルゴリズム
探索とは? キー 一致するものを探す レコード フィールド
START n=10, i =0, target=54 i : n a[i] : target i++ < = 線形探索アルゴリズム (1) 前提 : 配列 a に n 個のデータが保存 処理 :target と同じデータが蓄えられている配列要素の添え字を返し, ない場合は -1 を返すフローチャートを記せ return i return -1 END
番人による少し早い線形探索 key data table[0] table[1] tabel[2] table[3] : : table[n-1] table[n] : : table[199] 75 福崎慎也 101 渡邊滋之 17 大野綾子 28 川島祐毅 : : : : 64 仲野弘幸 87 番人 (sentinel)
番人を利用した線形探索アルゴリズム START target = 54, i =0, a[n] = target a[i] : target i=i+1 = ループ毎に i と n-1 の比較が不要 i : N < return i return -1 END
2 つの線形探索アルゴリズムの比較 START n=10, target = 54, i =0 i : N < a[i] : target i=i+1 番人なし 前処理 = return i return -1 START n=10, target = 54, i =0, a[n] = target a[i] : target i=i+1 i : N < = 番人あり 前処理 return i return -1 END END
二分探索法 ( バイナリサーチ ) 探すキーの値は 14 とする low middle high a[0]=1 a[1]=3 a[2]=4 a[3]=8 a[4]=13 a[5]=14 a[6]=18 a[7]=20 a[8]=21 a[9]=25 <14 low =middle+1 middle high a[0]=1 a[1]=3 a[2]=4 a[3]=8 a[4]=13 a[5]=14 a[6]=18 a[7]=20 a[8]=21 a[9]=25 >14 a[0]=1 a[1]=3 a[2]=4 a[3]=8 a[4]=13 low, middle a[5]=14 =14 high a[6]=18 =middle-1 a[7]=20 a[8]=21 a[9]=25 探索範囲
二分探索アルゴリズム ( 半分ずつ捨てるのがポイント ) サイズnの配列 key(0~n-1) においてsを探す 1 first=0, last=n-1 2 mid = (first+last)/2 3 key(mid)=s -> Found key(mid)<s -> first=mid+1 Goto 2 key(mid)>s -> last=mid-1 Goto 2 上記アルゴリズムの問題点は? 完成させよ
線形探索の計算量 ( 比較の回数 ) は最良 1 最悪 n 平均 n/2 データ数 n に対して O(n) 二分探索の計算量 ( 比較の回数 ) は 2 k-1 n<2 k のとき k 回つまり データ数 n に対して約 O(log 2 n)
線形探索の計算量は O(n) 二分探索の計算量は O(log2 n) n=1,000 だったら? n=1,000 log 2 n= 約 10 ( なぜなら 2 10 =1,024) 100 倍違う! 定数係数が少しくらい違ったって 勝負は明らか!
ビッグ O のグラフ化 N 5 10 15 20 25 O(2 n ) 32 1024 32768 1048576 33554432 O(N 2 ) 25 100 225 400 625 O(NlogN) 3.49 10 17.64 26.02 34.94 O(N) 5 10 15 20 25 O(logN) 0.69 1 1.17 1.30 1.39 O(1) 1 1 1 1 1
O(2 n ) O(N 2 ) O(NlogN) ビッグオーの グラフ化 O(N) O(logN) O(1)
データの登録も考えると 登録 (n 要素当り ) 探索 (1 回当り ) 線形探索 O(n) O(n) 二分探索 O(n 2 ) O(log n) クイックソートで O(n log n)
登録 1 回あたりの探索回数を S とすると 線形探索 O(n)+S O(n) 二分探索 O(n log n)+s O(log n) n<<s でないと 二分探索は有利にならない! 頻繁にデータ集合が変わるような応用には二分探索は適さない
ハッシュ法
ハッシュ法 ハッシング (hashing) ともいう hash: 切りきざむ 挿入 探索 削除が O(1) でできるつまり データの個数 n に依存しない理想の探索技法!?
学生番号から氏名などを求めたい 2003 年度に入学した学生だけを考えると 70310001~70310101 配列の 0 番目から 100 番目に氏名を格納 ( 学生番号下 3 桁 -1) 番目の配列要素を見ればよい direct access という でも 一般にキーはこのように順序よく並んでいない
英和辞書 5 万語の英和辞書の全体をメモリにのせて使いたい 各単語のインデクス番号が分かれば,O(1) である単語の意味を知ることができる インデクス番号 1 2 3. 50,000 内容 hash: 切り刻む どうすれば各単語のインデクス番号が分かるか?
語を数に変換する ASCII( アスキー ) コード 大文字, 小文字, 数字, 記号などを 0 から 255 までの数で表現 a:97, b:98,, z:122 大文字, 数字, 記号などを使わないとしたら スペースを 0 として,a:1, b:2, c:3,, z:26 の 27 文字で表現できる
語を数に変換する方法 1: 単語の各文字に対応する数の総和をインデクス番号とする cats = 3 + 1 + 20 + 19 = 43 Dic[43] = cat: ネコ, 猫科の動物 ここで, 単語の最大文字数を 10 とすると, 辞書の一番最後の文字は, ( 理論的には ) zzzzzzzzzz(z が 10 個 ) = 26 X 10 = 260 50,000( 単語あるとすれば ) 260 = 192 サイズ 260 の配列を準備すれば 1 つの配列要素に 192 語が該当する 例えば 単語の各文字に対応する数の総和が cat と同じ 43 になる単語 was(23+1+19), give(7+9+22+5), tend(20+5+14+4),.
語を数に変換する方法 2: 桁位置を利用する ( べき乗化 ) 数値の場合は0から9の10 種類 (10 進数 ) 各桁は10のべき乗 配列今回の前提では 1 要素あたり, スペース 1バイトとすると,aからzの27 種類, (27 進数 ) 約 190TB のメモリが必要!! 各桁は 27 のべき乗 1TB = 1024 * 1024 * 1024 * 1024 = cats = 3x27 3 +1x27 2 +20x27 1 +19x27 0 = 60,337 zzzzzzzzzz = 26x27 9 +26x27 8 + +26x27 0 = 205,891,132,094,648 1,099,511,627,776 ( 約 1 兆バイト ) 200 兆以上!!
語を数に変換する方法 2: 桁位置を利用する ( べき乗化 ) 単語ではない fira firb firc fird fire firf firg 125146 125147 125148 125149 125150 125151 125152 実在する単語
ハッシュ法 巨大な範囲の数を実用的なサイズの配列の添え字 ( インデクス ) に変換 簡単な方法としては, モジュロ演算子 (%) を使う %n は 0 から n- 1 までの数を作りだす ( 値域 :0~3) 23 % 4 = 3 13052 % 4 = 0 38 % 4 = 2 配列のインデクス = 巨大な数 % 配列サイズ
ハッシュ関数 (hash function) キーの値 x の集合添字 ( ハッシュ値 ) h(x) の集合 h(x) 0,1,2,,99 26 5 100 大きな値域の数を小さな値域の数へとハッシュ ( 切り刻む ) する 文字列を一定範囲の整数に変換すること
ハッシュ関数の例 int hash(char *s) { int i = 0; while (*s) i += *s++; return i % 100} a:97 z:122 アスキーコードの総和を 100 で割った余りを配列添字とする a 97 b 98 c 99 d 100 e 101 f 102 g 103 h 104 i 105 j 106 k 107 l 108 m 109 n 110 o 111 p 112 q 113 r 114 s 115 t 116 u 117 v 118 w 119 x 120 y 121 z 122 この関数で求まるハッシュ値の例 文字列ハッシュ値 one 22 two 46 three four five six seven eight nine ten
ハッシュ表 ( テーブル ) ハッシュ値の例文字列ハッシュ値 one 22 two 46 three four five six seven eight nine ten ハッシュ関数を使ってデータを挿入した配列 0 1.. 26 five 27 ten 28 29 eight..
ハッシュ (1) 問題 1: 以下のハッシュ関数を用いて 表の各文字列に対応するハッシュ値を求めよ ハッシュ関数 int hash(char *s) { int i = 0; while (*s) i += *s++; return i % 11} アルファベットに対応する数値 a:1, b:2, c:3, d:4, e:5, f:6, g:7, h:8, i:9, j:10, k:11, l:12, m:13, n:14,o:15, p:16, q:17, r:18, s:19, t:20, u:21, v:22, w:23, x:24, y:25, z:26 例 :yamaguti = (25+1+13+1+21+20+9) % 11 = 2 文字列 fukuzaki watanabe oono kawashima nakano miura ハッシュ値
異なるキーが同じハッシュ値に写像されたら どうするか? 衝突の処理大きく分けて l チェイン法 l オープンアドレス法
チェイン法 ハッシュ表の同じ場所に写像されたデータを連結リストにつなぐ ハッシュ表は連結リストの先頭を指すポインタの配列
0 1 2 3 ハッシュ表 A C B 4 D E F 5 6 7 8 9 G H J I
オープンアドレス法 ある一定の方法で, 空セルを探して, そこに新たな項目を挿入する方法 1 線形探査 (linear probing) 2 平方探査 (quadratic probing) 3 ダブルハッシュ (double hashing)
ハッシュ表 h(x)=h 0 (x) h 1 (x) h 2 (x) h 3 (x) オープンアドレス法は ハッシュ表の中で仮想的な連結リストを作るようなものただし 次の要素はポインタでなく 再ハッシュ関数によって決まる
オープンアドレス法 : 線形探査 配列を単純にシーケンシャルに辿って空きセルを探すやり方 0 1 nine = 110+105+110+101 = 426 ハッシュ値 = 426%100 =26 衝突 衝突 OK.. 26 five 27 ten 28 nine 29 eight..
オープンアドレス法 : 線形探査 (2) 再ハッシュ (rehash) k 回目にアクセスする場所 : h k (x) x はキー k=0,1,2,,b-1 最も簡単な再ハッシュ関数は h k x = h x + k % B h x : 最初のハッシュ関数 B: ハッシュ表配列の大きさ
オープンアドレス法 : 線形探査の問題点 この状態でさらにハッシュ値が 26 のキーを挿入する場合データが連続してしまい, 効率が落ちる クラスター化 0.. 25 26 five 27 ten 28 nine 29 eight 30
オープンアドレス法 : 平方探査 線形探査のように, 隣接するセルに挿入してい くとクラスターができやすいので, もっと離れた 場所に挿入しようというやり方 h k x = h x + k 2 % B h x : 最初のハッシュ関数 B: ハッシュ表配列の大きさ 注意点 : 配列のサイズを素数にしなければ同じ場所を探し続けることがある
オープンアドレス法 : 平方探査の問題点 サイズ 59 の配列 ( 要素 7 に値が入っているとする ) に, 184,302,420,538 というキーを順番に挿入することを考えると 184 % 59 = 7 1 ステップで配列の要素 8 へ 302 % 59 = 7 2 ステップで配列の要素 11 へ 420 % 59 = 7 3 ステップで配列の要素 16 へ 538 % 59 = 7 4 ステップで配列の要素 23 へ 第 2 種クラスター化
オープンアドレス法 : ダブルハッシュ キーの値によって探査の歩幅が異なるようにする方法 キーに対して 2 度目のハッシュを行い, 得られた結果をステップ幅として使う h k x = h x + k h s x % B h s x = C (x % C) % B B: ハッシュ表配列の大きさ h x : 最初のハッシュ関数 C: 定数 ( 配列サイズより小さい素数 )
オープンアドレス法 : ダブルハッシュの注意点 最初のハッシュ関数と同じであってはならない 0 が作られることのある関数であってはならない ハッシュ表のサイズは素数でなければならない サイズ 59 の配列 ( 要素 7 に値が入っているとする ) に,184,302,420,538 というキーを順番に挿入することを考えると?
オープンアドレス法 : ダブルハッシュの注意点 h 5 x = h x + k h 8 x % 59 h 8 x = 11 (x % 11) % 59 (B = 59, C = 11) とすると h 184 = 184 % 59 = 7 h 8 184 = 11 (184 % 11) % 59) = 3 h D 184 = 7 + 1 3 % 59 = 10 h 302 = 302 % 59 = 7 h 8 302 = 11 (302 % 11) % 59) = 6 h D 302 = 7 + 1 6 % 59 = 13 h 420 = 420 % 59 = 7 h 8 420 = 11 (420 % 11) % 59) = 9 h D 420 = 7 + 1 9 % 59 = 16 h 538 = 538 % 59 = 7 h 8 538 = 11 (538 % 11) % 59) = 10 h D 538 = 7 + 1 10 % 59 = 17 配列の要素 10へ 配列の要素 13へ 配列の要素 16へ 配列の要素 17へ
良いハッシュ関数とは 手早い計算 ハッシュ法の利点はスピードなので, ハッシュ関数は高速であるべき ランダムキー Index = key % arraysize で得られるインデクスもランダム ( 均等 ) に分布 ノンランダムキー テーブルサイズには素数を使う 多くのキーと配列サイズに共通の公約数がある場合, それらが同じ位置へハッシュされるため
問題 1: ハッシュ (2) (2) (1) の表に示した文字列を上から順番に 要素数 11 のハッシュ表に格納せよ (3) 衝突が発生した場合には チェイン法とオープンアドレス法でそれぞれどのように衝突が回避されるかを図で示せ (4) オープンアドレス法は線形探査とダブルハッシュの両方を示すこと 線形探査とダブルハッシュのハッシュ関数は以下のとおり 線形探査のハッシュ関数 h F x = h x + k % B ダブルハッシュのハッシュ関数 h F x = h x + k h H x % B h H x = C (x % C) % B B = 11, C = 7 とする k 回目にアクセスする場所 (k=0, 1, 2,, 10)