コンピュータプラクティ スⅠ 比較実験 水野嘉明

本日の予定 計算量について 「比較実験」  パラメータを変化させての比較 ⇒ 実験１  二つのプログラムの比較 ⇒ 実験２  実験レポート Ｒ３として提出 2

計算量の表現 速度の評価 ① 実行時間を実測 前回の実験 ② 文を実行する回数をカウント プログラムの文面を見て、計 算 できる （概算） 3

計算量の表現 次のプログラムを考える 4 sum = 0; for (i = 0; i < N; i++){ for (j = 0; j < N; j++) { sum += data[i][j]; } ①②③④①②③④

計算量の表現  各文の実行回数は、 ① ： １回 ② ： N+1 回 ③ ： N*(N+1) 回 ④ ： N ２ 回 合計は、２ N ２ ＋ 2N ＋ 2 回 5

計算量の表現 f(N)= ２ N ２ ＋ 2N ＋ 2  N=10 ⇒ f(N)= 222  N=100 ⇒ f(N)=  N=1000 ⇒ f(N)=  N=10000 ⇒ f(N)= ほぼＮ ２ に比例する と言える Ｏ(Ｎ２)Ｏ(Ｎ２)

計算量の表現 計算量を考える時、比例定数はあ まり意味がない  実行時間は、コンパイラやＣＰ Ｕ能力により左右される パラメータ N について、どんなオー ダーであるかが重要 O(N) 、 O(N ・ log(N)) 、 O(N 2 ) 、 O(2 N ) ・・ 7

計算量の表現 アルゴリズムを評価する場合は、 その計算量のオーダーを考える  O(N ・ log(N)) のアルゴリズムは 、 O(2 N ) のアルゴリズムより は るかに速いといえる  実行回数を厳密に 数えるわけではない 8

比較実験 パラメータを変化させての比較 ⇒ 傾向分析 二つのプログラムの比較 ⇒ 比較実験 9

傾向分析 プログラムがパラメータにより異な る振る舞いをする場合 パラメータを変化させる 振る舞いの変化を明確にする （一度に複数の項目を変化させると、 変化の原因がわからなくなる） 10

実験１ プログラム L06Y01 について、  パラメータ RANGE を変化させ、 実行時間の変化を調べよ  また、グラフを描いてその傾向 について考察せよ （対数グラフがよい） 11

プログラムの説明 （ L06Y01 ） 「時間の測定」にて使用  RANGE 以下の素数の数を求める （数える範囲を、 #define 文で定 義している）  ２～ RANGE の各々について、 ｋで割り切れるかどうかを調べ ている （ n%k は n を k で割っ た余り） 12

実験１についての注意 科学的方法を思い出すこと 観察により（つまり、プログラ ムの文面 を見て）仮説を立てる 実行時間 の測定により、仮説を 検証する 13

実験１についての注意 オーダーの考え方（ O 記法）を用い て、仮説を立てること  『 RANGE が大きくなったら実行 時間も増大』 お粗末な仮説 実験しなくてもわかる！ 14

実験１についての注意 実行時間の測定は、前回と同じ仕 組みを用いる （バッチではない！ time() 関数に より、ラップを測る。実行時間 測定ツール (measure.cpp) を使う とよい。）  何桁の有効数字で求めるかを、 考えること 15

実験１についての注意 プログラムを繰り返すのは、測定 精度を上げるため （繰返し回数を増やしても速度は 変わらない 、つまり P10 の「複数 の項目」には入らない） 繰返し回数を固定してはならない 16

比較実験 他のプログラムとの比較により、 プログラムの評価を行なう  二つの実験対象を比較 比較実験 17

実験２ 付録Ａのプログラムは、任意の整 数を４つの整数の２乗和で表すプ ログラムである 付録Ｂは、付録Ａの改良版 元のプログラム ( 付録Ａ）と改良版 ( 付録Ｂ）を比較せよ  プログラムの文面と、実行時間 の両方を比較すること 18

プログラムの説明 （付録 A ） if 文  ｘが４個の整数の二乗和となっ たとき printf で表示 a,b,c,d の for 文  変数 a が 0 からｘまで変化  その各々の値について、 b が a か ら x まで変化  c,d も同様 19 ⇒ O(x) ⇒ O(x 2 ) ⇒ if 文のオーダは ？

プログラムの説明 （付録 B ） A プログラムの繰り返し回数は、 減らすことができる  a > √x （ a ２ > x ）の時、明らか に if 文の条件式は成り立たない  a ２ +b ２ > x の時も同様 B は、これらを改良 20

実験２についての注意 実行時間の測定は、前回および実 験１と同じ仕組みを用いる  scanf をループ内に入れないこ と（ループ内にあると、それだ けの回数キーボードからの入力 が必要） 21

実験２についての注意 測定のための繰返し回数は、必要 な有効数字の桁数が出るように適 当な値を設定する  固定する必要もないし、しては ならない  ＡプログラムとＢプログラムで は、当然異なるはず 22

実験２についての注意 仮説を検証するためには、入力値 ｘはどのような値を何種類くらい 試せばよいのかを考える  悪い例 ｘ = 1 のみで実験したら、どうなる か？ 23

課題 O 記法について  O 記法の正確な定義について、 文献を調査せよ  O 記法の利点について、考察せ よ

実験レポート 実験１、２と課題を、レポートＲ ３として提出せよ  表題は、「比較実験」  章立ては、Ｒ１ と同じ （実験は二つなので、第４章が 課題、第５章が結論） 25

次回の予定 「再現性」  実験の再現と実験環境について  本日の実験１、２について、追 実験を行う  レポートＲ４ として提出 26

お疲れさまでした