2次元配列: Sample 2: マトリックス・ベクトルの掛け算(JScript)

高速化プログラミング   
トップ  >  メモリジャンプと高速化  >  2次元配列  >  Sample 2: マトリックス・ベクトルの掛け算(JScript)

2次元配列: Sample 2: マトリックス・ベクトルの掛け算(JScript)

言語の変更:   C版   FORTRAN版

■ 概要

このサンプルではマトリックスとベクトルの掛け算を行います。

c=Ab           ... 式(1)

通常、マトリックスAijを2次元配列A[i][j]としてコーディングしますが、場合によっては列と行を入れ替えてA[j][i]にすることもできます。ベクトルcさえ求まればどちらも採用してもいいですが、問題は計算時間です。実際にプログラムを見て、実行してみましょう。

下のCode 1ではA[j][i]、Code 2ではA[i][j]としてコーディングしてマトリックスとベクトルの掛け算をします。これらのコードは本ページに埋め込んでありますので、コードの下のフォームにサイズnを入力し実行ボタンを押すと、これらのコードを実際に実行できます。そして計算にかかった時間は表示されますので、どのコードがどれぐらい速いか体験できます。

■ ソースコード


  ◆ Code 1   ◆ Code 2
 
/*
  Program to measure time to carry out matrix-vector product.
  c(i) = sum(a(j,i)*b(j),j=1,...,n) for i=1,...,n
 */

function ex1(n)
{
    // Allocation
    a = new Array(n);
    for (i=0; i<n; i++)
	a[i] = new Array(n);
    b = new Array(n);
    c = new Array(n);

    // Initialization
    for (j=0; j<n; j++)
	for (i=0; i<n; i++)
	a[j][i] = 1;
    for (i=0; i<n; i++)
      b[i] = 1;

    // Start time
    time0 = new Date();

    // Main calculation: matrix-vector product
    for (i=0; i<n; i++) {
      c[i] = 0;
      for (j=0; j<n; j++) {
	c[i] += a[j][i] * b[j];
      }
    }

    // Finish time
    time1 = new Date();

    // Computational time (sec)
    time = 0.001 * (time1 - time0);
    return time;
}
    
 
/*
  Program to measure time to carry out matrix-vector product.
  c(i) = sum(a(i,j)*b(j),j=1,...,n) for i=1,...,n
 */

function ex2(n)
{
    // Allocation
    a = new Array(n);
    for (i=0; i<n; i++)
	a[i] = new Array(n);
    b = new Array(n);
    c = new Array(n);

    // Initialization
    for (j=0; j<n; j++)
	for (i=0; i<n; i++)
	a[j][i] = 1;
    for (i=0; i<n; i++)
      b[i] = 1;

    // Start time
    time0 = new Date();

    // Main calculation: matrix-vector product
    for (i=0; i<n; i++) {
      c[i] = 0;
      for (j=0; j<n; j++) {
	c[i] += a[i][j] * b[j];
      }
    }

    // Finish time
    time1 = new Date();

    // Computational time (sec)
    time = 0.001 * (time1 - time0);
    return time;
}
    
上のJScriptコードを実行してみよう!
サイズ n =

計算時間 = sec
サイズ n =

計算時間 = sec

■ 考察

JScript言語ではC言語と同様に2次元配列を行単位で1次元配列に組みなおされるので、内側のループが列に関連付けられたCode 1は図2のように飛び飛びしたメモリアクセスになります。一方、内側のループが行に関連付けられたCode 2は図3のように連続したメモリアクセスになります。上のフォームを使ってCode 1よりCode 2の方が速いことをご確認してみてください。

Code 1のときのメモリアクセス
図2 Code 1のときのメモリアクセス
Code 2のときのメモリアクセス
図3 Code 2のときのメモリアクセス


はじめに

演算数を減らす

メモリジャンプを減らす

高性能のアルゴリズム

その他



3 4 9 0 4 5