アルゴリズムとデータ構造1

アルゴリズムとデータ構造1
2005年7月1日
酒居敬一([email protected])
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処理
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
private
private
private
•front, rearというポインタで管理
•キューの容量はmaxSizeで管理
int front;
int maxSize;
Object[] queueArray;
int rear;
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;
•frontの指すところがキューの先頭
}
•先頭と最後尾が同じ場合は空
return dequedObject;
}
•条件文でラップラウンド処理
public boolean isEmpty()
{
return (this.rear == this.front);
}
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;
}
•rearの指すところがキューの最後尾
return true;
•先頭と最後尾が同じ場合は空
}
•そうならないようにする判定が必須
•条件文でラップラウンド処理
public boolean isFull()
{
return ((this.rear + 1) == this.front);
}
public void printAll()
{
System.out.println("待ち行列の内容");
if(this.isEmpty()){
System.out.println();
•場合分けしてラップラウンド処理
return;
•frontから配列終わりまでの表示
}
int count = 1;
•配列先頭からrearまでの表示
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;
while(position < limit){
System.out.println(count +"\t" + this.queueArray[position]);
++count;
++position;
}
System.out.println();
}
マージソート(198ページ)
手続きf(p)
• 問題pを半分にする
それぞれの部分問題に対して次の処理
– 部分問題の要素数が2個
• 小さい順に並び替える→次の処理へ
– 部分問題の要素数が1個
• 並び替える必要が無い→次の処理へ
– 部分問題の要素数が2個より多い
• 手続きfを部分問題を引数に呼ぶ
• 半分にした問題をマージする
– 部分問題列の先頭から、小さい順に取り出す
分割統治法(162ページ)
• 元の問題をサイズの小さいいくつかの部
分問題に分割
• 個々の部分問題を何らかの方法で解決
• それらの解を統合することで元の問題の
解を得る
53 12 41 69 11
2
84 28 31 63 97 58 76 19 91 88
53 69 69
11 84 84
63 97 97
12 53 41 84
2
31 63 58 97 19 88 88
2
28 28
76 91 91
41
69
11
58
91
76
12
53
2
31
88
19
11
41
76
28
63
12
58
11
31
2
19
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ステップで終了
53 12 41 69 11
2
84 28 31 63 97 58 76 19 91 88
53 69 69
11 84 84
63 97 97
12 53 41 84
2
31 63 58 97 19 88 88
2
28 28
76 91 91
41
69
11
58
91
76
12
53
2
31
88
19
11
41
76
28
63
12
58
11
31
2
19
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ステップで終了

Download Report