アルゴリズム論 ( 第 10 回 ) マージソート 佐々木研 ( 情報システム構築学講座 ) 講師山田敬三 k-yamada@iwate-pu.ac.jp 内部ソートと外部ソート 内部ソート メモリを使用 外部ソート ファイルを直接操作してソートを行う. 一般に, 主記憶 < 補助記憶 外部ソートの留意点 1. 記憶空間を節約することは考慮しない. ソートを高速化するためには, 同じデータをいくつかのファイルに同時に格納 2. アクセス ( ランダムアクセスと順アクセス ) メモリ上では, ランダムアクセスと順アクセスの時間は変わらない. しかし, 媒体によってはランダムアクセスは不可能. ファイルの場合, 順アクセスの方が, 結果早くなることもある. バッファリングが可能なため ファイルの merge P.64~P.65 のプログラム解説 ファイル aaa, ファイル bbb から同時に 1 つずつ数値を読み込み 小さい値をファイル ccc に書き込む aaa,bbb のどちらかが終わるまで続ける どちらかが終わったら 数値が残っているファイルの中身を ccc へ書き込む 自然マージ (merge) ソート 連 (run): 順序つけられた部分 f: 29 32 34 21 19 50 10 43 33 49 100 60 下線で示した連を fa, fb のファイルに分配 fa: 29 32 34 19 50 33 49 100 fb: 21 10 43 60 これから fa, fb をマージして f に書き込む f: 21 29 32 34 10 19 43 50 60 33 49 100 これを繰り返す 1
自然マージ (merge) ソート f: 21 29 32 34 10 19 43 50 60 33 49 100 fa: 21 29 32 34 33 49 100 fb: 10 19 43 50 60 f :10 19 21 29 32 34 43 50 60 33 49 100 fa: 10 19 21 29 32 34 43 50 60 fb: 33 49 100 f: 10 19 21 29 32 33 34 43 49 50 60 100 ファイルの merge P.66~P.69 のプログラム解説 main: メインプログラム 初期設定 ファイルからデータ入力と 結果出力 nmsort: distribute と merge を繰り返してソート distribute: 連ごとにファイルへ分散 copyarun を呼び出して fa, fb へ連をコピー merge: 2 つのファイル fa, fb を連ごとにマージ copyarun: f から連を抽出する ソート終了 ランダムアクセスを使ったソート ランダムアクセスを行う関数 fseek( fp, offset, code) ファイルの読み取り ( 書き込み ) 開始場所を指定する fseek(fp, 0L, SEEK_END) でファイルの長さが確認できる ftell(fp) 現在のファイルの読み取り ( 書き込み ) 開始位置を確認する ランダムアクセスを使用してクイックソートを行う (P.71~73) 安定な (stable) ソート 同じキーを持つレコードの順番がソート後も保持されるソートのこと 345 Patterson 289 Taylor 345 Johnson 安定したソート クイックソートの場合はこうなることがある 289 Taylor 345 Patterson 345 Johnson 289 Taylor 345 Johnson 345 Patterson ソートの評価 クイックソートも自然マージソートも O(n log n) 自然マージソートはクイックソートに比べて多くのファイル空間を使用する ハードウェアの条件によっては, クイックソートが遅い場合もある. ハードディスク :Qsort Msort 仮想ディスク : Qsort Msort ソートの評価 1. 自然マージソートは一時的なファイルを使用するが クイックソートは使用しない 2. クイックソートはランダムアクセスに基づいているため ランダムアクセスが出来ないハードウェアや開発言語では実現不可 3. すでに, ほぼ昇順になっている場合は, 自然マージソートの方が速い. 4. 自然マージソートは安定な (stable) ソートである.( クイックソートは違う ) 5. クイックソートのキーの比較回数は 自然マージソートに比べてはるかに低い 2
データの探索 2 分探索 配列 a 要素 a[i](i=0,1,,n-1) 配列 a から値 x を探索 ( 線形探索 ) i=0~n-1 まで, 以下を繰り返す. a[i] と x を比較 a[i]==x なら終了 2 分探索 (binary search) 前提条件 要素 a[i](i=0,1,,n-1) について a[0]<a[1]< <a[n-1] が成立 配列 aからxの場所を求める方法 xが配列 aにあるか否か, 配列のどの要素よりも大きいか, 小さいかも返値とする 返値 0 x a[0] i= j a[j-1]<x a[j] (0<j N-1) N a[n-1]<x 2 分探索 (binary search) アルゴリズム (P.82~83) 1. x a[0] またはx>a[n-1] であるかどうかを調査する そうでなければ a[0]<x a[n-1] の場合のみを考える 2. leftとrightについて初期化する left=0, right=n-1 3. 探索する配列の中央を探す middle = (left + right) / 2 4. xと中央の値 a[middle] を比較する 1. xがa[middle] 以下の場合は 新しい探索配列の右側を middleにする 2. xがa[middle] よりも大きい場合は 新しい探索配列の左側 をmiddleにする 5. 3~4 をright-left<=1になるまで繰り返す 計算量 検索範囲は比較する段階で元の配列の 1/2 となる 比較する回数 k は 全体の要素数 N とすると 2 k = N すなわち k=log 2 N よって O(logN) 使うときの注意点 検索結果 i を用いて必ず配列を確認する アルゴリズムは n を返すことがあるが, 配列は a[n-1] までしか値がない x が配列 a の中に見つかるとは限らない. すなわち,x == a[i] とは限らないので, 検査する必要がある. 3
アルゴリズム論 ( 第 11 回 ) ハッシュ法 佐々木研 ( 情報システム構築学講座 ) 講師山田敬三 k-yamada@iwate-pu.ac.jp ハッシュ法 対象データを非常に効率よく格納し 検索する方法 対象データはレコード レコードは互いに異なるキーを含む キーを適当な範囲の自然数に変換 ハッシュ法 キーの値が レコードの位置に対応していれば 検索が速い a[0], a[1],, a[n-2], a[n-1] に, レコードのキー i に対して,a[i] にデータを格納していればよい しかし,i が配列のサイズよりも大きい場合や, キーが自然数でない場合は, この方法は不可能 そこで キーを適当な自然数に変換する関数を考える ハッシュ関数 ハッシュ法 ハッシュ関数 H を適用し 一次インデックス値を得る 一次インデックスは要素数 N よりも小さい非負の整数値 一次インデックスとキーは 1 対 1 であることが望ましいが, ここでは問わない ( 難しい ) H(k1)=H(k2) となる状況を衝突 (collision) という P.86 のプログラムを参照 ここでは 先頭文字と最終文字と長さに依存しているため, 同じハッシュ値になるものは簡単に見つかる ABC と AZC は同じハッシュ値になる ハッシュ法 同じハッシュに対応するための方法 オープンアドレス法と連結法 ここでは オープンアドレス法を用いる 与えられた配列にすべてのデータを格納する 連結法では レコードを多数の線形リストとして格納する 衝突した場合 つまり 同じ場所にすでにデータが入っているので データを格納できない 次の配列番号の配列要素にデータを格納する i+1 (i<n のとき ) または 0 (i=n-1 のとき ) を繰り返す 線形探査法 (linear probing) P.88 のプログラムを参照 4
線形探査法 ABC AZC hash hash 1028 ハッシュ法 線形探査法は単純で魅力的! しかし 同じハッシュが続くと効率が悪くなる 線形探索法は 1 つずつ配置をずらすために効率が悪い 衝突が起こったときに 増分を別のハッシュ関数で求める 増分を用いて循環的に足し算する ダブルハッシュ法 循環的に足し算するので 配列の大きさ N が素数で無い場合は 元の場所に戻る可能性がある 増分 inc は N よりも小いとしても一般性を失わない inc<n ダブルハッシュ法 ダブルハッシュ法 ABC hash AZC hash Second hash ABC hash AZC hash Second hash + 234 =1261 + 234 =1261 1261+234=1495 1495%1493=2 1261 2 1261 1492 ハッシュ法 P.90~92のプログラムを参照 ダブルハッシュ法はデータ ( レコード ) の数よりも十分大きな配列 ( 空間 ) を持つことが望ましい 循環 重連結リスト 5
循環リストと重連結リスト 循環リスト (circular list) 循環リストと重連結リスト 循環 重連結リスト 重連結リスト (doubly linked list) dummy 空の循環 重連結リスト 循環リストと重連結リスト ノードの挿入 *(p->left) ノードの削除 *q q *p *p p typedef struct Node { int num; struct Node *left, *right; } node; int insert_cdl_list(int x) { node *q, *p = (node*)malloc(sizeof(node)); if (p == NULL) return 0; p->num = x; 1 q = start->left; 2 start->left = p; 3 p->right = start; 4 q->right = p; 5 p->left = q; return 1; } int insert_left(node *p, int x) { node *q = (node*)malloc(sizeof(node)); if (q == NULL) return 0; 6 q->left = p->left; q->num = x; 7 q->right = p; 8 p->left->right = q; 9 p->left = q; return 1; } 循環 重連結リスト 初期状態 start 関数 insert_cdl_list を実行 2 start 5 4 1 q p 3 typedef struct Node { int num; struct Node *left, *right; } node; int insert_cdl_list(int x) { node *q, *p = (node*)malloc(sizeof(node)); if (p == NULL) return 0; p->num = x; 1 q = start->left; 2 start->left = p; 3 p->right = start; 4 q->right = p; 5 p->left = q; return 1; } int insert_left(node *p, int x) { node *q = (node*)malloc(sizeof(node)); if (q == NULL) return 0; 6 q->left = p->left; q->num = x; 7 q->right = p; 8 p->left->right = q; 9 p->left = q; return 1; } 問題 1 再度, 関数 insert_cdl_list を実行した結果を答えなさい. start 解答 start 2 q 1 q 3 5 4 p p typedef struct Node { int num; struct Node *left, *right; } node; int insert_cdl_list(int x) { node *q, *p = (node*)malloc(sizeof(node)); if (p == NULL) return 0; p->num = x; 1 q = start->left; 2 start->left = p; 3 p->right = start; 4 q->right = p; 5 p->left = q; return 1; } int insert_left(node *p, int x) { node *q = (node*)malloc(sizeof(node)); if (q == NULL) return 0; 6 q->left = p->left; q->num = x; 7 q->right = p; 8 p->left->right = q; 9 p->left = q; return 1; } 問題 2 関数 insert_left を実行した結果を答えなさい. 解答 6 8 q q 9 7 p p 6
アルゴリズム論 ( 第 12 回 ) 2 分木 佐々木研 ( 情報システム構築学講座 ) 講師山田敬三 k-yamada@iwate-pu.ac.jp 2 分探索のためのデータ構造 連結リストの探索には 線形探索が使われる 線形探索は 2 分探索に比べて遅い! 2 分探索を動的なデータ構造に適応することを考える 2 分探索木 2 分木自体はすでに済 完全バランス 2 分木 テキストファイル中の単語の出現頻度を調べるプログラム P.161~ ソースファイル : bintree.c bt バランスのよい 2 分木 2 分木はバランスしていることが望ましい. -バランスとは -2 分探索木と連結リストとの比較 0 完全にバランスした木 全てのノードにおいて, その左部分木と右部分木でそれぞれのノードの数がたかだか 1 つしか違わない木. 10 20 30 40 完全にバランス高さがバランス (AVL 木 ) 7
変換 2 分木から 完全にバランスした 2 分木 への変換 読み込むデータが昇順で与えられている. データの数があらかじめわかっている. 1: node* pbtree(int n) { 2: int nleft, nright, nleftplusright = n - 1; 3: node* p; 4: if (n == 0) { return NULL; } 5: nleft = nleftplusright / 2; 6: nright = nleftplusright - nleft; 7: p = (node*)malloc(sizeof(node)); 8: p->left = pbtree(nleft); 9: scanf("%d", &p->num); 10: p->right = pbtree(nright); 11: return p; 12: } typedef struct Node { int num; struct Node *left, *right; } node; 2 分探索木 ( データ数 :10) 15 12 18 11 13 16 19 14 17 20 情報システムへの応用 データ : 個人名と数値 ( 電話番号, 登録番号など ) 1. ファイルから全てのデータを読み込み, 完全にバランスした2 分探索木を生成する.(.L) 2. 指定した名前のデータを探索する.(<name>?) 3. 新しいデータを追加する.(<name> <value>) 4. 指定したデータを削除する.(<name> /) 5. 指定したデータの数値を変更する.(<name> <value>) 6. 全てのデータをファイルにセーブする.(.S) 7. 全てのデータをアルファベット順に表示する.(.P) 問題 下記の 8 個のデータに対して, 関数 pbtree を実行したときの, 完全にバランスした 2 分木を答えなさい. 1, 2, 3, 4, 5, 6, 7, 8 P.175~ ソースファイル : infsys2.c 2 分探索木 ( データ数 :8) 2 4 6 B- 木 1 3 5 7 8 8
B 木 大容量データを処理するためには補助記憶装置が必要. 全データ中, 必要部分を読込, 利用することを考慮する. 補助記憶装置 ( ハードディスク ) のアクセスは遅い. キーを含むデータをグループ化し, 大きなデータブロックとして扱うことを考える. B 木 ( 多分木の一種 ) 固定値 Mに対して, 各ノードは最大 2M 個のデータを含む. 根ノードを除く各ノードは少なくともM 個のデータを含む. 根ノードは少なくとも1 個のデータを含む. 各ノードのデータは昇順に並んでいる. B 木の全ての葉は, 同じレベルにある. ソースファイル : btree.c M : B 木の次数 ( 位数,order) B 木の例 ( 次数 :2) 40 -- -- -- ルートノード 12 18 -- -- 50 60 -- -- 5 6 -- -- 20 21 -- -- 41 42 -- -- 63 66 68 69 14 15 16 17 52 56 58 -- B 木の変化 : 60,20,80,10 を挿入 B 木の変化 : 15 を挿入 10 20 60 80 10 20 60 80 20 -- -- -- 10 15 -- -- 60 80 -- -- B 木の変化 : 30,70 を挿入 B 木の変化 : 22 を挿入 20 -- -- -- 20 -- -- -- 10 15 -- -- 60 80 -- -- 10 15 -- -- 30 60 70 80 20 -- -- -- 20 60 -- -- 10 15 -- -- 30 60 70 80 10 15 -- -- 22 30 -- -- 70 80 -- -- 9
B 木の変化 : 12,18,19,4,5,6,2,3 を挿入 B 木の変化 : 1 を挿入 20 60 -- -- 6 15 20 60 10 15 -- -- 22 30 -- -- 70 80 -- -- 2 3 4 5 18 19 -- -- 70 80 -- -- 10 12 -- -- 22 30 -- -- 6 15 20 60 15 -- -- -- 2 3 4 5 18 19 -- -- 70 80 -- -- 10 12 -- -- 22 30 -- -- 1 2 -- -- 3 6 -- -- 10 12 -- -- 18 19 -- -- 20 60 -- -- 70 80 -- -- 4 5 -- -- 22 30 -- -- B 木の変化 : 27 を削除 ( ケース 1) P 20 30 40 -- L R 10 12 -- -- 25 27 -- -- 33 34 36 -- 46 48 -- -- ノードLでアンダーフロー P 20 33 40 -- L R 10 12 -- -- 25 30 -- -- 34 36 -- -- 46 48 -- -- ノードRから1つ借りた B 木の変化 : 27 を削除 ( ケース 2) P 20 30 40 -- L R 10 12 -- -- 25 27 -- -- 33 34 -- -- 46 48 -- -- ノード L でアンダーフロー P 20 40 -- -- 10 12 -- -- 25 30 33 34 46 48 -- -- ノード L と R を合併した 問題 1 30 を挿入した後の B- 木を答えなさい. 問題 2 80 を挿入した後の B- 木を答えなさい. 20 -- -- -- 8 20 43 56 9 11 -- -- 25 31 -- -- 2 3 -- -- 22 25 -- -- 60 72 77 79 17 18 -- -- 44 49 -- -- 43 -- -- -- 20 -- -- -- 8 20 -- -- 56 77 -- -- 2 3 -- -- 22 25 -- -- 44 49 -- -- 79 80 -- -- 9 11 -- -- 25 30 31 -- 17 18 -- -- 60 72 -- -- 10
問題 3 25 を削除した後の B- 木を答えなさい. 20 30 40 -- 10 12 -- -- 22 25 -- -- 31 35 39 -- 46 48 -- -- アルゴリズム論 ( 第 13 回 ) 20 31 40 -- 10 12 -- -- 22 30 -- -- 35 39 -- -- 46 48 -- -- 佐々木研 ( 情報システム構築学講座 ) 講師山田敬三 k-yamada@iwate-pu.ac.jp バックトラッキングとは バックトラッキング 分岐点における 1 つの選択肢からの展開を全て調べた後に またその分岐点に戻ること バックトラッキングとは 木構造のデータを全て調べていくことは無駄が多い 最適解を調べたいとき その条件を超える場合は 経験的にそれ以上調べる必要がないことはわかる 探索ルートと途中で戻ることを枝刈りという バックトラッキングとは バックトラッキングと枝刈りを組み合わせて使うことで効率よく問題を解決できる 11
ナップサック問題 n 個の荷があり それらの重さは a 1,a 2,,a n である. 重さ W まで耐えるナップサックがあり, それにぴったりになるように荷を選びたい. それらの全ての組み合わせを求めよ. n が大きくなると大変解きにくい 全体の組み合わせは 2 n ( 例 ) n=30 のとき 2 30 10 9 ナップサック問題 枝刈りの方針 全ての組み合わせを調べる途中で, それまでの重さの計がすでに Wを超えていたら, それ以後の組み合わせは考えない ナップサック問題 ナップサック問題 ( 例題 ) 重さ 10,5,15,7,3 の 5 つの荷があり, W=22 のときの全ての組み合わせを求めよ 割宛て問題への適用 (1) 仕事と人の相性を考えて 合計コストが一番小さくなるように n 個の仕事を n 人に割り当てる問題 a b c d e 1 10 14 20 32 20 2 5 20 30 8 14 3 7 15 22 18 8 4 12 10 25 25 10 5 8 13 22 12 18 割宛て問題への適用 (2) 腕ずくの方法 ずべての組み合わせを調べて最小のコストを探す 全ての組み合わせは n! 通り (5!=120 通り ) 枝きりの方法を使う 途中の計算上で最小のコストを越した場合は それ以上の計算を進めない バックトラックする 12
8 人の女王問題 ( エイト クイーン ) 8 人の女王を 8 8 の盤に配置する問題 条件 1 人の女王から その行と列およびその位置から見える対角線上に他の女王がいてはいけない 置き方の総当り数は? 64C8 = 4,426,165,368 女王は同じ行列にいることはできないので 8! = 8 7 6 5 4 3 2 1=40,320 となる 配置例 8 人の女王を 8 8 の盤面に配置する. ある女王を配置した行列およびその対角線上には他の女王を置いてはいけない. 配置例 13
失敗 14
用語 構文解析 帰納的に定義された文字列の無限集合を言語という ( 例 : 算術式 ) 形式的な規則によって 与えられた文字列が言語に属するか否かが決定される規則 文法 (grammar) or 構文規則 (syntax rule) 意味規則 (semantic rule): 一般的な言語 ( 算術式やプログラミング言語 ) に対して定められる 算術式の場合 式の意味は式の値として定義される プログラミング言語の場合, 命令の実行順序を表す抽象的な記述 ( 抽象的な機械語 ) として定義される VSL(Very Simple Language) 簡単な例 :VSLを定義 VSLの実現を考える 実現方法 (implimantation) には インタプリタ ( 解釈系, interpreter) コンパイラ ( 翻訳系, compiler) インタプリタとコンパイラ インタプリタ 計算機を支配下に置く 入力データの記述に従って処理を進める 入力データは ソースコードまたは中間コード コンパイラ 最終的に独立したプログラムになるコードを生成する 生成されたコードを目的コードとよぶ 構文グラフ 図 9.1 参照 {,}, 数字 : 終端記号またはプリミティブ 式 : 非終端記号 項 因子 構文グラフ プログラム 式 項 因子 式 項 項 因子 因子 因子 数字 数字 数字 { 2 * ( 4-1 ) } 15
式と 2 分木 式は2 分木で表現できる {2*3-4*5} - * * 2 3 4 5 中置記法から後置記法 記法 - 8 3 前置 8-3 中置 8 3 - 後置 ( 逆ポーランド記法 ) 引数を持つ関数は前置記法 8-3=5 は subtract(8, 3) コンパイラの作成を考える上では 逆ポーランド記法が優位 中置記法から後置記法 変換方法 中置式は2 分木で表記できる - 2 分木の通り方によって前置 中置 後置記法に変わる * * 1. 行きがけ順 前置 2. 通りがけ順 中置 3. 帰りがけ順 後置 2 3 * 4 5 * - 後置記法 ( 逆ポーランド記法 ) ならスタックが使える 2 3 4 5 ソーステキストインタプリタ プログラミング言語の設計 言語構文規則 意味規則 任意の VSL プログラムを読み込み 記述された処理を実行する C プログラム ソーステキストインタプリタ ソーステキストを解析する方法 再帰降下法 (recursive descent) 再帰的な関数の階層構成に基づいた方法 目的プログラムと実行時システム コンパイラ 解釈を必要とする中間コードの代わりに プログラムの形式を持つ実行可能なコードを生成する 現在のコンパイラ ソースコードから機械語を生成する 途中でアセンブリコードに変換することもある 中間コードとの違い 中間コードは入力データである ソーステキストの解析 因子などの構文的概念のそれぞれに対して 1 つの関数を用意する 大域変数 buf を準備 buf が 0 でないときだけその内容を使用 関数 factor の機能は 入力ファイルから 1 つの因子を読み込む 因子を評価し その値を返す 16
ソーステキストの解析 関数 next buf が 0 のときだけファイルから文字を読む buf が 0 でないとき buf の値を使用し buf=0 とする 空白と改行は無視する 関数 nextis 与えられた文字が入力ストリームから読み込むことができるかどうかを調べる 読み込めれば 1 を返す そうでなければ 0 ソーステキストの解析 関数 term 因子を読んで * が続くまで読み込む 各因子に対して * の演算を行う 関数 expression 項を読んで +- の演算を行う ここまでのまとめ INTERPR.C 直接ソースコードを解釈して結果を出す POSTFIX.C 中間コードとして後置式を出力する 構文解析と計算を分離する 中間コードを作成する方が効率がよい 同じ種類の計算が何度も実行される繰り返しがあるときに 処理を 1 度で済ますことが出来る 現在のインタープリタは中間コードに変化 その後解釈する この課題では 目的プログラムを C 言語とする VSL から C 言語へのコンパイラ P.300 の VSL を P.301 の C 言語へ変換 1. OBJECT.C をコンパイラから生成 2. OBJECT.C を C でコンパイル 3. RTS とリンクする (RTS.C はライブラリ ) 4. 実行 この課題では コンパイラとしてPOSTFIX.Cを変更 P.304~P.306 新 POSTFIX.CはVSLを後置法 ( 逆ポーランド記法 ) に変換 変換された後置記法の表現を OBJECT.CのC 言語に変換 17