酒居敬一(sakai.keiichi@kochi-tech.ac.jp) アルゴリズムとデータ構造1 2005年7月1日 酒居敬一(sakai.keiichi@kochi-tech.ac.jp) http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2005/index.html

待ち行列（FIFO） データ挿入 データ取得 待ち行列（データの挿入・取得）

待ち行列の配列による実現 データ挿入 データ取得 新しい要素を入れようとすると入らない →右へコピーして移動 →隙間を空ける

リングバッファ(46ページ) 配列の最初と最後を接続して環にしたもの ２つのポインタでデータの出し入れを管理 データの先頭を指すポインタ head, front データの最後尾を指すポインタ tail, rear ２つのポインタが重なったらデータは空 領域の大きさをnとしたらポインタの位置はnとおり データの数が0からnまでn+1とおりある ポインタが重なったら、空か満杯の状態が重なる…

リングバッファ 挿入口 リア 環状のデータ格納領域 データの存在を示すポインタ 取り出し口 フロント

満杯になったとき、 リアとフロントのポインタが 重なってしまって 空と区別が付かない フロント フロント リア

配列を使用したリングバッファ 配列には始まりと終わりがある ポインタが終わりまで移動したら先頭へ戻る （フロント－リア）の演算でも境界を考慮 ラップラウンド処理 条件文で判定 配列の大きさを2のべき乗にする 配列のインデックスをビットごとのAND処理

データのおき場所は配列 front, rearというポインタで管理 キューの容量はmaxSizeで管理 public class Queue { private Queue() } public Queue(int aMaxSize) int realSize = aMaxSize + 1; this.maxSize = realSize; this.queueArray = new Object[realSize]; this.front = 0; this.rear = 0; private int front; private int maxSize; private Object[] queueArray; private int rear; データのおき場所は配列 front, rearというポインタで管理 キューの容量はmaxSizeで管理

frontの指すところがキューの先頭 先頭と最後尾が同じ場合は空 条件文でラップラウンド処理 public Object dequeue() { if(this.isEmpty()){ System.err.println("待ち行列は空です"); return null; } Object dequedObject = this.queueArray[this.front]; this.queueArray[this.front] = null; ++this.front; if(this.maxSize == this.front){ this.front = 0; return dequedObject; public boolean isEmpty() return (this.rear == this.front); frontの指すところがキューの先頭 先頭と最後尾が同じ場合は空 条件文でラップラウンド処理

rearの指すところがキューの最後尾 先頭と最後尾が同じ場合は空 そうならないようにする判定が必須 条件文でラップラウンド処理 public boolean enqueue(Object aTarget) { if(this.isFull()){ System.err.println("待ち行列はいっぱいです"); return false; } this.queueArray[this.rear] = aTarget; ++this.rear; if(this.maxSize == this.rear){ this.rear = 0; return true; public boolean isFull() return ((this.rear + 1) == this.front); rearの指すところがキューの最後尾 先頭と最後尾が同じ場合は空 そうならないようにする判定が必須 条件文でラップラウンド処理

場合分けしてラップラウンド処理 frontから配列終わりまでの表示 配列先頭からrearまでの表示 public void printAll() { System.out.println("待ち行列の内容"); if(this.isEmpty()){ System.out.println(); return; } int count = 1; int position = this.front; int limit = (this.front > this.rear)? this.maxSize: this.rear; while(position < limit){ System.out.println(count +"\t" + this.queueArray[position]); ++count; ++position; position = 0; limit = (this.front > this.rear)? this.rear: 0; 場合分けしてラップラウンド処理 frontから配列終わりまでの表示 配列先頭からrearまでの表示

マージソート(198ページ) 手続きf(p) 問題pを半分にする それぞれの部分問題に対して次の処理 半分にした問題をマージする 部分問題の要素数が2個 小さい順に並び替える→次の処理へ 部分問題の要素数が1個 並び替える必要が無い→次の処理へ 部分問題の要素数が2個より多い 手続きfを部分問題を引数に呼ぶ 半分にした問題をマージする 部分問題列の先頭から、小さい順に取り出す

分割統治法(162ページ) 元の問題をサイズの小さいいくつかの部分問題に分割 個々の部分問題を何らかの方法で解決 それらの解を統合することで元の問題の解を得る

69 11 84 63 76 91 53 97 41 2 28 31 58 19 12 88 53 69 69 11 84 84 63 97 97 76 91 91 12 53 41 84 2 28 28 31 63 58 97 19 88 88 41 69 11 58 91 76 12 53 2 31 88 19 41 76 28 63 12 58 11 31 2 19 2 11 12 19 28 31 41 53 58 63 69 76 84 88 91 97

マージソート (逐次処理, 201ページ) データの分割にかかる時間(2要素に分解) n/2 ソートにかかる時間(段数log2n, データ数n) 　　n log2n ステップ数は n/2 + n log2n つまり O(n log2n) 　　クイックソートと並ぶオーダーで処理ができる

マージソート (並列処理) データの分割にかかる時間(2要素に分解) log2n - 1 ソートにかかる時間 2n - 1 ステップ数は (log2n + 2n – 2) つまり O(n) 　　　例ではn=16なので34ステップで終了

69 11 84 63 76 91 53 97 41 2 28 31 58 19 12 88 53 69 69 11 84 84 63 97 97 76 91 91 12 53 41 84 2 28 28 31 63 58 97 19 88 88 41 69 11 58 91 76 12 53 2 31 88 19 41 76 28 63 12 58 11 31 2 19 2 11 12 19 28 31 41 53 58 63 69 76 84 88 91 97

パイプラインマージソート データの分割にかかる時間(図には書いてない） log2n - 1 最初のデータがソートされる時間 log2n 引き続くn-1個のデータがソートされる時間 　　　　n-1 ステップ数は (２ log2n + n-2) つまりO(n)である 　　例では、n=16 なので22ステップで終了