[c#] C#で多次元配列と配列の配列の違いは何ですか?



Answers

多次元配列は素敵な線形メモリレイアウトを作成し、ギザギザの配列はいくつかの余分な間接レベルを意味します。

値段の高いjagged[3][6]をギザギザの配列で探しますjagged[3][6] var jagged = new int[10][5]は次のように動作します:インデックス3(配列)の要素をルックアップし、その配列内の6(値)。 この場合の各ディメンションには、追加のルックアップがあります(これは高価なメモリアクセスパターンです)。

多次元配列はメモリに線形に配置され、実際の値はインデックスを掛け合わせることによって求められます。 しかし、配列var mult = new int[10,30]場合、その多次元配列のLengthプロパティは、要素の合計数、つまり10 * 30 = 300を返します。

ギザギザの配列のRankプロパティは常に1ですが、多次元配列は任意のランクを持つことができます。 任意の配列のGetLengthメソッドを使用して、各次元の長さを取得できます。 この例の多次元配列では、 mult.GetLength(1)は30を返します。

多次元配列の索引付けは高速です。 例えばこの例では多次元配列mult[1,7] = 30 * 1 + 7 = 37の場合、そのインデックス37の要素を取得します。これは、1つのメモリ位置だけが関係するため、配列のアドレス。

したがって多次元配列は連続的なメモリブロックを割り当てますが、ギザギザの配列は正方形である必要はありません。たとえば、 jagged[1].Lengthjagged[2].Lengthと同じであるjagged[1].Lengthはありません。多次元配列で真です。

パフォーマンス

パフォーマンスが向上し、多次元配列が高速になるはずです。 ずっと速いですが、本当に悪いCLR実装のためにそうではありません。

 23.084  16.634  15.215  15.489  14.407  13.691  14.695  14.398  14.551  14.252 
 25.782  27.484  25.711  20.844  19.607  20.349  25.861  26.214  19.677  20.171 
  5.050   5.085   6.412   5.225   5.100   5.751   6.650   5.222   6.770   5.305 

最初の行はギザギザの配列のタイミングで、2番目の行は多次元配列を示し、3番目の配列はそれがどのようにすべきかを示しています。 プログラムは以下に示されています、FYIこれはモノラルでテストされています。 (ウィンドウのタイミングは、主にCLRの実装の違いによって大きく異なります)。

ウィンドウ上では、ギザギザの配列のタイミングが非常に優れています。多次元配列のルックアップがどのようなものであるべきかについての私の解釈とほぼ同じです。「Single()」を参照してください。 悲しいことに、WindowsのJITコンパイラは本当に愚かですが、残念なことに、これらのパフォーマンスの議論は難しくなります。あまりにも多くの矛盾があります。

これらは、私が窓で得たタイミングです、ここでは同じ取引、最初の行はギザギザの配列、多次元と多次元の2番目と3番目の実装です。

  8.438   2.004   8.439   4.362   4.936   4.533   4.751   4.776   4.635   5.864
  7.414  13.196  11.940  11.832  11.675  11.811  11.812  12.964  11.885  11.751
 11.355  10.788  10.527  10.541  10.745  10.723  10.651  10.930  10.639  10.595

ソースコード:

using System;
using System.Diagnostics;
static class ArrayPref
{
    const string Format = "{0,7:0.000} ";
    static void Main()
    {
        Jagged();
        Multi();
        Single();
    }

    static void Jagged()
    {
        const int dim = 100;
        for(var passes = 0; passes < 10; passes++)
        {
            var timer = new Stopwatch();
            timer.Start();
            var jagged = new int[dim][][];
            for(var i = 0; i < dim; i++)
            {
                jagged[i] = new int[dim][];
                for(var j = 0; j < dim; j++)
                {
                    jagged[i][j] = new int[dim];
                    for(var k = 0; k < dim; k++)
                    {
                        jagged[i][j][k] = i * j * k;
                    }
                }
            }
            timer.Stop();
            Console.Write(Format,
                (double)timer.ElapsedTicks/TimeSpan.TicksPerMillisecond);
        }
        Console.WriteLine();
    }

    static void Multi()
    {
        const int dim = 100;
        for(var passes = 0; passes < 10; passes++)
        {
            var timer = new Stopwatch();
            timer.Start();
            var multi = new int[dim,dim,dim];
            for(var i = 0; i < dim; i++)
            {
                for(var j = 0; j < dim; j++)
                {
                    for(var k = 0; k < dim; k++)
                    {
                        multi[i,j,k] = i * j * k;
                    }
                }
            }
            timer.Stop();
            Console.Write(Format,
                (double)timer.ElapsedTicks/TimeSpan.TicksPerMillisecond);
        }
        Console.WriteLine();
    }

    static void Single()
    {
        const int dim = 100;
        for(var passes = 0; passes < 10; passes++)
        {
            var timer = new Stopwatch();
            timer.Start();
            var single = new int[dim*dim*dim];
            for(var i = 0; i < dim; i++)
            {
                for(var j = 0; j < dim; j++)
                {
                    for(var k = 0; k < dim; k++)
                    {
                        single[i*dim*dim+j*dim+k] = i * j * k;
                    }
                }
            }
            timer.Stop();
            Console.Write(Format,
                (double)timer.ElapsedTicks/TimeSpan.TicksPerMillisecond);
        }
        Console.WriteLine();
    }
}
Question

多次元配列double[,]と配列の配列double[][]の違いは何ですか?

違いがある場合は、それぞれに最適なものは何ですか?




序文:このコメントはshareに対処shareことを意図していますが、SOの愚かな評判システムのために、私はそれが所属する場所に投稿することはできません。

メソッド呼び出しのために、他のものより遅いというあなたの主張は正しいものではありません。 より複雑な境界チェックアルゴリズムのため、一方は他方よりも遅い。 ILではなく、コンパイルされたアセンブリで、これを簡単に確認することができます。 たとえば、私の4.5のインストールでは、eaxとedxに格納されたインデックスを持つecxが指し示す2次元配列に格納された要素(edxのポインタ経由)にアクセスすると、次のようになります。

sub eax,[ecx+10]
cmp eax,[ecx+08]
jae oops //jump to throw out of bounds exception
sub edx,[ecx+14]
cmp edx,[ecx+0C]
jae oops //jump to throw out of bounds exception
imul eax,[ecx+0C]
add eax,edx
lea edx,[ecx+eax*4+18]

ここでは、メソッド呼び出しによるオーバーヘッドがないことがわかります。 境界チェックは、ジグザグ配列では提供されていない機能であるゼロ以外のインデックスの可能性のために非常に畳み込まれています。 ゼロ以外の場合のサブ、cmp、およびjmpsを削除すると、コードは(x*y_max+y)*sizeof(ptr)+sizeof(array_header)ます。 この計算は、要素へのランダムアクセスのための何か他のものとほぼ同じくらい高速です(1回の乗算は1回のシフトで置き換えることができます.2ビットの累乗としてサイズを決める理由があります)。

もう1つの問題は、現代のコンパイラが、単一次元配列を反復しながら要素アクセスのネストされた境界チェックを最適化するケースがたくさんあることです。 結果は、基本的に配列の連続したメモリ上のインデックスポインタを進めるコードです。 多次元配列に対する純粋な反復には、通常ネストされたロジックの余分なレイヤが含まれるため、コンパイラは操作を最適化する可能性が低くなります。 そのため、単一の要素にアクセスする際の境界チェックのオーバーヘッドが配列の寸法とサイズに関して一定の実行時間に償却されるにもかかわらず、その差を測定する簡単なテストケースが実行に何時間もかかることがあります。




.NETで多次元配列がギザギザの配列より速いので、私はこれを更新したいと思います 。 私はJohn Leidegrenのテストを実行しました。これらは.NET Core 2.0プレビュー2の結果です。私は背景の影響を受けないように寸法値を大きくしました。

Debug (code optimalization disabled)
Running jagged 
187.232 200.585 219.927 227.765 225.334 222.745 224.036 222.396 219.912 222.737 

Running multi-dimensional  
130.732 151.398 131.763 129.740 129.572 159.948 145.464 131.930 133.117 129.342 

Running single-dimensional  
 91.153 145.657 111.974  96.436 100.015  97.640  94.581 139.658 108.326  92.931 


Release (code optimalization enabled)
Running jagged 
108.503 95.409 128.187 121.877 119.295 118.201 102.321 116.393 125.499 116.459 

Running multi-dimensional 
 62.292  60.627  60.611  60.883  61.167  60.923  62.083  60.932  61.444  62.974 

Running single-dimensional 
 34.974  33.901  34.088  34.659  34.064  34.735  34.919  34.694  35.006  34.796 

私は逆アセンブルを見て、これは私が見つけたものです

jagged[i][j][k] = i * j * k; 実行するために必要な34の命令

multi[i, j, k] = i * j * k; 実行するために必要な11の命令

single[i * dim * dim + j * dim + k] = i * j * k; 実行するには23の命令が必要

私は単次元配列がまだ多次元より高速であった理由を特定することはできませんでしたが、私はCPU上で行われた最適化




他の答えに加えて、多次元配列はヒープ上の大きなチャンクオブジェクトとして割り当てられることに注意してください。 これにはいくつかの意味があります。

  1. いくつかの多次元配列は、同等のギザギザの配列の対応がない場合は、ラージオブジェクトヒープ(LOH)に割り当てられます。
  2. GCは多次元配列を割り当てるために連続した1つの空きメモリブロックを見つける必要がありますが、ギザギザの配列はヒープフラグメンテーションによるギャップを埋めることができるかもしれません...これは通常、コンパクションしかし、LOHはデフォルトで圧縮されません(あなたはそれを求めなければなりません。そして、あなたがそれを必要とするたびに尋ねなければなりません)。
  3. 多次元配列の場合は、 <gcAllowVeryLargeObjects>を調べて、ぎざぎざの配列だけを使用する場合は問題が発生する前にしてください。



Links