【ワレコC#講座】多次元配列のループテクニック【高速化】

C#で多次元配列を使う場合には、幾つかの注意事項がある。

それを知っているかいないかで、作成したプログラムの実行速度が数倍くらい変わる場合もある。

数値計算などで少しでも高速に計算したい人には必須の知識であるが、知らない人も多い。

この記事では、C#において多次元配列を使う上でのそんなテクニックを紹介したい。

なお、多次元配列の親戚の多段階配列に関しては、別の記事で解説しているので参考にして頂きたい。

【ワレコC#講座】多段階配列（ジャグ配列）完全マスター【ややこしい】

C#やVB.NETに限らず、一般にプロブラミングの世界で配列を使う場合には、一次元配列よりも多次元配列配列を使う場合のほうが多いと思う。 例えば二次元の 6行 x 5列 の配列ならこんなイメージか。 図　二次元配列の例 さて、C#やVB.N...

www.wareko.jp

2017.10.26

この記事が意外に人気が高いのだ。

 

では本題に入ろう。

C#の典型的な二次元配列の例（初期値を与える）

以下では intArray、intArray2と言う二つの整数型配列を定義している。

後者の intArray2 の場合には、宣言と同時に初期値を与えている。

非常に簡単な例である。

class Test1_整数配列
{
    public static void test1()
    {
        int[,] intArray = new int[4, 3];
 
        LibClass.二次元配列の中身を表示する(intArray, nameof(intArray));
 
        //                        [i, j]
        int[,] intArray2 = new int[4, 3] {
            //         j=0   1   2
            /* i=0 */ { 00, 01, 02 },     // 　00 → →
            /* i=1 */ { 10, 11, 12 },     //   → → →　　メモリ上には矢印順
            /* i=2 */ { 20, 21, 22 },     //   → → →　　に配置される
            /* i=3 */ { 30, 31, 32 },     //   → → 32  
        };
 
        LibClass.二次元配列の中身を表示する(intArray2, nameof(intArray2));
    }
}

上のコードで注意すべき点は、二次元配列の各要素はコンピュータのメモリ上に矢印で示す順番に配置されると言う点である。

C#のint型のサイズは下のコードを実行すると分かるように、4バイトだ。

var sizeOfInt = sizeof(int);
Console.WriteLine(sizeOfInt); // 4

従って、上のプログラムを実行すると、intArrayとintArray2はそれぞれ

4行 x 3列 x 4バイト = 48 バイト

のメモリ領域が配列データ格納用に確保される。 

配列の中身を表示する関数を即席で作成してみた。

class LibClass
{
    public static void 二次元配列の中身を表示する(int[,] intArr, string arrName)
    {
        string typeOfVariable = intArr.GetType().ToString();//"System.Int32[,]"
        string space = new String(' ', arrName.Length + 1);
 
        Console.Write(space + "   j =");
        for (int j = intArr.GetLowerBound(1); j <= intArr.GetUpperBound(1); j++)
        {
            Console.Write("{0,9:d}", j);
        }
        Console.WriteLine();
 
  
        Console.Write(space + "i     ");
        for (int j = intArr.GetLowerBound(1); j <= intArr.GetUpperBound(1); j++)
        {
            Console.Write("{0,9:s}", "-----");
        }
        Console.WriteLine("");
 
 
        for (int i = intArr.GetLowerBound(0); i <= intArr.GetUpperBound(0); i++)
        {
          //Console.Write("intArr({0}, j)=", i);
            Console.Write("{0}[{1}, j]=", arrName, i);
            for (int j = intArr.GetLowerBound(1); j <= intArr.GetUpperBound(1); j++)
            {
                Console.Write("{0,9:d}", intArr[i, j]);
            }
            Console.WriteLine();
        }
        Console.WriteLine();
    }
}

まあ、即席で作成したので突っ込みどころは多いかも知れないが次に進もう。

なおConsole.WtiteLine()内の書式設定を学びたい人はこの記事がお勧めだ。

【ワレコC#】Console.WriteLine()書式指定で右詰め･ゼロ埋め･桁指定･16進など

ワテの場合、C# を使い始めてからかなりの年月が経つのだが、Console.WriteLine() の書式指定が未だに覚えられない。 Console.WriteLine() とは、C#のコンソールアプリケーション、つまり実行するとコンソール

www.wareko.jp

 

早速冒頭のテストプログラムを実行してみる。

