多次元配列とfor文

多次元配列とは

配列には2種類存在し、直線のような一次元配列と表のような多次元配列があります。
多次元配列では以下の表のように行(x)と列(y)が存在し、2種類の値を使って多次元配列から値を取り出します。

多次元配列のアクセス順番

先程、多次元配列を表のように表しましたが、実際のメモリ上では以下のようになっているらしいです。

そのため、呼び出す順番を間違えると処理の速度に差が出てきます。
これを確かめるために、今回は行列の積を使って実験をしてみようと思います。
ここで行列の積を説明するのは大変なので、今回は省略します。行列の積を求める計算は以下のように3重ループを組みます。

 for(int i=0;i<n;i++)
 {
     for(int w=0;w<n;w++)
     {
         for(int v=0;v<n;v++)
         {
             data3[i,w] += data1[i,w] * data2[w,v];
         }
     }
 }                
        

今回行う実験ではこの「 i 」と「 w 」、「 v 」の場所を変えて処理の速度にどのくらいの差が出るかを調べます。
ちなみに、この3つの変数の順番を変えても行列の積の値は変わりません。
コードは長くなってしまうため省略しますが、3重ループを開始したときから、すべてのループを抜けたときまでの処理時間を測定します。
以下の図が実験の結果です。

どうですか、かなり差が出ていますね。今回の実験では2000×2000の行列で計測しました。
一番時間が短いのは以下のコードです。

 for(int i=0;i<n;i++)
 {
     for(int w=0;w<n;w++)
     {
         for(int v=0;v<n;v++)
         {
             data3[i,w] += data1[i,w] * data2[w,v];
         }
     }
 }    
        

一番時間が長いのは以下のコードです。

 for(int v=0;v<n;v++)
 {
     for(int w=0;w<n;w++)
     {
         for(int i=0;i<n;i++)
         {
             data3[i,w] += data1[i,w] * data2[w,v];
         }
     }
 }    
        

処理時間が短い方は、行(x)の移動が多く、処理時間が長い方は、列(y)の移動が多くなっています。多次元配列の列(y)の移動に関して、実際には2000個先のデータにアクセスするため無駄が多くなってしまうのですね。
このように、同じ計算の処理であっても、ループ処理の順番を変えるだけで処理の時間に差が出るのですね。

まとめ

多次元配列とfor文を組み合わせるときは、データにアクセスする順番に注意が必要であることが分かりましたね。
正直なところ普通に実装していると気が付かないものです。ちなみに言語によってはメモリ上の保存方法が異なるときがあるため調べてみるといいと思います。
なお、今回の実験中に気になることを発見したため、次回はその内容をまとめようと思います。 今回はこの辺で、ではまた！