Download presentation
Presentation is loading. Please wait.
1
酒居敬一(sakai.keiichi@kochi-tech.ac.jp)
アルゴリズムとデータ構造1 2005年7月1日
2
待ち行列（FIFO） データ挿入 データ取得 待ち行列（データの挿入・取得）
3
待ち行列の配列による実現 データ挿入 データ取得 新しい要素を入れようとすると入らない →右へコピーして移動 →隙間を空ける
4
リングバッファ(46ページ) 配列の最初と最後を接続して環にしたもの ２つのポインタでデータの出し入れを管理 データの先頭を指すポインタ
head, front データの最後尾を指すポインタ tail, rear ２つのポインタが重なったらデータは空 領域の大きさをnとしたらポインタの位置はnとおり データの数が0からnまでn+1とおりある ポインタが重なったら、空か満杯の状態が重なる…
5
リングバッファ 挿入口 リア 環状のデータ格納領域 データの存在を示すポインタ 取り出し口 フロント
6
満杯になったとき、 リアとフロントのポインタが 重なってしまって 空と区別が付かない フロント フロント リア
7
配列を使用したリングバッファ 配列には始まりと終わりがある ポインタが終わりまで移動したら先頭へ戻る （フロント－リア）の演算でも境界を考慮
ラップラウンド処理 条件文で判定 配列の大きさを2のべき乗にする 配列のインデックスをビットごとのAND処理
8
データのおき場所は配列 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で管理
9
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の指すところがキューの先頭 先頭と最後尾が同じ場合は空 条件文でラップラウンド処理
10
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の指すところがキューの最後尾 先頭と最後尾が同じ場合は空 そうならないようにする判定が必須 条件文でラップラウンド処理
11
場合分けしてラップラウンド処理 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までの表示
12
マージソート(198ページ) 手続きf(p) 問題pを半分にする それぞれの部分問題に対して次の処理 半分にした問題をマージする
部分問題の要素数が2個 小さい順に並び替える→次の処理へ 部分問題の要素数が1個 並び替える必要が無い→次の処理へ 部分問題の要素数が2個より多い 手続きfを部分問題を引数に呼ぶ 半分にした問題をマージする 部分問題列の先頭から、小さい順に取り出す
13
分割統治法(162ページ) 元の問題をサイズの小さいいくつかの部分問題に分割 個々の部分問題を何らかの方法で解決
それらの解を統合することで元の問題の解を得る
14
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
15
マージソート (逐次処理, 201ページ) データの分割にかかる時間(2要素に分解) n/2
ソートにかかる時間(段数log2n, データ数n) n log2n ステップ数は n/2 + n log2n つまり O(n log2n) クイックソートと並ぶオーダーで処理ができる
16
マージソート (並列処理) データの分割にかかる時間(2要素に分解) log2n - 1 ソートにかかる時間 2n - 1
ステップ数は (log2n + 2n – 2) つまり O(n) 例ではn=16なので34ステップで終了
17
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
18
パイプラインマージソート データの分割にかかる時間(図には書いてない） log2n - 1 最初のデータがソートされる時間 log2n
引き続くn-1個のデータがソートされる時間 n-1 ステップ数は (２ log2n + n-2) つまりO(n)である 例では、n=16 なので22ステップで終了
Similar presentations
