PowerPoint Presentation

Size: px

Start display at page:

Download "PowerPoint Presentation"

ふみなおいもり
4 years ago
Views:

1 今週のトピックスアルゴリズムとデータ構造第 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

2 データベースの基本操作 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

3 連結リストによる実現 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

4 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

5 内挿探索の例 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

6 2 分探索と内挿探索の計算量 2 分探索 : 成功不成功とも比較は lgn+1 回以下内挿 : 成功不成功とも比較は lglgn+1 回以下例 :N=10 億の場合内挿探索の比較回数は 5 より小さいので 2 分探索よりかなり良いクイズ次のようなソートされたデータがある : (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

Microsoft PowerPoint - algo ppt [互換モード]

Microsoft PowerPoint - algo ppt [互換モード] ( 復習 ) アルゴリズムとはアルゴリズム概論 - 探索 () - アルゴリズム問題を解くための曖昧さのない手順与えられた問題を解くための機械的操作からなる有限の手続き機械的操作 : 単純な演算, 代入, 比較など安本慶一 yasumoto[at]is.naist.jp プログラムとの違いプログラムはアルゴリズムをプログラミング言語で表現したものアルゴリズムは自然言語でも, プログラミング言語でも表現できる