演習 (11/08)

本日の演習のテーマは，プログラムの実行（過程）を対象とした観察・観測である． 演習の前半部分では，プログラムの実行過程を詳細に調べる方法について学ぶ． これには，デバッガと呼ばれるツールを用いる． デバッガは，バグの原因を探るために利用されることが多いツールである． 一方，後半部分では，プログラムの実行時間の測り方を学ぶ．

プログラムの実行を観察する

ここでは例題として次のプログラムを用いる．

#include <stdio.h>

int main (int argc, const char * argv[]) {
  int table[5];
  table[0] = 3;
  table[1] = 2;
  table[2] = 4;
  table[3] = 1;
  table[4] = 5;

  int i, j;
  for (i = 0; i < 5; i++) {
    for (j = i + 1; j < 5; j++) {
      if (table[j] < table[i]) {
        int temp = table[i];
        table[i] = table[j];
        table[j] = temp;
      }
    }
  }
  return 0;
}

このプログラムは何も出力しないので，実行結果から何を計算しているかを知ることはできない．

作業１

上のプログラムが何を計算しているか，しばらくプログラムを眺めて考えよ．

このプログラムの挙動を調べるために，ところどころに printf を挿入し，各時点での配列 table, 変数 i, j の値を出力させる方法がある． たとえば，次のようにするとtable への5回の代入が終了した時点での各要素の値を確認することができる．

#include <stdio.h>

int main (int argc, const char * argv[]) {
  int table[5];
  table[0] = 3;
  table[1] = 2;
  table[2] = 4;
  table[3] = 1;
  table[4] = 5;

  int k;                                     // 追加
  for(k = 0; k < 5; k++) {                   // 追加
    printf("table[%d] = %d\n", k, table[k]); // 追加
  }                                          // 追加

  int i, j;
  for (i = 0; i < 5; i++) {
    for (j = i + 1; j < 5; j++) {
      if (table[j] < table[i]) {
        int temp = table[i];
        table[i] = table[j];
        table[j] = temp;
      }
    }
  }
  return 0;
}
作業２

上のプログラムの実行結果がどうなるか予想してから，実際にプログラムを実行し，予想通りの結果となるかどうかを確認せよ． さらに，for 文の内側にも printf を挿入し，for 文の繰り返しの中で行われている動作が「作業１」での予想と一致するかどうかを確認せよ．

このように printf を適宜挿入することで，原理的にはプログラムの実行過程を観察できる． しかし，この方法では，プログラムを一時的に書き換える必要があるので，間違いを犯すと元のプログラムに戻せなくなる可能性もある． プログラムが大きくなり，観察したい箇所が増えてくるとだんだん作業が煩雑になる． 観察や観測を行うときに対象を破壊せずにすむ方が望ましいのは，コンピュータサイエンスに限ったことではない．

プログラムを書き換えずに実行過程を観察するためのツールとしてデバッガがある． デバッガを使うと，プログラムの実行中に一時停止し，その時点での変数の値を確認することができる．

Xcode の中でデバッガを起動する時には，まず実行を一時停止したい行にブレークポイントを設定するのが一般的である． 下の図では，最初の for 文の先頭行にカーソルを移動してから，「ブレークポイント」ボタンを押した様子を示しており，この行の左側の細長い５角形がブレークポイントの印である．


図1: ブレークポイントの設定

この状態で，「デバッグ」メニューから「デバッガ」を選択すると新しいウィンドウが現れる．


図2: デバッガの初期画面

このウィンドウの「ビルドとデバッグ」ボタンを押すと，プログラムの実行が開始された後，ブレークポイントを設定した箇所で一時停止する．


図3: ブレークポイントでの一時停止

ウィンドウの下側のパネルにはブレークポイントの近辺の行が表示される． 現在 for 文の先頭で止まっていることをこの図から読み取ることができる． そして，右上のパネルには，現在参照できる変数のリストとその値が表示される． 今興味があるのは table, i, j なので，そのあたりを見てほしい． table の右側に記された [5] は，table の長さが5であることを示している． 一方, i, j の右側の0と-1881115804 は，i, j の値を示している． 一度も代入が行われていない変数には変な値が入っていることもあるので注意が必要である．

table の各要素の値を見るには，table の左側の三角形をクリックするとよい． table の中身が展開され，0番目から4番目のまでの値が 3, 2, 4, 1, 5 であることがわかる．


図4: テーブルの中身の確認

ここで「ステップオーバー」ボタンを押すと1行ずつ実行が進む． 「ステップオーバー」ボタンを2度押した段階で，表示は次のようになる．


図5: ステップオーバー

赤い矢印が2行分先へ進むとともに，変数jの値が1に変化した． 変数の値が直前に変化したことを，赤い文字で表している．

このような操作を続けると，プログラムを1行ずつ実行しながら，各時点での変数の値を調べることができる． この方法で，原理的にはプログラムの実行過程を詳細に調査可能だが，現実問題として人手で追える行数には限界がある．

「ステップオーバー」の代わりに「続ける」ボタンを押すと，次のブレークポイントに達するまで実行を続けるので，少し状況が改善される． ただし，適切な箇所にブレークポイントを設定するのはユーザの責任になる． ブレークポイントは複数設定しても良いし，実行を一時停止したときに追加，削除することもできる． たとえば，デバッガでは，プログラム左側のブレークポイントの印や赤い矢印が現れる領域をマウスでクリックすると，その位置に新たなブレークポイントを設定できる．

