x - Researchmap

情報工学概論
(アルゴリズムとデータ構造)
第6回
番兵 (Sentinel)
• プログラムを単純にするために用いるダミー
オブジェクト
void LIST_DELETE(dllist *L, lobj *x)
{
if (PREV(x) != NIL) NEXT(PREV(x)) = NEXT(x);
else
HEAD(L) = NEXT(x);
if (NEXT(x) != NIL) PREV(NEXT(x)) = PREV(x);
}
void LIST_DELETE2(dllist2 *L, lobj *x)
{
NEXT(PREV(x)) = NEXT(x);
PREV(NEXT(x)) = PREV(x);
}
2
双方向リストの構造体
• リストの要素 (以前と同じ)
typedef struct lobj {
struct lobj *prev; // 前の要素へのポインタ
struct lobj *next; // 後の要素へのポインタ
data key;
// キー
} lobj;
• 双方向リスト
typedef struct {
lobj *nil;
// NILを表す要素のポインタ
} dllist2;
3
データ構造の変更点
• リスト L は NIL を表現するオブジェクトを持つ
• 双方向リストをNILを含めた循環リストに変更
• 先頭要素は HEAD(L) = NEXT(NIL(L))
nil(L)
9
16
4
NIL
4
連結リストの探索
• LIST_SEARCH(L, k): リスト L に属する，キー k
を持つ最初の要素のポインタを返す
• キー k を持つ要素が存在しなければ NIL を返す
lobj *LIST_SEARCH(dllist2 *L, data k)
• (n) 時間
{
lobj *x;
x = HEAD(L);
while (x != NIL(L) && KEY(x) != k) {
x = NEXT(x);
}
return x;
nil(L)
}
9
16
4
5
連結リストへの挿入
• LIST_INSERT(L, x): x を L の先頭に挿入
– x のキーは既にセットされているとする
• O(1) 時間
x
nil(L)
void LIST_INSERT(dllist2 *L, lobj *x)
{
NEXT(x) = HEAD(L);
PREV(HEAD(L)) = x;
HEAD(L) = x;
PREV(x) = NIL(L);
}
9
9
16
4
16
4
6
リストによるスタック/キューの実現
• スタックの場合
– 先頭に追加，先頭から削除
– 一方向リストで実現可能
• キューの場合
–
–
–
–
末尾に追加，先頭から削除
削除は簡単
追加のためには，末尾へのポインタが必要
一方向リストで実現可能
• 全て O(1) 時間
7
11.3 ポインタとオブジェクトの実現
• オブジェクトは構造体やポインタを用いて表
現される
• Fortran 77のような言語で実現するにはどう
すればいいか
8
オブジェクトの多重配列表現
•
•
•
•
オブジェクトのフィールドごとに配列を用いる
ポインタの代わりに，配列の添字を用いる
0 は NIL ポインタを表す
変数 L はリストの先頭を表す
L
1
2
3
next
3
0
2
5
key
4
1
16
9
prev
5
2
7
0
7
4
5
6
7
8
9
オブジェクトの割り付けと開放
• 動的集合を表現する場合，新しいオブジェクト
を格納するメモリ領域が必要
• C言語では malloc や free を用いるが，これは
オーバーヘッドが大きい
• オブジェクトのサイズがすべて等しい場合に限
定して，割り付けと開放を実装する
10
• オブジェクトは多重配列で表現されているとする
• 配列の長さを m，現在表現されている動的集合の
サイズを n とする
• mn 個のオブジェクトは未使用 (free)
• 未使用オブジェクトを “未使用リスト” (free list) と
呼ばれる1方向リストとして管理する
L
1
7
2
3
4
5
6
7
8
8
3
0
key
4
1
16
9
prev
5
2
7
0
next
0
1
2
4
5
free
6
11
• 未使用リストでは，配列 next のみ用いる
• 未使用リストの先頭は大域変数 free_list が保持
• 各オブジェクトはリスト L か未使用リストのどちらか
に属する
L
1
7
2
3
4
5
6
7
8
8 free_list
3
0
key
4
1
16
9
prev
5
2
7
0
next
0
1
2
4
5
6
12
オブジェクトの割り付け
•
•
•
•
未使用リストをスタックとみなす
割り付けるオブジェクトはリストの先頭
開放したらリストの先頭に追加
int ALLOCATE_OBJECT(void)
O(1) 時間
{
int x;
if (free_list == NIL) {
printf("ERROR メモリ不足\n");
exit(1);
} else {
x = free_list;
free_list = NEXT(x);
return x;
}
}
13
オブジェクトの開放
• オブジェクト x を開放し，未使用リストの先頭に
追加
• O(1) 時間
• オブジェクトに next フィールドがない場合も，あ
るフィールドを next として用いてリストを表現
void FREE_OBJECT(int x)
{
NEXT(x) = free_list;
free_list = x;
}
14
メモリの初期化
• まず，すべてのオブジェクトを未使用リスト
に入れておく void INIT_MEMORY(int size)
{
int i;
prev = (int *)malloc((size+1)*sizeof(int));
next = (int *)malloc((size+1)*sizeof(int));
key = (data *)malloc((size+1)*sizeof(data));
if (prev == NULL || next == NULL || key == NULL) {
printf("ERROR メモリ不足\n");
exit(1);
}
for (i = 1; i < size; i++) {
NEXT(i) = i+1;
}
NEXT(size) = NIL;
free_list = 1; nil = NIL;
}
15
多重配列表現の欠点
• 多くの操作ではオブジェクト中の複数のフィールド
を読み書きする
– key, next, prev
• 多重配列表現では，CPUキャッシュが利きにくい
– 1つのオブジェクトがメモリ中で分断されているため
16
オブジェクトの単一配列表現
• 計算機のメモリは大きな配列とみなせる
– 0 番地から M1 番地
• オブジェクトはメモリのある連続した場所を占める
• ポインタはオブジェクトの占める場所の先頭番地を
指す
• 各フィールドは，ポインタにオフセットを加えたもの
で指される
L 13
A
key
next
prev
4
7 13
1
2
3
4
5
6
3
0
1
9
1
0
7
8
9 10 11 12 13 14 15
17
二分探索
• アルゴリズムとデータ構造で重要な概念
• 全順序集合の探索を高速化する
• 集合 S の要素を L, E, G に分ける
– L = {x | x  S, x < p} (p より小さい要素)
– E = {x | x  S, x = p} (p と等しい要素)
– G = {x | x  S, x > p} (p より大きい要素)
• k を探索するとき
– p = k ならば探索終了 (見つかった)
– p < k ならば G を二分探索
– p > k ならば L を二分探索
18
•
•
•
•
•
サイズ n の集合の二分探索の時間を T(n) とする
L, G のサイズを n1, n2 とする (n1+n2  n)
T(n) = O(1) + max{T(n1)+T(n2)}
n1  ½ n, n2  ½ n なら T(n) = O(1) + T(½ n)
T(n) = O(log n) となる
19
既ソート配列を用いた辞書
•
•
•
•
集合の要素を配列に格納するデータ構造
探索は二分探索を用いることができる
挿入はソート順を保つようにする必要がある
削除は未ソートの場合と同じ
• 集合の要素は全て異なるとする
20
既ソート配列での二分探索
•
•
•
•
•
•
•
•
E は配列の中央の要素 (p = S[n/2])
L は中央より左側の要素 (S[0..n/21])
G は中央より右側の要素 (S[n/2+1..n1])
集合が配列のl 番目からh 番目で表されているとき
m = (l+h) / 2 とする
S[m]=k ならば探索終了 (k が存在した)
S[m]<k ならば k はL, E には存在しない⇒G を探索
S[m]>k ならば k はG, E には存在しない⇒L を探索
l
<p
L
m
p
E
h
>p
G
21
int search(dic_sortedarray *S, int k)
{
int i;
int high, low, mid;
low = 0;
// 探索の範囲は最初は配列全体 [0..n-1]
high = S->n-1;
i = 0;
while (low <= high) {
mid = (low + high) / 2;
if (S->key[mid] == k) {
return mid;
} else if (S->key[mid] < k) {
low = mid + 1;
i = mid + 1;
} else {
high = mid - 1;
i = mid;
}
}
return -(i+1); // 見つからなかったときに挿入する場所を返す
}
22
• l > h になったら探索終了 (見つからなかった)
• その直前では l = h = m
• S[m] = p < k だったとき
m
p
>k
k はここに入る
• S[m] = p > k だったとき
<k
m
p
k はここに入る
23
要素の挿入
•
•
•
•
•
k が既に存在するなら挿入しない
k を探索し，挿入場所 i を求める
i から配列の最後までの要素を右に1つずらす
空いたところに k を入れる
O(n) 時間
void insert(dic_sortedarray *S,int k)
{int i,j;
i = search(S, k); if (i >= 0) return;
if (S->n+1 > S->MAX) {
printf("ERROR 配列のオーバーフロー\n");
exit(1);}
i = -i-1;
for (j = S->n; j > i; j--) {S->key[j] = S->key[j-1];}
S->key[i] = k;
S->n = S->n + 1;
24
}
既ソート配列を用いた辞書のまとめ
• 探索： O(log n) 時間
• 挿入: O(n) 時間
• 削除: O(n) 時間
• 初めに指定したサイズのメモリを常に使用する
• それより多い数の要素は格納できない
25
9.1 ソーティングの下界
• ソーティングの入力：〈a1, a2, ..., an〉
• 比較ソートでは要素間の比較のみを用いて
ソートを行う
• 2つの要素 ai, aj が与えられたとき，それらの相
対的な順序を決定するためにテストを行う
– ai aj, ai aj, ai aj, ai aj, ai aj のみ
• これ以外の方法では要素のテストはできない
26
仮定
• すべての入力要素は異なると仮定する
– ai aj という比較は行わないと仮定できる
• ai aj, ai aj, ai aj, ai aj は全て等価
• 全ての比較は ai aj という形と仮定できる
27
決定木モデル
• 比較ソートは決定木 (decision tree) とみなせる
• 決定木はソーティングアルゴリズムで実行される
比較を表現している
• アルゴリズム中における制御，データの移動など
の要因は無視する
28
5,4,3
2,4,1
2,4,1
a1 : a2

