情報システム基盤学 基礎1 アルゴリズムとデータ構造 Elements of Information Systems Fundamentals1 アルゴリズムとデータ構造　第3回 前半部

目次: 基本的なデータ構造 初歩的過ぎる ので 教科書を自分で読むこと． （平均的な効率の解析は難しい  ＭＩＴ本を見よ）． 線形リスト スタック キュー ハッシュテーブル 初歩的過ぎる　ので　教科書を自分で読むこと． （平均的な効率の解析は難しい  ＭＩＴ本を見よ）．

線形リスト データを一列に並べて 覚えたもの データを一列に並べたもの （データを線形順序に並べたもの） 9 16 4 1 各要素： 16 直観 データを一列に並べて 覚えたもの データを一列に並べたもの （データを線形順序に並べたもの） 9 16 4 1 head 線形リストの例 各要素： 前の要素へ のポインタ 次の要素へ のポインタ 1つの要素はprev，key，nextの組 prev key next prev next 16 次／前の要素がなければNULL key NULL： データ

様々な線形リスト 1. 単一方向の線形リスト 9 16 4 1 2. 双方向の線形リスト 9 16 4 1 head 2. 双方向の線形リスト 9 16 4 1 head 3. ソートされた双方向の線形リスト 1 4 9 16 head 4. ソートされてない双方向の線形リスト 9 16 4 1 head

線形リストに対する命令 探索（search） 挿入（insert） 削除（delete） 与えられた値 k をもつ要素を返す

探索 値 k が与えられたとき, 値 k をもつ要素返す 1. 値 k をもつ要素を見つける 先頭から順々に調べていく（線形探索） 2. 見つけた要素を返す, なかったらNULLを返す 例 値 4 が与えられたならば, 答えとして 4 を返す 下記のリストに対して 9 16 4 1 head 線形探索

ポインタ = 要素の名前 と解釈すればプログラミング しやすいかもしれません 探索の擬似コード LIST-SEARCH(k) 1 x = head 2 while x ≠ NULL and key[x] ≠ k 3 do x ← next[x] 4 return x ポインタ = 要素の名前 と解釈すればプログラミング しやすいかもしれません head: 線形リストの先頭要素 x: 線形リスト上の1要素を表現 key[x]: 要素 x がもつ値 next[x]: 要素 x の次の要素 prev[x]: 要素 x の前の要素 計算時間： O(n) 時間 9 16 4 1 head

挿入 要素 x が与えられたとき, x を線形リストの先頭に加える 下記のリストに対して値 25 をもつ要素が与えられたとすると 9 16 例 下記のリストに対して値 25 をもつ要素が与えられたとすると 9 16 4 1 head 挿入 25 9 16 4 1 head

挿入の擬似コード LIST-INSERT(x) 1 next[x] ← head 2 if head ≠ NULL 3 then prev[head] ← x 4 head ← x 5 prev[x] ← NULL x head head: 線形リストの先頭要素 x: 線形リスト上の1要素を表す key[x]: 要素 x がもつ値 next[x]: 要素 x の次の要素 prev[x]: 要素 x の前の要素 計算時間： O(1) 時間

削除 要素 x が与えられたとき, x を削除 下記のリストに対して値 4 をもつ要素が与えられたとすると 25 9 16 4 1 25 9 例 下記のリストに対して値 4 をもつ要素が与えられたとすると 25 9 16 4 1 head 削除 25 9 16 1 head

削除の擬似コード LIST-DELETE(x) 1 if prev[x] ≠ NULL 2 then next[prev[x]] ← next[x] 3 else head ← next[x] 4 if next[x] ≠ NULL 5 then prev[next[x]] ← prev[x] x head head: 線形リストの先頭要素 x: 線形リスト上の1要素を表す key[x]: 要素 x がもつ値 next[x]: 要素 x の次の要素 prev[x]: 要素 x の前の要素 計算時間： O(1) 時間

目次: 今日やること 基本的なデータ構造 線形リスト スタック キュー ハッシュテーブル 課題

