Was sind die Unterschiede zwischen einem mehrdimensionalen Array und einem Array von Arrays in C #?

Was sind die Unterschiede zwischen mehrdimensionalen Arrays double[,]und Array-of-Arrays double[][]in C #?

Wenn es einen Unterschied gibt, was ist die beste Verwendung für jeden?

Arrays von Arrays (gezackte Arrays) sind schneller als mehrdimensionale Arrays und können effektiver verwendet werden. Mehrdimensionale Arrays haben eine schönere Syntax.

Wenn Sie einfachen Code mit gezackten und mehrdimensionalen Arrays schreiben und dann die kompilierte Assembly mit einem IL-Disassembler untersuchen, werden Sie feststellen, dass das Speichern und Abrufen von gezackten (oder eindimensionalen) Arrays einfache IL-Anweisungen sind, während dieselben Operationen für mehrdimensionale Arrays Methoden sind Aufrufe, die immer langsamer sind.

Betrachten Sie die folgenden Methoden:

static void SetElementAt(int[][] array, int i, int j, int value)
{
    array[i][j] = value;
}

static void SetElementAt(int[,] array, int i, int j, int value)
{
    array[i, j] = value;
}

Ihre IL wird die folgende sein:

.method private hidebysig static void  SetElementAt(int32[][] 'array',
                                                    int32 i,
                                                    int32 j,
                                                    int32 'value') cil managed
{
  // Code size       7 (0x7)
  .maxstack  8
  IL_0000:  ldarg.0
  IL_0001:  ldarg.1
  IL_0002:  ldelem.ref
  IL_0003:  ldarg.2
  IL_0004:  ldarg.3
  IL_0005:  stelem.i4
  IL_0006:  ret
} // end of method Program::SetElementAt

.method private hidebysig static void  SetElementAt(int32[0...,0...] 'array',
                                                    int32 i,
                                                    int32 j,
                                                    int32 'value') cil managed
{
  // Code size       10 (0xa)
  .maxstack  8
  IL_0000:  ldarg.0
  IL_0001:  ldarg.1
  IL_0002:  ldarg.2
  IL_0003:  ldarg.3
  IL_0004:  call       instance void int32[0...,0...]::Set(int32,
                                                           int32,
                                                           int32)
  IL_0009:  ret
} // end of method Program::SetElementAt

Wenn Sie gezackte Arrays verwenden, können Sie problemlos Vorgänge wie Zeilentausch und Zeilengrößenänderung ausführen. In einigen Fällen ist die Verwendung mehrdimensionaler Arrays möglicherweise sicherer, aber selbst Microsoft FxCop weist darauf hin, dass gezackte Arrays anstelle von mehrdimensionalen Arrays verwendet werden sollten, wenn Sie sie zur Analyse Ihrer Projekte verwenden.

Ein mehrdimensionales Array erstellt ein schönes lineares Speicherlayout, während ein gezacktes Array mehrere zusätzliche Indirektionsebenen impliziert.

Das Nachschlagen des Werts jagged[3][6]in einem gezackten Array var jagged = new int[10][5]funktioniert folgendermaßen: Suchen Sie das Element bei Index 3 (das ein Array ist) und das Element bei Index 6 in diesem Array (das ein Wert ist). In diesem Fall gibt es für jede Dimension eine zusätzliche Suche (dies ist ein teures Speicherzugriffsmuster).

Ein mehrdimensionales Array wird linear im Speicher angeordnet, der tatsächliche Wert wird durch Multiplizieren der Indizes ermittelt. In Anbetracht des Arrays var mult = new int[10,30]gibt die LengthEigenschaft dieses mehrdimensionalen Arrays jedoch die Gesamtzahl der Elemente zurück, dh 10 * 30 = 300.

Die RankEigenschaft eines gezackten Arrays ist immer 1, aber ein mehrdimensionales Array kann einen beliebigen Rang haben. Die GetLengthMethode eines beliebigen Arrays kann verwendet werden, um die Länge jeder Dimension zu ermitteln. Für das mehrdimensionale Array in diesem Beispiel wird mult.GetLength(1)30 zurückgegeben.

Die Indizierung des mehrdimensionalen Arrays ist schneller. Wenn Sie beispielsweise das mehrdimensionale Array in diesem Beispiel mult[1,7]= 30 * 1 + 7 = 37 haben, erhalten Sie das Element an diesem Index 37. Dies ist ein besseres Speicherzugriffsmuster, da nur ein Speicherort beteiligt ist, nämlich die Basisadresse des Arrays.

