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

(1)

コンピュータプラクティスⅠ

比較実験

水野嘉明

(2)

本日の予定



計算量について



「比較実験」



パラメータを変化させての比較 ⇒ 実験１



二つのプログラムの比較 ⇒ 実験２



実験レポートＲ３として提出

2

(3)

計算量の表現



速度の評価

① 実行時間を実測前回の実験

② 文を実行する回数をカウントプログラムの文面を見

て、計算できる（概算）

3

(4)

計算量の表現



次のプログラムを考える

4 sum = 0;

for (i = 0; i < N; i+

+){

for (j = 0; j < N;

j++) {

sum += data[i][j];

} }

① ②

③ ④

(5)

計算量の表現



各文の実行回数は、

① ：１回

② ： N+1 回

③ ： N*(N+1) 回

④ ： N ^２回

合計は、２ N ^２＋ 2N ＋ 2 回

5

(6)

計算量の表現

f(N)= ２ N ^２＋ 2N ＋ 2



N=10 ⇒ f(N)= 222



N=100 ⇒ f(N)= 20202



N=1000 ⇒ f(N)= 2002002



N=10000 ⇒ f(N)= 200020002

6

ほぼＮ^２に比例すると言えるＯ

(

Ｎ^２

)

Ｎが大きければ

(7)

計算量の表現



計算量を考える時、比例定数はあまり意味がない



実行時間は、コンパイラやＣＰＵ能力により左右される

パラメータ N について、どんなオーダーであるかが重要

O(N) 、 O(N ・ log(N)) 、 O(N

2) 、 O(2^N) ・・

⁷

(8)

計算量の表現



アルゴリズムを評価する場合は、

その計算量のオーダーを考える



O(N ・ log(N)) のアルゴリズムは、 O(2^N) のアルゴリズムよりはるかに速いといえる



実行回数を厳密に数えるわけではない

8

(9)

比較実験



パラメータを変化させての比較 ⇒ 傾向分析



二つのプログラムの比較 ⇒ 比較実験

9

(10)

傾向分析



プログラムがパラメータにより異なる振る舞いをする場合

パラメータを変化させる

振る舞いの変化を明確にする

（一度に複数の項目を変化させる変化の原因がわからなくなる）と、

10

(11)

実験１



プログラム L06Y01 について、



パラメータ RANGE を変化させ

、実行時間の変化を調べよ



また、グラフを描いてその傾向について考察せよ

（対数グラフがよい）

11

(12)

プログラムの説明（ L06Y0 1 ）



「時間の測定」にて使用



RANGE 以下の素数の数を求める

（数える範囲を、 #define 文で定義している）



２～ RANGE の各々について、

ｋで割り切れるかどうかを調べている（ n%k は n を k で割った余り）

12

(13)

実験１についての注意



科学的方法を思い出すこと

観察により（つまり、プログラムの文面を見て）仮説を立てる

実行時間の測定により、仮説を検証する

13

(14)

実験１についての注意



オーダーの考え方（ O 記法）を用いて、仮説を立てること



『 RANGE が大きくなったら実行時間も増大』

お粗末な仮説

実験しなくてもわかる！

14

(15)

実験１についての注意



実行時間の測定は、前回と同じ仕組みを用いる

（バッチではない！ time() 関数により、ラップを測る。実行時間測定ツール (measure.cpp) を使うとよい。）



何桁の有効数字で求めるかを、

考えること

15

(16)

実験１についての注意



プログラムを繰り返すのは、測定精度を上げるため

（繰返し回数を増やしても速度は変わらない、つまり

P10 の「複

数の項目」には入らない）

繰返し回数を固定してはならない

16

(17)

比較実験

 他のプログラムとの比較により、

プログラムの評価を行なう



二つの実験対象を比較

比較実験

17

(18)

実験２

 付録Ａのプログラムは、任意の整

数を４つの整数の２乗和で表すプログラムである

 付録Ｂは、付録Ａの改良版

 元のプログラム ( 付録Ａ）と改良版

(

付録Ｂ）を比較せよ



プログラムの文面と、実行時間

の両方を比較すること

₁₈

(19)

プログラムの説明（付録 A ）



if 文

 ｘが４個の整数の二乗和となっ

たとき printf で表示



a,b,c,d の for 文



変数 a が 0 からｘまで変化



その各々の値について、

b

が a から

x

まで変化



c,d も同様

19 ⇒ O(x)

⇒ O(x

²

)

⇒ if

文のオーダは？

(20)

プログラムの説明（付録 B ）



A プログラムの繰り返し回数は、

減らすことができる



a > √x （ a ^２

> x ）の時、

明らかに if 文の条件式は成り立たない



a ^２ +b ^２

> x の時も同様

 B

は、これらを改良

20

(21)

実験２についての注意



実行時間の測定は、前回および実験１と同じ仕組みを用いる



scanf をループ内に入れないこと（ループ内にあると、それだけの回数キーボードからの入力が必要）

21

(22)

実験２についての注意



測定のための繰返し回数は、必要な有効数字の桁数が出るように適

当な値を設定する

 固定する必要もないし、しては

ならない

 ＡプログラムとＢプログラムで

は、当然異なるはず

22

(23)

実験２についての注意



仮説を検証するためには、入力値

ｘはどのような値を何種類くらい試せばよいのかを考える

 悪い例

ｘ = 1 のみで実験したら、どう

なるか？

23

(24)

課題

 O

記法について

 O

記法の正確な定義について、

文献を調査せよ

 O

記法の利点について、考察せよ

(25)

実験レポート



実験１、２と課題を、レポートＲ３として提出せよ



表題は、「比較実験」

 章立ては、

Ｒ１と同じ

（実験は二つなので、第４章が

課題、第５章が結論）

25

(26)

次回の予定



「再現性」



実験の再現と実験環境について



本日の実験１、２について、追実験を行う



レポートＲ４として提出

26

(27)

お疲れさまでした

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