スタック（Stack） もっとも基本的なデータ構造のひとつ 木の探索を表現（深さ優先探索） Last-in first-out（LIFO）

スタックを例えると 出入口が1つだけの満員電車 A B C D 電車の中へ 出入口 電車（だと思ってください）

スタックを例えると 出入口が1つだけの満員電車 電車（だと思ってください） 最後に入った人が最初に出る仕組み D C B A 出入口 電車の外へ 出入口 D C B A 電車（だと思ってください）

スタックのイメージ 縦長の箱に, データを一列に入れていく 注意：データの出入口は1つだけ 提供されている命令 データの流れ 縦長の箱に, データを一列に入れていく 注意：データの出入口は1つだけ 5 12 30 提供されている命令 スタック プッシュ（push）: データの追加 ポップ（pop）: データの削除 例 10 10 8 10 8 13 8 10 10 10を 追加 8を 追加 13を 追加 削除 削除

プッシュ命令 与えられた要素 x をスタックの先頭に追加 要素が1つ だけ増える 125 5 5 値125 をもつ 要素をプッシュ 12 30 30 スタック スタック

プッシュ命令の擬似コード ※線形リストでスタックが実装されていたと仮定 PUSH(x) 1 next[x] ← top 2 if top ≠ NULL 3 then prev[top] ← x 4 top ← x 5 prev[x] ← NULL 125 top top 125 5 5 12 12 30 30 線形リストの挿入と同じ スタック スタック

ポップ命令 スタックの先頭の要素を削除 ※要素を選んだりはしない 要素が1つ だけ減る 5 ポップ 12 12 30 30 スタック

ポップ命令の擬似コード ※線形リストでスタックが実装されていたと仮定 POP(x) 1 if top ≠ NULL 2 then top ← next[top] 3 prev[top] ← NULL top top 5 ポップ 12 12 30 30 スタック スタック

スタックと木の探索の関連 深さ優先探索で, 1. 頂点 v へ初めて訪れたとき, v をプッシュ 2. 頂点 v を最後に訪れるときポップ 次の操作をやってみる 深さ優先探索で, 1. 頂点 v へ初めて訪れたとき, v をプッシュ 2. 頂点 v を最後に訪れるときポップ Start End 1 7 2 3 6 5 4 4 5 6 2 3 1 7

木構造 木構造：上から下へ枝分かれした構造 r ：頂点（点） ：辺 a b c d ：根 e f h g i j 親と子 葉と内点 祖先と子孫 k m l 頂点 x を根とする部分木 深さ n 木（根つき木）の例

木構造 木構造：上から下へ枝分かれした構造 r ：頂点（点） ：辺 a b c d ：根 e f h g i j 親と子 g i j 隣接する2頂点のうち, 　・根に近い方 → 親 　・根から遠い方 → 子 k m l n 木（根つき木）の例

目次: 今日やること 基本的なデータ構造 線形リスト スタック キュー ハッシュテーブル 課題

キュー（Queue） もっとも基本的なデータ構造のひとつ 待ち行列を表現 First-in first-out（FIFO） レジ 待っている人の列 レジ

キューのイメージ 横長の箱にデータを出し入れ ※データの入口と出口の2つがある 提供されている命令 3 23 20 ※データの入口と出口の2つがある データの流れ 提供されている命令 エンキュー（enqueue）: データの追加 デキュー（dequeue）: データの削除 20 23 20 3 23 20 3 23 3 20をエン キュー 23をエン キュー 3をエン キュー デキュー デキュー

エンキュー（Enqueue） 与えられた要素 x をキューの最後尾に追加 tail head 14 5 20 値34をもつ要素を エンキュー

エンキューの擬似コード ※線形リストでスタックが実装されていたと仮定 ENQUEUE(x) 1 if tail = NULL 2 head x ENQUEUE(x) 1 if tail = NULL 2 then head ← x 3 next[x] ← NULL 4 else prev[tail] ← x 5 next[x] ← tail 6 prev[x] ← NULL 7 tail ← x 34 14 5 20 値34をもつ要素を エンキュー tail head 34 14 5 20