Ein mehrdimensionales Array weist daher einen kontinuierlichen Speicherblock zu, während ein gezacktes Array nicht quadratisch sein muss, z. B. jagged[1].Lengthnicht gleich sein muss jagged[2].Length, was für jedes mehrdimensionale Array zutreffen würde.

Performance

In Bezug auf die Leistung sollten mehrdimensionale Arrays schneller sein. Viel schneller, aber aufgrund einer wirklich schlechten CLR-Implementierung nicht.

 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 

Die erste Zeile enthält Timings von gezackten Arrays, die zweite zeigt mehrdimensionale Arrays und die dritte, so sollte es sein. Das Programm ist unten gezeigt, FYI dies wurde mit Mono getestet. (Die Windows-Timings sind sehr unterschiedlich, hauptsächlich aufgrund der Variationen der CLR-Implementierung.)

Unter Windows sind die Timings der gezackten Arrays weit überlegen, ungefähr so ​​wie meine eigene Interpretation, wie ein mehrdimensionales Array aussehen sollte, siehe 'Single ()'. Leider ist der Windows JIT-Compiler wirklich dumm, und dies macht diese Leistungsdiskussionen leider schwierig, es gibt zu viele Inkonsistenzen.

Dies sind die Timings, die ich für Windows erhalten habe, das gleiche gilt hier, die erste Zeile sind gezackte Arrays, die zweite mehrdimensionale und die dritte meine eigene Implementierung von mehrdimensional. Beachten Sie, wie viel langsamer dies bei Windows im Vergleich zu Mono ist.

  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

Quellcode:

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();
    }
}

Einfach ausgedrückt ähneln mehrdimensionale Arrays einer Tabelle in DBMS.
Mit Array of Array (gezacktes Array) kann jedes Element ein anderes Array mit dem gleichen Typ variabler Länge enthalten.

Wenn Sie also sicher sind, dass die Datenstruktur wie eine Tabelle aussieht (feste Zeilen / Spalten), können Sie ein mehrdimensionales Array verwenden. Gezackte Arrays sind feste Elemente und jedes Element kann ein Array variabler Länge enthalten

ZB Pseudocode:

int[,] data = new int[2,2];
data[0,0] = 1;
data[0,1] = 2;
data[1,0] = 3;
data[1,1] = 4;

Stellen Sie sich das Obige als 2x2-Tabelle vor:

1 | 2
3 | 4

int[][] jagged = new int[3][]; 
jagged[0] = new int[4] {  1,  2,  3,  4 }; 
jagged[1] = new int[2] { 11, 12 }; 
jagged[2] = new int[3] { 21, 22, 23 }; 

Stellen Sie sich das Obige als jede Zeile mit variabler Anzahl von Spalten vor:

 1 |  2 |  3 | 4
11 | 12
21 | 22 | 23

Vorwort: Dieser Kommentar soll die Antwort von okutane ansprechen , aber aufgrund des albernen Reputationssystems von SO kann ich ihn nicht dort posten, wo er hingehört .

Ihre Behauptung, dass einer aufgrund der Methodenaufrufe langsamer als der andere ist, ist nicht korrekt. Einer ist langsamer als der andere, weil die Algorithmen zur Überprüfung der Grenzen komplizierter sind. Sie können dies leicht überprüfen, indem Sie nicht die IL, sondern die kompilierte Assembly betrachten. Bei meiner 4.5-Installation sieht der Zugriff auf ein Element (über einen Zeiger in edx), das in einem zweidimensionalen Array gespeichert ist, auf das ecx zeigt, mit in eax und edx gespeicherten Indizes folgendermaßen aus:

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]

Hier sehen Sie, dass Methodenaufrufe keinen Overhead verursachen. Die Überprüfung der Grenzen ist nur sehr kompliziert, da Indizes ungleich Null möglich sind. Diese Funktion wird bei gezackten Arrays nicht angeboten. Wenn wir sub, cmp und jmps für Fälle ungleich Null entfernen, wird der Code so gut wie aufgelöst (x*y_max+y)*sizeof(ptr)+sizeof(array_header). Diese Berechnung ist ungefähr so ​​schnell (eine Multiplikation könnte durch eine Verschiebung ersetzt werden, da dies der ganze Grund ist, warum wir Bytes als Potenzen von zwei Bits auswählen) wie alles andere für den wahlfreien Zugriff auf ein Element.