class Program
{
    static void Main(string[] args)
    {
        Test1_整数配列.test1();
    }
}

その実行結果は以下の通り。

            j =        0        1        2
         i         -----    -----    -----
intArray[0, j]=        0        0        0
intArray[1, j]=        0        0        0
intArray[2, j]=        0        0        0
intArray[3, j]=        0        0        0

             j =        0        1        2
          i         -----    -----    -----
intArray2[0, j]=        0        1        2
intArray2[1, j]=       10       11       12
intArray2[2, j]=       20       21       22
intArray2[3, j]=       30       31       32

続行するには何かキーを押してください . . .

無事に実行出来た。

intArrayは初期値を与えていないのでデフォルト値の0で初期化されている。

一方、intArray2は宣言と同時に与えた初期値が正しく表示出来ている。

 

さて、ここまでの処理に関しては、皆さん特には疑問は無いだろう。

ところが、二次元配列の全要素を行と列の二重ループ処理して、その配列要素を参照する場合に、行ループと列ループの順番に注意する必要があるのだ。

その事を知らない人も多い。

速さが必要なら二次元配列の行と列の順番に注意する

以下のサンプルプログラムは、先ほどのサンプルとほぼ同じ。

違いは要素数が 10000 x 10000 に増えた事と、execute() 関数内での二重ループが

• i, j の順番にループするか
• j, i の順番にループするか

の違いである。

早速実行してみよう。

ちなみにワテのマシンのスペックは以下の通り。

• Windows10 Pro 64
• CPU Core i7-4770K Haswell (3.5GHz)
• MEM CFD W3U1600HQ-8GC11 [DDR3 PC3-12800 8GB 2枚組]　計32GB
• SSD　Crucial Micron製 750GB

マシンの詳細は

【ワテ本番機】Win8をWin10に無料アップグレード完了

に記載している。

さて、test2()を実行してみる。

class Test2_二次元配列の行と列
{
    public static void test2()
    {
        const int iLen = 10000;
        const int jLen = 10000;

        int[,] intArr = new int[iLen, jLen];
 
        Stopwatch watch = new Stopwatch();
        execute("第1回目");
        execute("第2回目");
        execute("第3回目");
 
        void execute(string testCount)
        {
            Console.WriteLine("---------------------------------\r\n{0}", testCount);
            watch.Restart();
            for (int i = 0; i < iLen; i++)
            {
                for (int j = 0; j < jLen; j++)
                {
                    intArr[i, j] = i * iLen + j;
                }
            }
            watch.Stop();
            Console.WriteLine("経過時間 ={0,12:d} [ミリ秒]", watch.ElapsedMilliseconds);
 
            watch.Restart();
            for (int j = 0; j < jLen; j++)
            {
                for (int i = 0; i < iLen; i++)
                {
                    intArr[i, j] = i * iLen + j;
                }
            }
            watch.Stop();
            Console.WriteLine("経過時間 ={0,12:d} [ミリ秒]", watch.ElapsedMilliseconds);
        }
    }
}

上のソースコードの内容は説明しなくて大体分ると思うが、念のために言うと、execute()と言う関数を三回実行している。

一回だけだと計測結果に偏りが出るなどの可能性もあるので、数回繰り返してより厳密に計測したかったので。

execute()関数内では、forループの二重構造が二カ所にある。

前者は一つの i の値に対して、j が全範囲を変化する。

後者は一つの j の値に対して、i が全範囲を変化する。

 

配列の各要素に

intArr[i, j] = i * iLen + j; 

で値を代入しているが、この計算自体は深い意味は無い。必要に応じて皆さんが目的とする処理をここに書けば良い。

 

そのtest2()の実行結果は以下の通り。

---------------------------------
第1回目
経過時間 =         542 [ミリ秒]
経過時間 =        1403 [ミリ秒]
---------------------------------
第2回目
経過時間 =         453 [ミリ秒]
経過時間 =        1384 [ミリ秒]
---------------------------------
第3回目
経過時間 =         476 [ミリ秒]
経過時間 =        1407 [ミリ秒]
続行するには何かキーを押してください . . .

なんやて！

ループ変数 i, j の順番を逆転すると計算時間が3倍くらい長く掛かっているぞ！

ループ変数 i, j の順番を逆転すると計算時間が変わる理由

今回利用した二次元の整数配列は intArr[10000, 10000] の大きさなので、必要なメモリ量は、

10,000 x 10,000 x 4バイト = 100M x 4 = 400M バイト

