多重ループ: Sample 3: ダミー配列との併用(C)

言語の変更： FORTRAN版

■ 概要

このサンプルでは式(1)にしたがって配列aから2次元配列配列xを計算します。2次元配列だから、2重ループを使用して配列xを求めます。

... 式(1)

式(1)を素直にコーディングしたのはCode 1です。メイン計算では2つのループ、ループiとループj、を設けてその中に式(1)の右辺をそのまま計算しています。

前のサンプルと同様にCode 1ではcosの計算が2N²回ありますが、必要最低限はi=1からNまでのcos(a[i])なのでN回のはずです。しかしこのサンプルではcos(a[i])とcos(a[j])が必要であり、片方のcos(a[j])をループ外に出せたとしても、もう片方のcos(a[i])は出せないので、cosの計算が結局N²+N回までしか減らせませんでした。この改良でCode 1が若干高速化されてはいますが、まだ高速化が足りません。cosの計算が必要最低限のN回まで減らしたいです。

ループiとjを入れ替えても状況は変わらないことを確認できます。

Code 2はcos(a[i])の回数を極限のN回まで減らした例です。ここではダミー配列cos_aを使用しています。メイン計算の前にcos(a[i])の値を全部あらかじめ計算して、cos_a[i]に入れておきます。メイン計算にはcosの計算をせず、cos_aから必要なものを使うだけ。このようにすれば、cosの計算はN回だけで済みます。

ここで一つ注意点があります。Code 2はCode 1より高速ですが、使用メモリも配列cos_aの分だけ多いです。メモリに余裕があったらCode 2が通用しますが、メモリが厳しければCode 1を使用するしかありません。高速化と省メモリ化は一般的に正反対の関係にあることがよくあります。

■ ソースコード

◆ Code 1 ◆ Code 2

 
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>

#define N 10000

double a[N], x[N][N];

int main()
{
  int i,j;

  // Initialization
  for (i=0; i<N; i++) a[i] = rand();

  // Start time
  clock_t time0 = clock();






  // Main calculation
  for (i=0; i<N; i++) {
    for (j=0; j<N; j++) {
      x[i][j] = cos(a[i]) * cos(a[j]);
    }
  }

  // Finish time
  clock_t time1 = clock();

  // Output time
  double time = (double)(time1-time0)/CLOCKS_PER_SEC;
  printf("Time = %15.7f sec\n", time);


  return 0;
}

 
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>

#define N 10000

double a[N], x[N][N];

int main()
{
  int i,j;

  // Initialization
  for (i=0; i<N; i++) a[i] = rand();

  // Start time
  clock_t time0 = clock();

  // Preparation
  double *cos_a = new double[N];
  for (i=0; i<N; i++)
    cos_a[i] = cos(a[i]);

  // Main calculation
  for (i=0; i<N; i++) {
    for (j=0; j<N; j++) {
      x[i][j] = cos_a[i] * cos_a[j];
    }
  }

  // Finish time
  clock_t time1 = clock();

  // Output time
  double time = (double)(time1-time0)/CLOCKS_PER_SEC;
  printf("Time = %15.7f sec\n", time);

  delete[] cos_a;
  return 0;
}

■ 計算時間の測定結果

Code 1とCode 2の計算時間の測定結果を表1に示します。ここではそれぞれのコードを5回実行して、平均とCode 1とCode 2との計算時間の比率も表示します。

表1 計算時間の測定結果(単位: sec)
	1回目	2回目	3回目	4回目	5回目	平均	倍率
Code 1	8.21	8.21	8.17	8.24	8.33	8.23	16.2
Code 2	0.50	0.51	0.51	0.50	0.51	0.51	-

■ 考察

Code 1はCode 2に比べて16.2倍遅いという結果が得ました。

前: Sample 2: ループの順番(C)

次: メモリジャンプと高速化

多重ループ: Sample 3: ダミー配列との併用(C)