デキュー（Dequeue） キューの先頭の要素を削除 tail head 34 14 5 20 デキュー tail head 34 14 5

デキューの擬似コード ※線形リストでスタックが実装されていたと仮定 DEQUEUE() 1 if head = tail 2 34 14 5 20 DEQUEUE() 1 if head = tail 2 then head ← tail ← NULL 3 else head ← prev[head] 4 next[head] ← NULL デキュー tail head 34 14 5 20

目次: 今日やること 基本的なデータ構造 線形リスト スタック キュー ハッシュテーブル 課題

ハッシュテーブル (Hash Table) もっとも基本的なデータ構造のひとつ 欲しいデータを素早く検索 比較的、省スペースで実現できる ハッシュ テーブル もっとも基本的なデータ構造のひとつ 欲しいデータを素早く検索 1 比較的、省スペースで実現できる （検索スピードとスペースはトレードオフ） 2 3 4 12 2 正の整数の集合 4 1 3 6 10 8 5 12 9 7 2 9 4 11 8

ハッシュの概要 1/2 やりたいこと：集合の一部を保存したい 線形リストを利用すれば実現可能 正の整数の集合 ハッシュ ハッシュの概要　1/2 やりたいこと：集合の一部を保存したい 線形リストを利用すれば実現可能 正の整数の集合 挿入： O(1) 時間 削除: O(1) 時間 探索: O(n) 時間 スペース: 保存する整数分だけ 1 3 6 10 5 7 9 2 もう少しスペースを使ってもいいから、 効率よく探索を行いたいなぁ・・・ 8 4 11 12 保存する整数の集合は可変なので、 挿入・削除も効率よくやりたいな・・・ （緑部分は可変） ハッシュ

ハッシュの概要 2/2 基本方針: テーブルに要素を保存する k h(k) 正の整数の集合 k テーブル 1 12 2 2 関数 h 3 3 ハッシュの概要　2/2 ハッシュテーブル と呼ぶ テーブル （配列だと思えば良い） 基本方針: テーブルに要素を保存する ハッシュ関数 と呼ぶ 1 12 正の整数の集合 2 2 任意に取り出し てきたk について考えます h(k) 関数 h 3 3 6 1 k 10 4 4 5 ハッシュ値 と呼ぶ 7 9 2 8 4 11 12 8 9 気になること ハッシュ関数の決め方 ハッシュ値が等しいとき（衝突）はどうする？ h(k) k

ハッシュ関数 h(k) = k mod p 様々なハッシュ関数が知られている テーブル上に整数を一様にばらまく（一様ハッシュ関数） 良いハッシュ関数 テーブル上に整数を一様にばらまく（一様ハッシュ関数） 計算が簡単 今回は、除算法（division method）を用いる h(k) = k mod p k: 保存したい整数 p: 自分で決める値（素数がよい） 除算法では以下のハッシュ関数を使用 テーブルサイズは p – 1 とする

ハッシュテーブルの例 下記の整数をハッシュテーブルで保存する 190 下記の整数をハッシュテーブルで保存する 1 77 2 {3, 5, 77, 109, 190, 245, 832, 852, 9924, 10346} 3 3 4 ハッシュ関数は下記のように定義 h(k) = k mod 19 p =19 としてます 5 5 6 9924 7 8 このとき, 各整数のハッシュ値は次の通り h(3) = 3, h(5) = 5, h(77) = 1, h(109) = 14, h(190) = 0, h(245) = 17, h(832) = 15, h(852) = 16, h(9924) = 6, h(10346) = 10 9 10 10346 11 12 13 14 109 ここで, もし, 整数 25 を挿入したいとしたら・・・ 15 832 16 852 h(25) = 6 となり, すでに 9924 が格納されている （これを衝突と呼ぶ） 　　　　ど、どうしよう。。。 17 245 18

