情報科学(5) アルゴリズムと計算量 1 復習: 問題解決とアルゴリズム (cf. 「情報」6.1.1) • コンピュータによる問題解決ではアルゴリズ ムが重要になる アルゴリズム プログラム いきなりプログラムを書くことはまれ 問題 モデル ※問題: 例: 銀行 オンラインシステム コンピュータにやらせたいこと全般 計算問題から、長期間のサービスまで ※モデル: 問題を抽象化したもの 2 アルゴリズムとは • 9世紀の数学者al-Khwarizmiの名に因む • 問題を解くための手順 答えが出るかどうか分から ないものはアルゴリズムと 有限の手順で答えを出すもの は言わない。cf. コラッツ予 想 曖昧さが(あまり)ない 特定のプログラミング言語に依らない コンピュータに実行させるとは限らない • 問題の例 「整数xが素数かどうかを判定する」 「整数xとyの最大公約数を求める」 3 アルゴリズムの役割 • 時間やメモリに関する性質を考えることができる 良し悪しが分かる → 計算量 (後述) • 具体的な問題と独立して考えることができる 問題における細かな点を無視して、解法の重要な点だけ を考える 異なる問題も同じアルゴリズムで解ける場合がある • 具体的なプログラムと独立して考えることができる プログラムにおける細かな点を無視して考えられる 特定のプログラミング言語に依らない 4 1つの問題に 複数のアルゴリズムがあり得る • アルゴリズムが違えば計算時間も変わる • プログラミング・テクニックによる速度の違いよりも大きいこと が多い • 例: 高速フーリエ変換 (CooleyとTukeyが1965年に再発明) 周期関数を周波数成分に分解する アルゴリズム • 単純な方法では成分数Nの2乗に 比例する時間がかかるところを、 このアルゴリズムではN×log(N)に 比例する時間で済ませられる 類似アルゴリズムである離散コサイ ン変換は、音声や映像の圧縮・信号 処理などに幅広く使われている © NDTnet - [email protected] 5 アルゴリズムによる 実行時間の違い • アルゴリズムによる計算時間の違いを実際の プログラミングによって調べる • 問題とアルゴリズム: 平方根の計算: 数え上げ/二分法/ニュートン法 ――すでに見た フィボナッチ数: 定義通り/数え上げ/行列 最大公約数: 単純なもの/ユークリッドの互除法 整列: 単純ソート/併合ソート/ビンソート 6 フィボナッチ数の計算 • 問題: フィボナッチ数列のx番目の数を求める フィボナッチ数列: 1,1,2,3,5,8,13,21,34,… x番目をfxと書くと fx =fx−1 + fx−2 となる数列 ただし f0 = f1 = 1 • アルゴリズム 定義通りに計算する方法 0から順に数え上げる方法 行列を用いる方法 15 Ruby 定義通りに計算する フィボナッチ数 • 定義: x番目をfxと書くとき fx =fx−1 + fx−2 ただし f0 = f1 = 1 • fxをメソッドfib1(x) にすればよい • 計算時間は? def fib1(x) if x==0 || x==1 then 1 else fib1(x-1)+fib1(x-2) end end 16 0から順に数え上げる フィボナッチ数の計算 考え方: • 状態: (i,fi,fi+1) • 初期値: (0,1,1) • 遷移: (i, fi, fi+1) → (i+1, fi+1, fi+fi+1) • 終了条件: i=xになるまで 例: (0,1,1) → +1 + (1,1,2) → +1 + (2,2,3) → (3,3,5) → (4,5,8) → (5,8,13) → (6,13,21) → (7,21,34) →... 17 Ruby 0から順に数え上げる フィボナッチ数の計算 def fib2(x) i=0; fi=1; fi1=1 while i < x i = i+1 f2 = fi+fi1 fi = fi1 fi1 = f2 end fi end (i,fi,fi+1)に対応 i=xになるまでの繰り返し (i,fi,fi+1)から (i+1,fi+1,fi+2)を作る f2が必要な理由は何 か(考えてみよ) i=xになったときのfiが答え • 計算時間は? 18 行列を用いるフィボナッチ数の計算法 (1) • (fx+1, fx)をベクトルだと思うと f x1 1 1 f x f x 1 0 f x1 x x 1 1 f1 1 1 1 1 0 f 0 1 0 1 という関係がある 20 行列を用いるフィボナッチ数の計算法 (2) x f x1 1 1 1 x 1 Q 1 f x 1 0 1 • Qxを高速に計算する方法はあるか? • Q2x=(Qx)2という関係を利用する 例: Q16=(Q8)2=((Q4)2)2=((Q2)2)2)2 ―― 2乗を4回 ( x 0) E x/2 2 x Q (Q ) ( x is even) Q(Q x1 ) ( x is odd) 21 Ruby 行列を用いる フィボナッチ数の計算法 (3) def power(q,n) E 単位行列 x/2 2 if n==0 then x ) 偶数ならば真 Q (Q E Q(Q x1 ) elsif is_even(n) then square(power(q, n/2)) else 行列の自乗 mat_x_mat(power(q, n-1), q) end 行列×行列 end 行列×ベクトル Q行列 ( x 0) ( x is even) ( x is odd) (1,1)ベクトル def fib3(n) mat_x_vec(power(Q, n), F01).y end ベクトルの第2成分のとり出し ※この色の定義は 省略されている 22 フィボナッチ数の計算: アルゴリズムの違い fib(7) fib(8) • 定義通り fib(10) fib(9) fib(7) fib(8) fib(7) • 数え上げ fib(6) fib(6) fib(5) fib(6) fib(5) fib(6) fib(5) fib(4) (0,1,1) (1,2,1) (2,3,2) (3,5,3) (4,8,5) (5,13,8) • 行列を使う 100 Q100 80 60 Q50 40 20 Q24 Q25 0 Q6 Q12 Q3 Q2 Q1 -0.5 Q0 23 最大公約数の計算 • 問題: xとyの最大公約数を求める (x<yとする) 応用例: 公開鍵暗号系において大きな素数から 鍵を生成する際に用いられる xやyは約500ビット(=約150桁)の数 • アルゴリズム 単純: 1,2,...,xでxとyを割り切る最大数を見つける ユークリッドの互除法 24 Ruby • 単純な 最大公約数の計算 アルゴリズム: 1,2,...,xでyを割り切る最大の数を見つける def gcd_simple(x,y) nがxとyの約数のときtrue n = x while !common_divisor(n,x,y) n = n - 1 end n end 25 ユークリッドの互除法 • アルゴリズム: 小さい方で大きい方を割った余りで大きい方を置 き換える gがxとyの最大公約数ならxと(y mod x)の最大公 約数もgになるという性質を利用 • 考え方: 「0とyの最大公約数」 = y 「xとyの最大公約数」= 「zとxの最大公約数」 ただしzはyをxで割った余り 26 Ruby ユークリッドの互除法 • 考え方: 「0とyの最大公約数」 = y 「xとyの最大公約数」 = 「zとxの最大公約数」 ただしzはyをxで 割った余り def euclid(x,y) if x == 0 then y else euclid(y % x, x) end end 27 整列 (sorting) • 問題: n個のデータを大きさ順に並べる (単純化): n個の整数を小さい順に並べる 色々な場面で使われる データの「下ごしらえ」としても使われる 例: 検索を高速化するために整列しておく • データ数は、時として非常に大きくなる 「全学生の氏名を学生証番号順に表示」 「『今日の料理』という言葉を持つページを信頼度順に表 示」 28 整列アルゴリズム とても沢山ある • 単純整列法: 1番小さいものを見つけ、2番目に小さ いものを見つけ、... • 併合整列法: • ビン整列法: • クイック整列法: (名前だけ) 29 単純整列法 • 方法: 列の中で最小の数を見つけ、それを順に置き、 列から取り除く • 考え方: 「aを整列した列」 = 空 (aは空) minに「a’を整列した列」をつなげた列 (aは非空) ただしminはa中の最小の数、 a’はaからminを取り除いた列 30 Ruby 単純整列法 # aのi番目とj番目を交換 def swap(a,i,j) ai = a[i]; aj = a[j] a[i] = aj; a[j] = ai end # aのi番目以降の最小の要素を見つけ、 # その添字を返す def find_minimum(a,i) min_value = a[i] # 暫定最小値 min_index = i # その添字 for j in (i+1)..(a.size-1) if a[j] < min_value then min_value = a[j] # 新たな最小値 min_index = j # を発見した end # 場合 end min_index # 添字を返す end # 本体: 先頭から順に最小要素を移動 def sort(a) for i in 0..(a.size-1) min_index = find_minimum(a,i) swap(a, i, min_index) end a end 31 Ruby def sort(a) n = a.size for i in 0..n-1 for j in i+1..n-1 def random(n) if a[j] < a[i] a = Array.new(n) w = a[i] for i in 0..n-1 a[i] = a[j] a[i] = rand(n) a[j] = w end end a end end end a end 33 Ruby def sort(a) n = a.size for i in 0..n-1 for j in i+1..n-1 def random(n) if a[j] < a[i] a = Array.new(n) a[i],a[j] = for i in 0..n-1 a[j],a[i] a[i] = rand(n) end end end a end end a end 34 併合整列法 未整列 整列済 • 方法: 1つの列を2つに分ける操作を繰り返し、長さ1になるまで 続ける 分けた列をそれぞれ併合してゆき、1つの列になるまで続 ける • 部分問題: 整列済の2つの列を併合する 1つの列を2つに分ける 35 併合整列法: 整列済の列の併合 • 方法: 2つの列の先頭を比べ、小さい方を取って並べる どちらかが空になるまで続ける • 考え方: 「leftとrightを併合した列」 = left (rightが空) right (leftが空) l::「leftの後ろとrightを併合した列」 (l<r) r::「leftとrightの後ろを併合した列」 (それ以外) ただしleft,rightの先頭をl,rとする 36 併合整列法: 列を2つに分ける • 方法: 列の奇数番目を右の列、偶数番目を左の列に並べてゆく • 考え方: 「lを分割してleft,rightに加えたもの」 = left, rightが分割 (lが長さ0) 「空を分割して(x1をleftに加えたもの), (lが長さ1) rightに加えたもの」 「l’を分割して(x1をleftに加えたもの), (それ以外) (x2をrightに加えたもの)に加えたもの」 ただしlの先頭、2番目、それ以降をx1,x2,l’とする 37 併合整列法 • 方法: 列を分割して、それぞれを併合整列したものを併合する • 考え方: 「lの整列」= l (lの長さが0または1) 「lを分割して『空』,『空』に加えたもの」 (それ以外) 「lを分割してleft,rightに加えたもの」 = 「「leftの整列」と「rightの整列」を併合」 (lが長さ0) 「空を分割して(x1をleftに加えたもの), (lが長さ1) rightに加えたもの」 「l’を分割して(x1をleftに加えたもの), (それ以外) (x2をrightに加えたもの)に加えたもの」 ただしlの先頭、2番目、それ以降をx1,x2,l’とする 木構造を使う方法もある 38 Ruby 併合整列法(木を作る) Tree = Struct.new(:left, :right) def divide(a,i_min,i_max) if i_min == i_max a[i_min] else mid = (i_min+i_max)/2 Tree.new(divide(a,i_min,mid), divide(a,mid+1,i_max)) end end 39 divide([3,1,4,1,5,9],0,5) 9 4 3 1 1 5 40 divide([3,1,4,1,5,9],0,5) divide(a,0,5) divide(a,0,2) divide(a,3,5) divide(a,0,1) divide(a,2,2) divide(a,3,4) divide(a,5,5) 4 9 divide(a,0,0) divide(a,1,1) divide(a,3,3) divide(a,4,4) 3 1 1 5 41 Ruby def merge(left,right) merged = Array.new() while left.size > 0 || right.size > 0 merged.push( if right.size == 0 left.shift elsif left.size == 0 right.shift elsif left[0]<right[0] left.shift else right.shift end ) end merged end 併合整列法 (木を併合する) def merge_tree(tree) if tree.instance_of?(Tree) merge(merge_tree(tree.left), merge_tree(tree.right)) else [tree] end end def merge_sort(a) merge_tree(divide(a,0,a.size-1)) end 42 Ruby a = [3,1,4,1,5,9] a.push(2) a.shift def merge(left,right) merged = Array.new() while left.size > 0 || right.size > 0 if right.size == 0 x = left.shift elsif left.size == 0 x = right.shift elsif left[0]<right[0] x = left.shift else x = right.shift end merged.push(x) end merged end 43 Ruby merge([1,3,4],[1,5,9]) merged: [] left: [1,3,4] right: [1,5,9] def merge(left,right) merged = Array.new() while left.size > 0 || right.size > 0 if right.size == 0 x = left.shift elsif left.size == 0 x = right.shift elsif left[0]<right[0] x = left.shift else x = right.shift end merged.push(x) end merged end 44 Ruby merge([1,3,4],[1,5,9]) merged: [1] left: [1,3,4] right: [5,9] def merge(left,right) merged = Array.new() while left.size > 0 || right.size > 0 if right.size == 0 x = left.shift elsif left.size == 0 x = right.shift elsif left[0]<right[0] x = left.shift else x = right.shift end merged.push(x) end merged end 45 Ruby merge([1,3,4],[1,5,9]) merged: [1,1] left: [3,4] right: [5,9] def merge(left,right) merged = Array.new() while left.size > 0 || right.size > 0 if right.size == 0 x = left.shift elsif left.size == 0 x = right.shift elsif left[0]<right[0] x = left.shift else x = right.shift end merged.push(x) end merged end 46 Ruby merge([1,3,4],[1,5,9]) merged: [1,1,3] left: [4] right: [5,9] def merge(left,right) merged = Array.new() while left.size > 0 || right.size > 0 if right.size == 0 x = left.shift elsif left.size == 0 x = right.shift elsif left[0]<right[0] x = left.shift else x = right.shift end merged.push(x) end merged end 47 Ruby merge([1,3,4],[1,5,9]) merged: [1,1,3,4] left: [] right: [5,9] def merge(left,right) merged = Array.new() while left.size > 0 || right.size > 0 if right.size == 0 x = left.shift elsif left.size == 0 x = right.shift elsif left[0]<right[0] x = left.shift else x = right.shift end merged.push(x) end merged end 48 Ruby merge([1,3,4],[1,5,9]) merged: [1,1,3,4,5] left: [] right: [9] def merge(left,right) merged = Array.new() while left.size > 0 || right.size > 0 if right.size == 0 x = left.shift elsif left.size == 0 x = right.shift elsif left[0]<right[0] x = left.shift else x = right.shift end merged.push(x) end merged end 49 Ruby merge([1,3,4],[1,5,9]) merged: [1,1,3,4,5,9] left: [] right: [] def merge(left,right) merged = Array.new() while left.size > 0 || right.size > 0 if right.size == 0 x = left.shift elsif left.size == 0 x = right.shift elsif left[0]<right[0] x = left.shift else x = right.shift end merged.push(x) end merged end 50 def merge_tree(tree) if tree.instance_of?(Tree) merge(merge_tree(tree.left),merge_tree(tree.right)) else [tree] end end 9 4 3 1 1 5 merge_tree(divide([3,1,4,1,5,9],0,5)) 51 merge_tree(divide([3,1,4,1,5,9],0,5)) 9 4 3 1 1 5 52 merge_tree(divide([3,1,4,1,5,9],0,5)) [1,1,3,4,5,9] [1,3,4] [1,5,9] [1,3] [1,5] [9] [4] [3] [1] [1] [5] 53 Ruby 時間の計測 begin t = Process.times.utime sort(random(1000)) Process.times.utime - t end 54 ビン整列法 • 考え方 頻度分布(ヒストグラム)を作る 各値の頻度だけ値を並べる 頻度→ ← ← 値 値 添字→ 添字→ 55 ビン整列法 1. 大きな配列を用意 し、全て0にしておく 2. 列の各要素xにつ いて、配列のx番目 を1増やす 3. 配列を順に調べ、x 番目がnならばxをn 個並べる 93146431394873312 0123456789 0000000000 0123456789 0315301112 11123333344467899 56 Ruby ビン整列法 結果を格納する配列 値の出現回数を数える 全ての値vに ついて def rebuild(a,counts) i=0 小さい順に 配列を出現回数で再構成 def count_occurences(a) counts = Array.new(Max, 0) for i in 0..(a.size-1) counts[a[i]] = counts[a[i]]+1 end counts aの全要素に end ついて a[i]の出現 回数を増やす 配列を返す 再構成される配列の添字 for v in 0..(Max-1) for k in 0..(counts[v]-1) a[i] = v i = i+1 vの出現回数だけ end end end aにvを書き込む def bin_sort(a) 配列aの整列 rebuild(a, count_occurences(a)) aをaの a end 出現回数で 再構成 57 課題: アルゴリズムによる速度差の 実測 • 平方根・整列の複数のアルゴリズムに対応し たプログラムを作り、速度の違いを調べる 平方根の場合: x/δの大きさによって時間がどう 変化するかをグラフを描いてみる。1秒間に何回 計算できるかで比べよ。 整列の場合: ランダムな列を作り、それを整列さ せてみよ。列の長さで時間がどう変化するかをグ ラフを描いてみる。 • グラフから、実行時間を予測する式を推定せ よ 58 計算量 • これまで見てきたように、アルゴリズムによってプロ グラムの実行時間は大きく変わり得る • プログラムを作らずに、良いアルゴリズムを選ぶに はどうすればよいか? →計算量 アルゴリズムが答えを出すのに必要とする資源の見積り 資源 = 計算時間や記憶容量 通常はおおまかな式(オーダー, O)で見積り比較する ←それでも充分 60 計算量の求め方 1. 各演算、関数呼び出し、判断、分岐をそれ ぞれ「1回の計算」とする 2. 入力の引数 x に対する計算回数の式を求 める(xに依存した式になる) 3. 定数を消し、主要な項だけを残す (計算量 のオーダー) ※3を前提にすると1, 2は厳密でなくともよくなる 実際、整列では比較回数だけを考えたのと 同じになる(ビン整列法は例外) 61 計算量の求め方: 数え上げによる平方根 • n が sqrt(x)/δ になるまで繰り返しをする • 1回あたりの計算は 乗算×2、比較、分岐、関 数呼出 → 計5回の計算 • 約 5 sqrt(x)/δ 回の 計算 • 定数5を消して 計算量は O(sqrt(x)/δ) 62 計算量の求め方: 二分法による平方根 • (high−low)はx, x/2, x/4, x/8, ... x/2n と変化 • x/2n < δ になれば繰り返しは止まるので 約log2(x/δ)回で止まる • 1回あたりの計算は 定数回なので、 • 計算量は O(log(x/δ)) 63 計算量を求める: フィボナッチ数 • 問題: n番目のフィボナッチ数 定義通り ― O(yn) (y=(1+sqrt[5])/2) 数え上げ ― O(n) 100 行列 ― O(log n) 80 60 40 20 0 0 20 40 n 64 Ruby 定義通りに計算する フィボナッチ数 fib1(x)の計算時間 = fib1(x-1)の計算時間 + fib1(x-2)の計算時間 + 定数 def fib1(x) if x==0 || x==1 then 1 else fib1(x-1)+fib1(x-2) end end フィボナッチみたい? → 黄金比 65 多倍長整数のfibの場合... • • • • fib(n)の値はnに対して指数的に大きくなる。 fib(n)の桁数はnに比例して大きくなる。 多倍長整数の足し算の時間は桁数nに比例。 多倍長整数の掛け算の時間は桁数nに対して、 n*n 素朴なアルゴリズム n*(log n)*(log log n) 最高速アルゴリズム • fibの計算時間 fib2(n) n*nに比例 fib3(n) n*n*(log n) 素朴 n*(log n)*(log n)*(log log n) 最高速 66 計算量を求める: 整列アルゴリズム 問題: k以下の整数の長さnの列を整列 • 単純整列法 ― O(n2) • 併合整列法 ― O(n log n) • ビン整列法 ― O(n + k) n 10 n2 100 n logn 33 664 9,966 132,877 1.7E+06 2.0E+07 2.3E+08 2.7E+09 3.0E+10 n +k 110 200 1,100 100,100 1.0E+06 1.0E+07 1.0E+08 1.0E+09 100 1,000 10,000 100,000 1.0E+06 1.0E+07 1.0E+08 1.0E+09 10,000 1.0E+06 1.0E+08 1.0E+10 1.0E+12 1.0E+14 1.0E+16 1.0E+18 10,100 (k = 100の場合) 67 時間計算量と空間計算量 • いままでの計算量は「計算回数」に注目していた → 時間計算量という • 配列やリストのようなデータ構造を使う場合は、必 要とする記憶領域の大きさも問題となる 例: データ数の2乗の記憶領域が必要なアルゴリズムが あったとき、データ数が109個(1G個)あったら? • 「全てのデータの組」について表を作る場合 • webページの総数は100億(= 1010)以上と推定されている → 空間計算量 • 考え方は時間計算量と同様 68 空間計算量の例 • 併合ソート データ個数 n の2倍 → O(n) • ビンソート データ範囲の幅 k と データの個数 n の大き い方 → O(k+n) 範囲が狭い場合のみ使 える 未整列 整列済 93146431394873312 0123456789 0000000000 0123456789 0315301112 11123333344467899 69 課題: 計算量と実測値の対応 • 紹介したアルゴリズムの計算量のオーダーを 求めてみよ • プログラムの実行時間の実測値と対応がと れているかを確認せよ • 対応がとれない場合は、理由を考えよ 70
© Copyright 2024 ExpyDoc