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

454

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?

ecleel
quelle
7
Das erste double[,]ist ein rechteckiges Array, während double[][]es als "gezacktes Array" bekannt ist. Die erste hat die gleiche Anzahl von "Spalten" für jede Zeile, während die zweite (möglicherweise) eine andere Anzahl von "Spalten" für jede Zeile hat.
GreatAndPowerfulOz

Antworten:

334

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.

okutane
quelle
7
@ John, messe sie selbst und mache keine Annahmen.
Hosam Aly
2
@ John: Meine erste Reaktion auch, aber ich habe mich geirrt - siehe Hosams Frage für Details.
Henk Holterman
38
Mehrdimensionale Arrays sollten logischerweise effizienter sein, ihre Implementierung durch den JIT-Compiler jedoch nicht. Der obige Code ist nicht nützlich, da er keinen Array-Zugriff in einer Schleife anzeigt.
ILoveFortran
3
@Henk Holterman - Siehe meine Antwort unten. Es mag sein, dass unter Windows gezackte Arrays schnell sind, aber man muss erkennen, dass dies vollständig CLR-spezifisch ist und nicht der Fall bei zB Mono ...
John Leidegren
12
Ich weiß, dass dies eine alte Frage ist, und frage mich nur, ob die CLR seit dieser Frage für mehrdimensionale Arrays optimiert wurde.
Anthony Nichols
197

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();
    }
}
John Leidegren
quelle
2
Versuchen Sie, sie selbst zu steuern, und sehen Sie, wie beide funktionieren. Gezackte Arrays sind in .NET viel optimierter. Es kann mit der Überprüfung von Grenzen zusammenhängen, aber unabhängig vom Grund zeigen Timings und Benchmarks deutlich, dass gezackte Arrays schneller zugänglich sind als mehrdimensionale.
Hosam Aly
10
Ihre Timings scheinen jedoch zu klein zu sein (einige Millisekunden). Auf dieser Ebene treten starke Störungen durch Systemdienste und / oder Treiber auf. Machen Sie Ihre Tests viel größer, mindestens ein oder zwei Sekunden.
Hosam Aly
8
@JohnLeidegren: Die Tatsache, dass mehrdimensionale Arrays beim Indizieren einer Dimension besser funktionieren als bei einer anderen, ist seit einem halben Jahrhundert bekannt, da Elemente, die sich nur in einer bestimmten Dimension unterscheiden, nacheinander im Speicher und mit vielen Arten von Speicher (Vergangenheit) gespeichert werden und vorhanden) ist der Zugriff auf aufeinanderfolgende Elemente schneller als der Zugriff auf entfernte Elemente. Ich denke, in .net sollte man eine optimale Ergebnisindizierung durch den letzten Index erhalten, was Sie getan haben, aber das Testen der Zeit mit den ausgetauschten Indizes kann in jedem Fall informativ sein.
Supercat
16
@supercat: Mehrdimensionale Arrays in C # in gespeicherten Zeilenhauptordnung wäre langsamer ist die Reihenfolge der Subskripte Swapping da man den Speicher nicht konsekutiv Zugriff würde. Übrigens sind die angegebenen Zeiten nicht mehr genau, ich bekomme fast doppelt so schnelle Zeiten für mehrdimensionale Arrays als für gezackte Arrays (getestet auf der neuesten .NET CLR), wie es sein sollte.
Amro
9
Ich weiß, dass dies ein bisschen pedantisch ist, aber ich muss erwähnen, dass dies nicht Windows gegen Mono ist, sondern CLR gegen Mono. Sie scheinen diese manchmal zu verwirren. Die beiden sind nicht gleichwertig; Mono funktioniert auch unter Windows.
Magus
70

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
shahkalpesh
quelle
4
Dies ist wirklich wichtig, wenn Sie entscheiden, was Sie verwenden möchten. Nicht dieses Geschwindigkeits-Ding. Nun, Geschwindigkeit kann ein Faktor werden, wenn Sie ein quadratisches Array haben.
Xaser
46

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.

Eglin
quelle
1
Vielen Dank für die Korrektur der Antwort von Okutan (nicht Dmitry). Es ist ärgerlich, dass Leute auf Stackoverflow falsche Antworten geben und 250 Up-Votes erhalten, während andere korrekte Antworten geben und weit weniger bekommen. Aber am Ende ist der IL-Code irrelevant. Sie müssen die Geschwindigkeit wirklich MESSEN, um etwas über die Leistung zu sagen. Hast du das gemacht? Ich denke, der Unterschied wird lächerlich sein.
Elmue
38

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

adsamcik
quelle
14

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!

abatishchev
quelle
7

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.

lznt
quelle
4

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.
Joe Amenta
quelle
2

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

Thomas C Hutchinson
quelle