2次元配列: Sample 1: 2次元配列への代入(C)
■ 概要
このサンプルでは正方マトリックスに値を単に代入するという非常に単純なプログラムを示します。ここでは2重ループを使って値を代入します。ループの順番から考えると、以下の2通りのコーディングの仕方があります。
Code 1では内側ループ(ループj)はマトリックスの行(第1の指数)に関連付けられます。一方、Code 2では列(第2の指数)に関連付けられます。マトリックスのサイズnは1000から30000までの30個の値を採用します。各nに対してマトリックスへの代入にかかった時間を測定し出力します。
■ ソースコード
|
◆ Code 1
|
◆ Code 2
|
/*
Program to measure time to initialize a nxn matrix to a value.
a(i,j) = 1 for i=1,...,n, and j=1,...,n.
*/
#include <stdio.h>
#include <time.h>
int main()
{
int i, j;
printf("Matrix size Elapsed time [sec] \n");
for (int k=1; k<=30; k++) {
// Matrix size
int n = k*1000;
// Allocation
int **a;
a = new int*[n];
for (i=0; i<n; i++)
a[i] = new int[n];
// Start time
clock_t time0 = clock();
// Main calculation: initialization
for (i=0; i<n; i++)
for (j=0; j<n; j++)
a[j][i] = 1;
// Finish time
clock_t time1 = clock();
// Output time
double time = (double)(time1-time0)/CLOCKS_PER_SEC;
printf("%11d %15.7f\n",n, time);
// Deallocation
for (int i=0; i<n; i++)
delete[] a[i];
delete[] a;
}
return 0;
}
|
/*
Program to measure time to initialize a nxn matrix to a value.
a(i,j) = 1 for i=1,...,n, and j=1,...,n.
*/
#include <stdio.h>
#include <time.h>
int main()
{
int i, j;
printf("Matrix size Elapsed time [sec] \n");
for (int k=1; k<=30; k++) {
// Matrix size
int n = k*1000;
// Allocation
int **a;
a = new int*[n];
for (i=0; i<n; i++)
a[i] = new int[n];
// Start time
clock_t time0 = clock();
// Main calculation: initialization
for (i=0; i<n; i++)
for (j=0; j<n; j++)
a[i][j] = 1;
// Finish time
clock_t time1 = clock();
// Output time
double time = (double)(time1-time0)/CLOCKS_PER_SEC;
printf("%11d %15.7f\n",n, time);
// Deallocation
for (int i=0; i<n; i++)
delete[] a[i];
delete[] a;
}
return 0;
}
|
■ 計算時間の測定結果
Code 1とCode 2を実行したときの計算時間をそれぞれ青線と赤線で図1に示します。そして両者の比を緑線で示します。
図1 測定時間
■ 考察
C言語では2次元配列を行単位で1次元配列に組みなおされるので、内側のループが列に関連付けられたCode 1は図2のように飛び飛びしたメモリアクセスになります。一方、内側のループが行に関連付けられたCode 2は図3のように連続したメモリアクセスになります。
さて図1ではCode 1がCode 2より計算時間が長いという結果を得ました。これはメモリアクセスのジャンプが頻繁に起こるためです。サイズnが大きくなるにつれてCode 1とCode 2との計算時間の比率が増えていき、Code 1がCode 2より50倍近く遅くなることもあります。言い換えれば、メモリアクセスのジャンプを避ければ、50倍も速いコードを書けるということがいえます。
.png)