衝突回避 その1: チェイン法（Chaning） ハッシュ テーブル 190 456 1 77 2 リストを使って衝突を回避 3 3 各スロットに複数の要素を対応させる 4 5 5 6 9924 25 44 7 各スロットについて線形リストを保持する 8 9 10 10346 例 11 h(25) = 6: スロット6で衝突 → スロット6のリストへ追加 12 13 h(456) = 0: スロット0で衝突 → スロット0のリストへ追加 14 109 h(44) = 6: スロット6で衝突 → スロット6のリストへ追加 15 832 16 852 17 245 デメリット： 使用していないスペースがまだあるのに, 他のスペースを使ってしまう 18

衝突回避 その2: 線形探査（Linear Probing） ハッシュ テーブル 190 1 77 線形探査の流れ 2 1. スロット i で衝突が発生 3 3 4 2. スロット i + 1 をチェック 5 5 3. スロット i + 1 が空きならば, そこへ整数を保存、終了 6 9924 25 4. そうでないならば, i をインクリメントして 1. へ戻る 7 25 8 例 9 h(25) = 6: スロット6で衝突 → スロット7へ スロット7が空きなので、そこへ追加 10 10346 11 12 h(91) = 15: スロット15で衝突 → スロット16へ スロット16で衝突 → スロット17へ スロット17で衝突 → スロット18へ スロット18が空きなので、そこへ追加 13 14 109 15 832 91 16 852 17 245 デメリット： クラスタができてしまい、 　　　　　　　追加・探索が極端に遅くなるかもしれない 18 91

Note: 本スライドは山中克久　助教（当時）が 2010年度に作成したものを，今回，大森が 改訂したものです．　　 2013．4.25．記

目次: 今日やること 基本的なデータ構造 線形リスト スタック キュー ハッシュテーブル 課題

第1回 レポート課題 課題1 挿入ソートと（クイックソート or マージソート）を作成して下さい 課題2 出題日: 2011/06/20 締切日: 2011/06/27 課題1 挿入ソートと（クイックソート or マージソート）を作成して下さい 余裕のある人へ ランダムに1万個の整数を生成し、挿入ソート・クイックソートそれぞれでソートを実行して下さい。それぞれのソートにかかる時間を測定して違いを確認して下さい。（整数の個数は、違いが分かればいくつでも良い。） 課題2 Boyer-Mooreの簡易版アルゴリズムをプログラムとして実装して下さい（簡易版：サボりを行っていないもの）。出現する文字は小文字アルファベットのみ（aからzまで）としてください。 自身のない人へ 上記の課題の代わりに、文字列照合で説明したNaiveアルゴリズム（Naive-String-Matcher）をプログラムとして実装して下さい。

レポート課題に関する注意 提出： 次の授業日（6/27, 月）までにMLに送付 　　　　送付先ML　kiso1-2011-report@hpc.is.uec.ac.jp 　 メール本文，および，レポート(プログラムの説明・考察を書いた資料)に (1) 学籍番号, (2) 専攻名 (3) 研究室, (4) 氏名 を記入のこと！ レポートには、プログラムソースと実行結果を含めること 適宜、プログラムの説明・考察を含めること どうしてもプログラムが書けないという人は、アルゴリズムの動作を詳しく説明したレポートを作成して提出すること

おまけ 時間測定の一例 clock_t time[2]; time[0] = clock(); // 関数呼出前の時刻 測りたい関数を呼び出す; time[1] = clock(); // 関数呼出後の時刻 printf("Running time for ins. sort: %.4f sec.\n", (double)(time[1]-time[0])/CLOCKS_PER_SEC); // 呼出前時刻から呼出後時刻を引き（time[1] – time[0]のところ）, // 秒数に変換（割り算のところ）, // さらに, double型として扱うように指定（(double)のところ）

目次: 今日やったこと 基本的なデータ構造 線形リスト スタック キュー ハッシュテーブル おしまい 今日もご苦労様でした

Item Page アイデア サイズ24 サイズ28 しかし アイデア

目次: 今日やること 基本的なデータ構造 線形リスト スタック キュー ハッシュテーブル