n - Researchmap

情報工学概論
(アルゴリズムとデータ構造)
第2回
実習用環境
• C言語
– 学習用Ｃ言語開発環境
http://9cguide.appspot.com/
• Fortran 90
– Self-extracting Windows x86
http://www.g95.org/downloads.shtml
http://ftp.g95.org/g95-MinGW.exe
2
アルゴリズムの設計
• 挿入ソート: 逐次添加法 (incremental approach)
• 分割統治法 (divide-and-conquer) に基づく方法
→マージソート
– 実行時間の解析が容易であることが多い
3
分割統治法
•
問題の再帰的な (recursive) 構造を利用
分割：問題をいくつかの小さな部分問題に分割
統治：各部分問題を再帰的に解く
統合：それらの解を組合わせて元の問題の解を構成
– マージソートでは
分割： n 要素の列を n/2 要素の2つの部分列に分割
統治：マージソートを用いて2つの部分列をソート
統合：2つのソートされた部分列を統合して答を得る
4
マージソート
void MERGE_SORT(data *A, int p, int r, data *B)
{
int q;
// A[p..r] をソート
if (p < r) {
// p==r ならソートする必要なし
q = (p+r)/2;
MERGE_SORT(A, p, q, B); // A[p..q] を再帰的にソート
MERGE_SORT(A, q+1, r, B); // A[q+1..r] を再帰的にソート
MERGE(A, p, q, r, B); // ソートされた部分列 A[p..q] と A[q+1..r] を統合
}
}
5
1
2
2
3
4
5
6
6
マージ
2
4
5
6
1
5
4
マージ
5
6
1
6
4
3
2
マージ
マージ
2
3
マージ
マージ
2
2
6
1
6
マージ
3
2
6
6
マージ
• 一時的な配列 B[0,n-1] を用いる
void MERGE(data *A, int p, int q, int r, data *B)
{ // ソートされた部分列 A[p..q] と A[q+1..r] を統合
int i,j,k;
data t;
k = p; i = p; j = q+1;
while (k <= r) {
if (j > r) t = A[i++];
// 前半のみにデータがある
else if (i > q) t = A[j++];
// 後半のみにデータがある
else if (A[i] <= A[j]) t = A[i++]; // 前半のほうが小さい
else t = A[j++];
// 後半のほうが小さい
B[k++] = t;
// 一時的な配列に保存
}
for (i=p; i<=r; i++) A[i] = B[i]; // 元の配列に書き戻す
}
7
void MERGE_SORT(data *A, int p, int r, data *B) // A[p..r] をソート
{
int q;
if (p < r) {
// p==r ならソートする必要なし
q = (p+r)/2;
MERGE_SORT(A, p, q, B); // A[p..q] を再帰的にソート
MERGE_SORT(A, q+1, r, B); // A[q+1..r] を再帰的にソート
MERGE(A, p, q, r, B); // ソートされた部分列 A[p..q] と A[q+1..r] を統合
}
}
int main(int argc, char *argv[])
{
data A[14] = {27,17,3,16,13,10,1,5,7,12,4,8,9,0};
data B[14];
int i,n;
n = 14;
MERGE_SORT(A,0,n-1,B);
for (i=0;i<n;i++) printf("%d ",A[i]);
printf("\n");
}
8
Rubyの場合
def merge(a, b)
x = []
i=0
j=0
while i < a.length do
if j == b.length then
x << a[i]
i=i+1
elsif a[i] < b[j] then
x << a[i]
i=i+1
else
x << b[j]
j=j+1
end
end
x.concat(b[j..-1])
return x
end
def merge_sort(a)
n = a.length
if n == 1 then
return [a[0]]
else
return merge(merge_sort(a[0..n/2-1]),
merge_sort(a[n/2..-1]))
end
end
a = [27,17,3,16,13,10,1,5,7,12,4,8,9,0]
b = merge_sort(a)
pb
9
Fortran 90の場合
program main
integer a(14)
integer b(size(a))
a = (/ 27,17,3,16,13,10,1,5,7,12,4,8,9,0 /)
print *, "a = ", a
print *, "merge sort"
call mergesort(a, lbound(a,1), ubound(a,1), b)
print *, "a = ", a
contains
recursive subroutine mergesort(a, p, r, b)
integer a(:), b(:)
integer p, r
integer q
if (p < r) then
q = (p+r)/2
call mergesort(a, p, q, b)
call mergesort(a, q+1, r, b)
call merge(a, p, q, r, b)
end if
end subroutine mergesort
subroutine merge(a, p, q, r, b)
integer a(:), b(:)
integer p, r, q, i, j, k
integer t
k = p; i = p; j = q+1
do
if (.not. (k <= r)) exit
if (j > r) then
t = a(i); i = i+1
else if (i > q) then
t = a(j); j = j+1
else if (a(i) <= a(j)) then
t = a(i); i = i+1
else
t = a(j); j = j+1
end if
b(k) = t; k = k+1
end do
do i = p, r
a(i) = b(i)
end do
end subroutine merge
end program main
10
分割統治アルゴリズムの解析
• 全体の実行時間は問題のサイズに関する漸化式
(recurrence) で記述できることが多い
• サイズ n の問題に関する実行時間を T(n) とする
• n  c (ある定数) ならば定数時間((1))
• 問題を a 個の部分問題に分割し, それぞれが元の
サイズの 1/b 倍になったとすると
(1)
n  cのとき