だ。

最初に示した 4 x 3 = 12 要素の配列の場合にはメモリ上に以下の矢印で示す順番にデータが配置される。

//                        [i, j]
int[,] intArray2 = new int[4, 3] {
    //         j=0   1   2
    /* i=0 */ { 00, 01, 02 },     // 　00 → →
    /* i=1 */ { 10, 11, 12 },     //   → → →　　メモリ上には矢印順
    /* i=2 */ { 20, 21, 22 },     //   → → →　　に配置される
    /* i=3 */ { 30, 31, 32 },     //   → → 32  
};

10,000 x 10,000 = 1億個（100メガ）の要素の場合も同様に配置される。

つまり、メモリ上には一つのiに対して、j=0～9,999に対応する配列要素が連続に10000個並んでいる。

それが終わると次のiの値に対して、同じくj=0～9,999に対応する配列要素が連続に10000個並んでいる。

以下、その繰り返し。

 

遅かった方の二番目のループでは以下のようにjを固定してiを0～9,999まで増やしている。

for (int j = 0; j < jLen; j++)
{
    for (int i = 0; i < iLen; i++)
    {
        intArr[i, j] = i * iLen + j;
    }
}   

そうすると内側のiループでiが変化する度に、メモリ上では10000要素先のデータを参照する事になる。

つまり、

10000 x 4バイト = 40キロバイト

なので、iが変化する度にメモリの40キロバイト先に計算結果を書き込む事になる。

ページングとかキャッシュとか言う用語を良く聞くと思うが、パソコンの実メモリは数ギガバイトくらいが一般的だ。

もし4GBのパソコンで上のサンプルを実行すると、配列要素だけで400メガバイトもメモリを利用する。

それは実メモリ4GBの10分の１に相当するので、上のサンプルプログラムが必要とする400メガバイトは実メモリ上に全部を確保出来なくは無いが、Windows上では多くのプログラムが同時並行的に動いているので、一つのプログラムが巨大なメモリを占有してしまうと、他のプロセスが動かないなどの弊害が出る。

その辺りを解決する技術がページングとかキャッシュと言うやつだが、詳しい説明は各自調べて頂くとして、ページングでメモリを管理するOSではこの400メガバイトはハードディスク上に確保されて、計算に必要な部分が実メモリ上に読み込まれて計算に使われる。

例えばページングの単位が例えば4メガバイトだとすると、ハードディスクから4メガバイト分のデータを読み込んで計算に使う。その範囲外の配列データが必要になったら再びページングで読み込み。

と言う事は、まあ、iを変化させるとメモリ上を大きく移動するので、ページングが発生し易い。その結果、ハードディスクの読み書き速度が計算時間に大きく影響して、計算時間が掛かると言う訳だ。まあ、ワテの説明もあまり上手では無いので、間違いなどありましたらご指摘お願いします。

VB.NET版のサンプルプログラム

VB.NETとC#は、どちらも .NET Framework の技術基盤の上で実行されるので、兄弟みたいなもんだ。いや姉妹かも分からない。そんな事はどうでも良いが、両者は互いに簡単に変換できる。

C# to VB.NET online converter

などのキーワードで検索すると幾つかのサイトがヒットする。

その中で、たまたま見付けた

Code Converter C# to VB and VB to C# – Telerik

Telerik Code Converter by Progress is free online code converter from C# to VB and from VB to C#. No registration requir...

converter.telerik.com

を使って冒頭のC#サンプルプログラムをVB.NETに変換してみた。

Sub Main()
    Test1_整数配列.test1()
    'Console.ReadKey()
End Sub

 

Class Test1_整数配列
    Public Shared Sub test1()
        'object[,] objArray = new object[4, 3];
 
        Dim intArray As Integer(,) = New Integer(3, 2) {}
 
        LibClass.二次元配列の中身を表示する(intArray, NameOf(intArray))
 
        'intArray2[i, j]
        '         j=0   1   2
        ' i=0     　00 → →
        ' i=1       → → →　　メモリ上には矢印順
        ' i=2       → → →　　に配置される
        ' i=3       → → 32  
        Dim intArray2 As Integer(,) = New Integer(3, 2) {
            {0, 1, 2},
            {10, 11, 12},
            {20, 21, 22},
            {30, 31, 32}}
 
        LibClass.二次元配列の中身を表示する(intArray2, NameOf(intArray2))
 
         Dim sizeOfInt = 4
        Console.WriteLine(sizeOfInt)        ' 4
 
    End Sub
 
