今週のトピックス アルゴリズムとデータ構造 第 10 回講義 : 探索その 1 探索 (search) 逐次探索 (sequential search) 2 分探索 (binary search) 内挿探索 (interpolation search) Produced by Qiangfu Zhao (Since 2009), All rights reserved (c) 1 Produced by Qiangfu Zhao (Since 2009), All rights reserved (c) 2 探索 (search) 探索 簡単に言えば データの中から データを探すこと. 前もって格納されている多くのデータの中からほしいデータを引き出す操作. 探索のプロセス 与えられた探索キーと一致するキーを持つ ( 全ての ) データを探し出す. 探索キーはほしいデータの特徴である 探索は与えられた特徴を持つデータを探し出すこと. 探索の例 辞書 (dictionary) 英 - 英辞書 英 - 日辞書 など キー : 単語 レコード : 単語に関連する情報 探索 : 与えられた単語の発音 意味などを調べること 記号表 (symbol table): プログラムを管理するためにシステムが作った 辞書 キー : プログラムで使用されている変数名 レコード : 変数の種類 サイズ 関連メソッドなどの情報 探索 : コンパイラが プログラム中の変数名に従ってプログラムを機械語に翻訳するために 必要な情報を引き出す 一般的に 辞書はデータベース 知識ベースと考えられる Produced by Qiangfu Zhao (Since 2009), All rights reserved (c) 3 Produced by Qiangfu Zhao (Since 2009), All rights reserved (c) 4 1
データベースの基本操作 Initialize: データ構造を初期設定する Search: 与えられたキーをもつレコードを探索する Insert: 新しいレコードを挿入する Delete: 指定されたレコードを削除する Join:2つの辞書を合併して1つの辞書を作る Sort: 辞書を整列する 逐次探索 (sequential search) プログラミング C のリニャサーチである 基本的な考え方 配列にレコードを格納し 新しいレコードを挿入する時に配列の最後におき レコードを探索する時には配列を順番に探していく 実現法 配列による 連結リストによる Produced by Qiangfu Zhao (Since 2009), All rights reserved (c) 5 Produced by Qiangfu Zhao (Since 2009), All rights reserved (c) 6 配列によるプログラム例 (p. 5, Vol. 2) static struct node {int key; int info; ; static struct node a[maxn+1]; static int N; seqinitialize() { N = 0; 最後の項目から調べ 見つ int search(int v) { かったら終了 ;a[0].keyにvを int x = N+1; 入れたので 必ず終了する a[0].key = v; a[0].info = -1; while (v!= a[--x].key) ; return a[x].info; seqinsert(int v, int info) { a[++n].key = v; a[n].info = info; Produced by Qiangfu Zhao (Since 2009), All rights reserved (c) 7 リストによる実現 : 初期化 static struct node { int key, info; struct node *next; ; static struct node *head, *z; listinitialize() { head = (struct node *) malloc (sizeof *head); z = (struct node *) malloc (sizeof *z); head->next = z; z->next = z; z->info =-1; (p. 7, Vol. 2) Produced by Qiangfu Zhao (Since 2009), All rights reserved (c) 8 2
連結リストによる実現 int listsearch(int v) { struct node *t = head; z->key = v; while (v > t->key) t = t->next; if (v!= t->key) return z->info; return t->info; リストは事前に整列されていることを前提とする リストによる実現 : 挿入 listinsert(int v, int info) { struct node *x, *t = head; z->key = v; while (v > t->next->key) t = t->next; x = (struct node *) malloc(sizeof *x); x->next = t->next; t->next =x; x->key = v; x->info = info; メリット : 整列が簡単にできる Produced by Qiangfu Zhao (Since 2009), All rights reserved (c) 9 Produced by Qiangfu Zhao (Since 2009), All rights reserved (c) 10 逐次探索の計算量 配列による実現 不成功探索 N+1 回の比較 成功探索 平均約 N/2 回の比較 整列リストによる実現 成功 不成功とも 平均約 N/2 回の比較 整列されていないリストによる実現 配列とほぼ同じ 2 分探索法 (binary search) 基本的考え方 : 分割統治法を適用 目的 : 探索時間を減らす レコードの集合を 2 つの部分に分けて 探すキーがどちらの部分に属しているかを判定し キーが属する部分を調べる レコードの集合を分割する方法 レコードを整列し 整列した配列の添字を用いて調べるべき部分を指定する Produced by Qiangfu Zhao (Since 2009), All rights reserved (c) 11 Produced by Qiangfu Zhao (Since 2009), All rights reserved (c) 12 3
2 分探索のプログラム ( 非再帰 ) int binarysearch(int v) { int l = 1, r = N, x; while (r >= l) { x = (l+r)/2; if (v < a[x].key) r = x-1; else l = x+1; if (v == a[x].key) return a[x].info; return 1; (p. 9, Vol. 2) 2 分探索の様子 キー M を探す様子 Produced by Qiangfu Zhao (Since 2009), All rights reserved (c) 13 Produced by Qiangfu Zhao (Since 2009), All rights reserved (c) 14 内挿探索 (interpolation search) 内挿探索の意味 : 線形予測 2 分探索の x = (r+l)/2 = l + (r-l)/2 を x = l + (v-a[l].key)(r-l)/(a[r].key-a[l].key) にすると 内挿探索 l a[r].key v a[l].key x r x l v a[ l]. key r l a[ r]. key a[ l]. key Produced by Qiangfu Zhao (Since 2009), All rights reserved (c) 15 Produced by Qiangfu Zhao (Since 2009), All rights reserved (c) 16 4
内挿探索の例 i 番目のアルファベットを i で表す M(=13) を探索するようす 2 分探索と内挿探索の比較 両方とも整列されているデータを探索する 2 分探索 真ん中のデータが 探したいデータかどうか調べ 探したいデータより小さければ左側に対して 大きければ右側に対して 同じことを繰り返す 内挿探索 真ん中のデータのかわりに 探したいデータの位置をある程度予測してからデータを調べる Produced by Qiangfu Zhao (Since 2009), All rights reserved (c) 17 Produced by Qiangfu Zhao (Since 2009), All rights reserved (c) 18 2 分探索の例 :20 を探したい 内挿探索の例 :20 を探したい Produced by Qiangfu Zhao (Since 2009), All rights reserved (c) 19 Produced by Qiangfu Zhao (Since 2009), All rights reserved (c) 20 5
2 分探索と内挿探索の計算量 2 分探索 : 成功 不成功とも 比較は lgn+1 回以下 内挿 : 成功 不成功とも 比較は lglgn+1 回以下 例 :N=10 億の場合 内挿探索の比較回数は 5 より小さいので 2 分探索よりかなり良い クイズ 次のようなソートされたデータがある : 1 4 6 9 10 13 19 23 25 30 (1) このデータから二分探索を用いて 9 を探索する過程を書きなさい (2) このデータから内挿探索を用いて 9 を探索する過程を書きなさい Produced by Qiangfu Zhao (Since 2009), All rights reserved (c) 21 Produced by Qiangfu Zhao (Since 2009), All rights reserved (c) 22 6