T ( n)  
aT (n / b)  D(n)  C (n) それ以外
D(n), C(n): 問題の分割, 統合にかかる時間
11
マージソートの解析
• n は2のべき乗と仮定する
• n=1のとき T(n) = (1)
• n>1のとき
– 分割： D(n) = (1)
– 統治：再帰的にサイズn/2の部分問題を解く
2T(n/2)
– 統合：MERGEは C(n) = (n)
(1)
n  1のとき

T ( n)  
2T (n / 2)  (n) n  1のとき
T(n)= (n lg n) となる
12
アルゴリズムの重要性
• コンピュータが速くても, 実行時間のオーダが
大きいアルゴリズムは役に立たない
• スーパーコンピュータで挿入ソートを実行
– 1秒間に1億命令実行
– 2n2 命令必要
• パーソナルコンピュータでマージソートを実行
– 1秒間に100万命令実行
– 50 n lg n 命令必要
13
• 100万個の数の配列のソート
• ス－パーコンピュータで挿入ソート
2  (106 ) 2 命令
 20,000秒  5.56時間
8
10 命令 / 秒
• パーソナルコンピュータでマージソート
50 106 lg 106 命令
 1,000秒  16.67分
6
10 命令 / 秒
• オーダの低いアルゴリズムの開発が重要
14
今までのソーティングアルゴリズム
1. 挿入ソート： (n2) 時間だが，入力サイズが
小さいときには高速．in-place
2. マージソート： (n lg n) 時間だが，実行には
一時的な配列が必要
15
新しいソーティングアルゴリズム
1. ヒープソート： (n lg n) 時間, in-place.
2. クイックソート：最悪 (n2) 時間だが平均実行
時間は(n lg n)．実際上は高速．in-place.
16
クイックソート
• n 個の数に対して最悪実行時間(n2)のソーティ
ングアルゴリズム
• 平均実行時間は(n log n)
• 記法に隠された定数も小さい
• in-place (一時的な配列が必要ない)
17
クイックソートの記述
• 分割統治法に基づく
• 部分配列 A[p..r] のソーティング
1. 部分問題への分割:
–
–
–
配列 A[p..r] を2つの部分配列 A[p..q] と A[q+1..r]
に再配置する．
A[p..q] のどの要素も A[q+1..r] の要素以下にする．
添字 q はこの分割手続きの中で計算する．
2. 部分問題の解決 (統治):
•
部分配列 A[p..q] と A[q+1..r] を再帰的にソート
3. 部分問題の統合
•
18
A[p..r] はすでにソートされているので何もしない
クイックソートのコード
void QUICKSORT(data *A, int p, int r)
{
int q;
if (p < r) {
q = PARTITION(A,p,r);
QUICKSORT(A,p,q);
QUICKSORT(A,q+1,r);
}
}
main()
{
QUICKSORT(A,0,n-1);
}
19
def quick_sort(a)
Rubyの場合
n = a.length
注：これはin-placeではない
if n <= 1 then
（一時的に余分な記憶領域が必要）
return a
else
pivot = a[0]
less = a.select{|x| x < pivot}
equal = a.select{|x| x == pivot}
greater = a.select{|x| x > pivot}
return quick_sort(less) + equal + quick_sort(greater)
end
end
a = [27,17,3,16,13,10,1,5,7,12,4,8,9,0]
b = quick_sort(a)
pb
20
配列の分割
int PARTITION(data *A, int p, int r) // O(n) 時間
{
int q, i, j;
data x, tmp;
x = A[p];
i = p-1; j = r+1;
while (1) {
do {j = j-1;} while (A[j] > x);
do {i = i+1;} while (A[i] < x);
if (i < j) {
tmp = A[i]; A[i] = A[j]; A[j] = tmp;
} else {
return j;
}
}
}
21
A[p..r]
5 3 2 6 4 1 3 7
i
j
5 3 2 6 4 1 3 7
i
A[i]  x
A[j]  x となる最初の i, j
7 は正しい分割位置にある
j
3 3 2 6 4 1 5 7
i
初期状態：
i と j は配列の範囲外
x = A[p] = 5 によって分割
x: 枢軸 (pivot) と呼ぶ
j
A[i] と A[j] を交換
正しい分割位置になる
22
3 3 2 6 4 1 5 7
i
j
3 3 2 1 4 6 5 7
i
A[i]  x
A[j]  x となる最初の i, j
A[i] と A[j] を交換
j
3 3 2 1 4 6 5 7
j i
i  j となったので
q = j を返す
A[p..q] は x 以下
A[q+1..r] は x 以上
23
Fortran 90の場合
program main
integer a(14)
a = (/ 27,17,3,16,13,10,1,5,7,12,4,8,9,0 /)
print *, "a = ", a
print *, "quick sort"
call quicksort(a, lbound(a,1), ubound(a,1))
print *, "a = ", a
contains
recursive subroutine quicksort(a, p, r)
integer a(:)
integer p, r, q
if (p < r) then
q = partition(a,p,r)
call quicksort(a,p,q)
call quicksort(a,q+1,r)
end if
end subroutine quicksort
function partition(a, p, r)
integer a(:)
integer p, r, q, i, j
integer x, tmp
x = a(p)
i = p-1; j = r+1
do
do
j = j-1
if (.not. (a(j) > x)) exit
end do
do
i = i+1
if (.not. (a(i) < x)) exit
end do
if (i < j) then
tmp = a(i); a(i) = a(j); a(j) = tmp
else
partition = j
exit
end if
end do
end function
end program main
24
PARTITIONの正当性
• PARTITIONの返り値を q とする
• A[p..r] の分割後に満たされるべき条件
– A[p..q] はある pivot x 以下
– A[q+1..r] は x 以上
–pq<r
• q = r となると，QUICKSORTは停止しないため，
どんな A に対しても q < r となることを保障する
必要がある
25
• 初期状態は i < j
• do {j = j-1;} while (A[j] > x);
do {i = i+1;} while (A[i] < x); の終了後
–
–
–
–
p  i, j  r
A[j+1..r] は x 以上
A[p..i-1] は x 以下
A[i]  x  A[j]
• i < j のとき，A[i] と A[j] を交換すると
– A[j..r] は x 以上
– A[p..i] は x 以下
• i  j のとき q = j
26
• PARTITIONの終了時に q = j = r とする
– while (1) のループを実行する毎に j は1以上減る
– 終了時に j = r ならばこのループは1度しか実行され
ていない
– しかし1回目のループでは x = A[p] なので i = p
• PARTITIONは p < r の場合のみ呼ばれるので，
1回目のループでは p = i < j = r
• つまり1回目のループでは終了しない
• よってPARTITION終了時に q = r とはならない．
つまり q < r
27
8.2 クイックソートの性能
• クイックソートの実行時間は分割が平均化さ
れているかどうかに依存
• これはpivotの選択に依存
• 分割が平均化されていれば実行時間は漸近
的にマージソートと同じ ((n log n))
• 最悪時は (n2)
28
最悪の分割
• 最悪の場合は，PARTITIONによって領域が
1 要素と n-1 要素に分けられる場合
• 分割には (n) 時間かかる
• 実行時間に対する漸化式は
– T(n) = T(n1) + (n), T(1) = (1)
• T(n) = (n2)
• 最悪実行時間は挿入ソートと同じ
• 入力が完全にソートされているときに起こる
(挿入ソートなら O(n) 時間)
29
n
n
n 1
1
n 1
n2
1
1
n
n
n2
n 3

3
2
2
1
再帰木
1
 
Total :  n
2
30
最良の分割
• クイックソートが最も速く動作するのは，
PARTITIONによってサイズ n/2 の2つの領域
に分割されるとき.
• T(n) = 2T(n/2) + (n)
• T(n) = (n lg n)
• ちょうど半分に分割される場合が最速
31
n
n
n
2
n
2
n
4
n
4
n
4
n
n
4
n
lg n
n n n n n n n n
8 8 8 8 8 8 8 8
n

n
Total : nlg n
32
平衡分割
• PARTITIONで常に 9 対 1 の比で分割されると
仮定する
• T(n) = T(9n/10) + T(n/10) + (n)
• 再帰木の各レベルのコストは O(n)
• 再帰の深さは log 109 n  lg n 
• 漸近的には中央で分割するのと同じ
• 分割の比が 99 対 1 でも同じ (定数比なら良い)
33

Download Report