入力：数の列
各ノードでは ai  aj
の比較を行う
 5,4,3
a2 : a3

a1 : a3

2,4,1
a1 : a3
a1, a2, a3



a2, a1, a3
a1, a3, a2 a3, a1, a2
1,2,4
葉は入力の置換に対応
5,4,3
a2 : a3


a2, a3, a1 a3, a2, a1
3,4,5
29
決定木の高さと比較回数
• 決定木はソートアルゴリズム A から決まる
• 入力数列を与えると決定木の対応する葉が決まる
• 根から葉までのパスの長さ
＝Aを実行する際の比較回数
• 根から葉までのパス長の最大値
＝実行されるソートアルゴリズムの最悪比較回数
• 比較ソートでの最悪の比較回数は決定木の高さに
対応
30
最悪時の下界
• 決定木の高さの下界＝任意の比較ソートアルゴ
リズムの実行時間の下界
定理 9.1 n 要素をソートするどんな決定木の高さも
(n lg n)
証明 n 要素をソートする高さ h の決定木を考える．
ソートを正しく行うには，n 要素の n! 通りの置換全
てが葉に現れなければならない．
高さ h の2分木の葉の数は高々 2h. よって
n!  2h ではソートできない. つまり h  lg(n!) 31
h  lg( n!)
Stirling
n
n!  
e
n
の公式よりn! 2n  e 
n

 1 
1    
 n 

n
n
n
h  lg  
e
 n lg n  n lg e
 (n lg n)
32

Download Report