Eine weitere Komplikation besteht darin, dass es viele Fälle gibt, in denen ein moderner Compiler die Prüfung verschachtelter Grenzen auf Elementzugriff optimiert, während er über ein eindimensionales Array iteriert. Das Ergebnis ist Code, der im Grunde nur einen Indexzeiger über den zusammenhängenden Speicher des Arrays bewegt. Die naive Iteration über mehrdimensionale Arrays umfasst im Allgemeinen eine zusätzliche Schicht verschachtelter Logik, sodass ein Compiler die Operation weniger wahrscheinlich optimiert. Obwohl sich der Aufwand für die Überprüfung der Grenzen beim Zugriff auf ein einzelnes Element zu einer konstanten Laufzeit in Bezug auf Array-Dimensionen und -Größen amortisiert, kann die Ausführung eines einfachen Testfalls zum Messen des Unterschieds um ein Vielfaches länger dauern.

Ich möchte dies aktualisieren, da in .NET Core mehrdimensionale Arrays schneller sind als gezackte Arrays . Ich habe die Tests von John Leidegren ausgeführt. Dies sind die Ergebnisse der .NET Core 2.0-Vorschau 2. Ich habe den Dimensionswert erhöht, um mögliche Einflüsse von Hintergrund-Apps weniger sichtbar zu machen.

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 

Ich habe mich mit Zerlegungen befasst und das habe ich gefunden

jagged[i][j][k] = i * j * k; brauchte 34 Anweisungen, um auszuführen

multi[i, j, k] = i * j * k; brauchte 11 Anweisungen, um auszuführen

single[i * dim * dim + j * dim + k] = i * j * k; brauchte 23 Anweisungen, um auszuführen

Ich konnte nicht feststellen, warum eindimensionale Arrays immer noch schneller als mehrdimensionale waren, aber ich vermute, dass dies mit einer gewissen Optimierung der CPU zu tun hat

Mehrdimensionale Arrays sind (n-1) -dimensionale Matrizen.

So int[,] square = new int[2,2]ist die quadratische Matrix 2x2, int[,,] cube = new int [3,3,3]ist eine Würfel - quadratische Matrix 3x3. Verhältnismäßigkeit ist nicht erforderlich.

Gezackte Arrays sind nur Arrays von Arrays - ein Array, in dem jede Zelle ein Array enthält.

MDA sind also proportional, JD möglicherweise nicht! Jede Zelle kann ein Array beliebiger Länge enthalten!

Dies wurde möglicherweise in den obigen Antworten erwähnt, jedoch nicht explizit: Mit einem gezackten Array können Sie array[row]eine ganze Datenzeile referenzieren, dies ist jedoch für Multi-D-Arrays nicht zulässig.

Beachten Sie zusätzlich zu den anderen Antworten, dass ein mehrdimensionales Array als ein großes, klobiges Objekt auf dem Heap zugewiesen wird. Dies hat einige Auswirkungen:

1. Einige mehrdimensionale Arrays werden auf dem Large Object Heap (LOH) zugewiesen, wo dies sonst nicht der Fall wäre.
2. Der GC muss einen einzelnen zusammenhängenden freien Speicherblock finden, um ein mehrdimensionales Array zuzuweisen, während ein gezacktes Array möglicherweise Lücken füllen kann, die durch Heap-Fragmentierung verursacht werden. Dies ist in .NET aufgrund der Komprimierung normalerweise kein Problem , aber der LOH wird nicht standardmäßig komprimiert (Sie müssen danach fragen, und Sie müssen jedes Mal fragen, wenn Sie es wollen).
3. Sie sollten <gcAllowVeryLargeObjects>nach mehrdimensionalen Arrays suchen , bevor das Problem auftritt, wenn Sie nur gezackte Arrays verwenden.

Ich analysiere von ildasm generierte .il-Dateien, um eine Datenbank mit Assemblys, Klassen, Methoden und gespeicherten Prozeduren für eine Konvertierung zu erstellen. Ich bin auf Folgendes gestoßen, was meine Analyse unterbrochen hat.

.method private hidebysig instance uint32[0...,0...] 
        GenerateWorkingKey(uint8[] key,
                           bool forEncryption) cil managed

Das Buch Expert .NET 2.0 IL Assembler von Serge Lidin, Apress, veröffentlicht 2006, Kapitel 8, Primitive Typen und Signaturen, S. 149-150, erklärt.

<type>[]wird als Vektor von <type>, bezeichnet

<type>[<bounds> [<bounds>**] ] wird als Array von bezeichnet <type>

**Mittel können wiederholt werden, [ ]Mittel optional.

Beispiele: Let <type> = int32.

1) int32[...,...]ist eine zweidimensionale Anordnung von undefinierten unteren Grenzen und Größen

2) int32[2...5]ist eine eindimensionale Anordnung der Untergrenze 2 und der Größe 4.

3) int32[0...,0...]ist eine zweidimensionale Anordnung von Untergrenzen 0 und undefinierter Größe.

Tom