multidimensional-array C#で多次元配列と配列の配列の違いは何ですか?





4 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();
    }
}
c# multidimensional-array jagged-arrays

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

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




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

メソッド呼び出しのために、他のものより遅いというあなたの主張は正しいものではありません。 より複雑な境界チェックアルゴリズムのため、一方は他方よりも遅い。 ILではなく、コンパイルされたアセンブリで、これを簡単に確認することができます。 たとえば、私の4.5のインストールでは、eaxとedxに格納されたインデックスを持つecxが指す二次元配列に格納された要素(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つの問題は、現代のコンパイラが、単一次元配列を反復しながら要素アクセスのネストされた境界チェックを最適化するケースがたくさんあることです。 結果は、基本的に配列の連続したメモリ上のインデックスポインタを進めるコードです。 多次元配列に対する純粋な反復には、通常ネストされたロジックの余分なレイヤが含まれるため、コンパイラは操作を最適化する可能性が低くなります。 したがって、単一の要素にアクセスするための境界チェックオーバーヘッドが配列の寸法とサイズに関して一定の実行時間に償却されるにもかかわらず、差を測定する簡単なテストケースは実行に何時間もかかることがあります。




多次元配列は(n-1)次元行列です。

したがって、 int[,] square = new int[2,2]は正方行列2x2ですint[,,] cube = new int [3,3,3]は3x3の正方行列です。 比例性は必要ありません。

ジグザグ配列は、配列の配列です。各セルに配列が含まれている配列です。

MDAは比例しているので、JDはそうではないかもしれません! 各セルは、任意の長さの配列を含むことができます!




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

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



Related