End Class
 
Class LibClass
    Public Shared Sub 二次元配列の中身を表示する(intArr As Integer(,), arrName As String)
 
        'string nameOfVariable = nameof(intArr);
        Dim typeOfVariable As String = intArr.[GetType]().ToString()
        '"System.Int32[,]"
        Dim space As String = New [String](" "c, arrName.Length + 1)
 
        Console.Write(space & Convert.ToString("   j ="))
        For j As Integer = intArr.GetLowerBound(1) To intArr.GetUpperBound(1)
            Console.Write("{0,9:d}", j)
        Next
        Console.WriteLine()
  
 
        Console.Write(space & Convert.ToString("i     "))
        For j As Integer = intArr.GetLowerBound(1) To intArr.GetUpperBound(1)
            Console.Write("{0,9:s}", "-----")
        Next
        Console.WriteLine("")
 
 
        For i As Integer = intArr.GetLowerBound(0) To intArr.GetUpperBound(0)
            'Console.Write("intArr({0}, j)=", i);
            Console.Write("{0}[{1}, j]=", arrName, i)
            For j As Integer = intArr.GetLowerBound(1) To intArr.GetUpperBound(1)
                Console.Write("{0,9:d}", intArr(i, j))
            Next
            Console.WriteLine()
        Next
        Console.WriteLine()
    End Sub
 End Class

その実行結果は以下の通り。

            j =        0        1        2
         i         -----    -----    -----
intArray[0, j]=        0        0        0
intArray[1, j]=        0        0        0
intArray[2, j]=        0        0        0
intArray[3, j]=        0        0        0

             j =        0        1        2
          i         -----    -----    -----
intArray2[0, j]=        0        1        2
intArray2[1, j]=       10       11       12
intArray2[2, j]=       20       21       22
intArray2[3, j]=       30       31       32

4
続行するには何かキーを押してください . . .

まあ、C#版と同じ結果になる。

まとめ

C#において二次元配列の行と列をループする場合に、そのループインデックス変数の順番が計算時間に大きく影響する事実を紹介した。

この事実は、二次元配列だけでなく、より次元の高い多次元配列でも同じである。

さらに注意すべき点は、これらの事実は言語によって挙動が異なるので、その点も要注意だ。

言語によって効率的なループ順は変わる

C#の場合には、配列を

array[i, j]

とした場合には、二重ループをするなら、

for(int i=0 ; i<iLen ; i++){
   for(int j=0 ; j<jLen ; j++){
      array[i, j] = ・・・
   }
}

i, j が速い。

ところが、他の言語では逆の場合もあるので要注意だ。

FORTRANならC#とは逆になり、

DO J = 1, JEND
   DO I = 1, IEND
      ARRAY(I, J) = ・・・
   END DO
END DO

J, I の順が速い。

久しぶりにFORTRANを書いた。

まあ本物のプログラマーならFORTRANをバリバリ書けなくてはならないのは言うまでも無い。

一方、C言語やC++ではC#と同じループ順になる。

従ってC/C++/C#で書かれた何らかの数値計算プログラムで多次元配列を使っている場合には、それをFORTRANに移植する場合にはループ構造を見直す必要がある。その逆も成り立つ。

 

これであなたも数値計算プログラムやシミュレーションプログラムを書く場合には、バリバリに高速なプログラムを開発出来るようになるだろう。

とは言っても現実の状況では物事はこんなには単純ではない。

なので、粗いステップの多重ループで目的とする計算をしてみて、その時に多重ループのループ順を色々入れ替えてみるなどして、最も計算時間が速いループ順を求めておく。

そして、そのループ順で本番計算をするなどの泥臭い手法が使われる事が多いと思う（ワテの経験では）。

いずれにしても、この手の計算プログラムを書く場合には、変数がメモリ上にどのように配置されているかなども明確に意識しながら高速プログラムを書く必要がある。

C#、VB.NET、FORTRAN、C、C++のワテ推薦図書

FORTRANやるなら並列化してCPUをバリバリ使いまくるのが男だ！いや女でも。

 

C++でも高速化を目指したい。

とは言っても、高速化とかオプティマイズとか、そう言うのばかりを重要視して、コーディングが遅々として進まない人も多い。

そう言うのは駄目だな。

そう言う人は偽物。

本物のプログラマーは最短の作業時間で高速に動くプログラムを作るのだ。