デバッガによるプログラム実行を途中で終了したい時には「終了」ボタンを押せばよい．

プログラムの実行時間を測定する

次は，プログラムの実行時間の測り方である． ここでの例題としては，さきほどのプログラムを少し一般化したものを用いる．

#include <stdio.h>

#define N 5

int main (int argc, const char * argv[]) {
  int table[N];
  int i, j;

  for (i = 0; i < N; i++) {
    table[i] = N - i;
  }

  for (i = 0; i < N; i++) {
    for (j = i + 1; j < N; j++) {
      if (table[j] < table[i]) {
        int temp = table[i];
        table[i] = table[j];
        table[j] = temp;
      }
    }
  }
  return 0;
}

今度は table の長さが N になっている． そして，先頭付近で #define を用いて， N を 5 と定義している． この部分を書き換えると，N の値を変更することができる．

作業３

作業１同様に，このプログラムが何を行っているか自分の頭で考えよ．

以下では，2番目の for 文の実行時間（内側の文の実行時間を含む）を測ることにする． そのためにプログラムを次のように変更する．

#include <stdio.h>
// 追加
#include <time.h>

#define N 5

int main (int argc, const char * argv[]) {
  int table[N];
  int i, j;

  for (i = 0; i < N; i++) {
    table[i] = N - i;
  }

  clock_t start = clock(); // 追加
  for (i = 0; i < N; i++) {
    for (j = i + 1; j < N; j++) {
      if (table[j] < table[i]) {
        int temp = table[i];
        table[i] = table[j];
        table[j] = temp;
      }
    }
  }
  clock_t ticks = clock() - start; // 追加
  printf("%d msec\n", (1000 * ticks)/CLOCKS_PER_SEC);  // 追加
  return 0;
}

基本的には，for 文の前後で clock() を用いて時間を調べ，その差を実行時間と考えて測定を行っている． MacOS X の場合，clock() を用いると，プログラム実行開始時点からの総 CPU 利用時間を10ミリ秒単位で測ることができる． clock() で計測した値を CLOCK_PER_SEC で割ると秒を単位としたCPU利用時間になる． (MacOS X の場合，CLOCK_PER_SEC は 100 になる)． このプログラムでは，clock() で測った時間を1000倍してから CLOCK_PER_SEC で割って出力しているので，ミリ秒単位の時間が表示される（ただし，精度はあくまで10ミリ秒）．

このプログラムを，そのまま実行してもあまり意味のある結果は得られない． プログラムの実行時間は10ミリ秒よりはるかに短いので，正確に測ることができない．

(1) N がもっと大きな場合を測定対象とする，(2) 同じ処理を何度も繰り返し，合計実行時間を長くする，(3) より高精度な測定手段を用いる，などが許される状況では意味のある結果が得られるかもしれない． 今日のところは，どうしても N = 5 の場合の実行時間が知りたいわけでもないので，(1) を試してみる． N の値を増やすのは簡単で，#define の後の 5 をもっと大きな整数にすればよい．

レポート課題1 (11/29 締切)

上のプログラムで N の大きさをいろいろ変化させたとき，実行時間がどのように変化するかを実測により調査せよ． そして，N の値と実行時間の間にどのような関係が成り立つか考察せよ． なお，測定を行うにあたっては，同じプログラムを複数回実行した時に，毎回同じ実行時間が得られるとは限らないという前提で行うこと．

レポート課題2 (11/29 締切)

上のプログラムで，3番目の for 文が繰り返し実行される回数を N の式で表せ． この繰り返し回数とレポート課題1で測った実行時間にはどのような関係があるか（あるいはないか）を考察せよ．

レポート課題3 (11/29 締切)

上のプログラムの最初の for 文では，配列の初期値を設定している． ここで table[i] に代入する値を N - i から i に変更すると，2番目の for 文の実行時間はどれくらい変化するだろうか？ 実測により確認するとともに，その変化の理由を考察せよ．

「プロジェクト」メニューから「アクティブなビルド構成を設定」を選ぶと，「Debug」と「Release」を選択することができる． この選択肢を切り替えると，プログラムの実行性能がかなり変わることがある．

レポート課題4 (11/29 締切)

「アクティブなビルド構成を設定」で選択されるのが「Debug」の場合と「Release」の場合で，実行性能がどれくらい違うか確認せよ．

レポート課題5 (11/29 締切)

演習室のコンピュータで，加算，代入などの単純な演算が毎秒何回程度実行できるか知りたい． そこで，これを推定するための実験を企画し，その実験結果から概数（有効数字1桁程度でよい）を求めよ． なお，本日紹介した実行時間の測定方法では，10ミリ秒単位での計測しかできないので，単純な演算1回の実行時間を直接測定するのは無理だと思った方がよい． また，for 文を使って一定回数の繰り返し実行を行う場合，i++ などの加算，i < N などの大小比較が，繰り返し回数分くらいは実行され，これが無視できない時間を消費する可能性もあることを考慮せよ．

最後に

本日は，プログラムの実行過程を観察する方法，プログラムの実行時間を測定する方法の初歩を学んだ． コンピュータサイエンスにとって，計算の質的な側面（e.g. 正しく計算を行えるか？）と量的側面（e.g. どれくらい速く計算できるか？）はともに重要なテーマである． 本日学んだ観察と測定の手法は，それぞれ計算の質と量を議論するうえでの基礎をなすものである．