探 索 アルゴリズム
探 索 とは? キー 一 致 するものを 探 す レコード : : : フィールド
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 番 人 なし START 番 人 あり n=10, target = 54, i =0 i : N < a[i] : target i=i+1 前 処 理 = return i return -1 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 前 要 提 素 では,スペース,aからzの27 あたり1バイトとすると, 種 類 (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 ハッシュ 値
異 なるキーが 同 じハッシュ 値 に 写 像 されたら どうするか? 衝 突 の 処 理 大 きく 分 けて チェイン 法 オープンアドレス 法
チェイン 法 ハッシュ 表 の 同 じ 場 所 に 写 像 された データを 連 結 リストにつなぐ ハッシュ 表 は 連 結 リストの 先 頭 を 指 す ポインタの 配 列
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の 配 列 (すべてセルが 空 いているとする)に, 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 s (x)=(c (k % C)) % B B:ハッシュ 表 ( 配 列 )の 大 きさ C: 定 数 ( 配 列 サイズより 小 さい 素 数 )
オープンアドレス 法 :ダブルハッシュの 注 意 点 最 初 のハッシュ 関 数 と 同 じであってはならない 0が 作 られることのある 関 数 であってはならない ハッシュ 表 のサイズは 素 数 でなければならない ハッシュ 表 のサイズが59で,ステップ 幅 は? h s (x)=(11 (k % 11)) % 59とすると 184 % 59 = 7 配 列 の 要 素 8へ 302 % 59 = 7 (11-(302%11))%59 = 6, 要 素 14へ 420 % 59 = 7 (11-(420%11))%59= 9, 要 素 17へ 538 % 59 = 7 (11-(538%11))%59=10, 要 素 18へ
良 いハッシュ 関 数 とは 手 早 い 計 算 ハッシュ 法 の 利 点 はスピードなので,ハッシュ 関 数 は 高 速 であるべき ランダムキー Index = key % arraysizeで 得 られるインデクスもランダム ( 均 等 )に 分 布 ノンランダムキー テーブルサイズには 素 数 を 使 う 多 くのキーと 配 列 サイズに 共 通 の 公 約 数 がある 場 合,そ れらが 同 じ 位 置 へハッシュされるため
問 題 1: ハッシュ(2) (2) (1)の 表 に 示 した 文 字 列 を 上 から 順 番 に 要 素 数 11のハッ シュ 表 に 格 納 せよ (3) 衝 突 が 発 生 した 場 合 には チェイン 法 とオープンアドレス 法 でそれぞれどのように 衝 突 が 回 避 されるかを 図 で 示 せ (4) オープンアドレス 法 は 線 形 探 査 とダブルハッシュの 両 方 を 示 すこと 線 形 探 査 とダブルハッシュのハッシュ 関 数 は 以 下 のとおり 線 形 探 査 のハッシュ 関 数 h k (x)=(h(x)+k) % 11 k 回 目 にアクセスする 場 所 (K=0, 1, 2,, 10) ダブルハッシュのハッシュ 関 数 h s (x)=(7 (k % 7)) % 11 kはハッシュ 関 数 hash() 内 の11で 割 った 余 りを 求 める 直 前 の 変 数 iの 値