Jakie są różnice między wielowymiarową tablicą a tablicą tablic w C#?

Wielowymiarowa tablica tworzy ładny układ pamięci liniowej, podczas gdy tablica postrzępiona implikuje kilka dodatkowych poziomów indrection.

Szukanie wartości jagged[3][6] w postrzępionej tablicy var jagged = new int[10][5] działa tak: wyszukaj element w indeksie 3 (który jest tablicą) i wyszukaj element w indeksie 6 w tej tablicy (który jest wartością). Dla każdego wymiaru w tym przypadku istnieje dodatkowe spojrzenie w górę (jest to kosztowny wzór dostępu do pamięci).

Wielowymiarowa tablica jest ułożona liniowo w pamięci, rzeczywista wartość znajduje się mnożąc razem indeksy. Jednak biorąc pod uwagę tablicę var mult = new int[10,30], właściwość Length tej wielowymiarowej tablicy zwraca całkowitą liczbę elementów, tj. 10 * 30 = 300.

Właściwość Rank tablicy postrzępionej jest zawsze równa 1, ale tablica wielowymiarowa może mieć dowolną rangę. Do uzyskania długości każdego wymiaru można użyć metody GetLength dowolnej tablicy. Dla tablicy wielowymiarowej w tym przykładzie mult.GetLength(1) zwraca 30.

Indeksowanie wielowymiarowa tablica jest szybsza. np. biorąc pod uwagę wielowymiarową tablicę w tym przykładzie mult[1,7] = 30 * 1 + 7 = 37, zdobądź element w indeksie 37. Jest to lepszy wzorzec dostępu do pamięci, ponieważ dotyczy tylko jednej lokalizacji pamięci, która jest adresem bazowym tablicy.

Wielowymiarowa tablica przydziela zatem ciągły blok pamięci, podczas gdy postrzępiona tablica nie musi być kwadratowa, np. jagged[1].Length nie musi być równa jagged[2].Length, co byłoby prawdziwe dla dowolnego wielowymiarowego / align = "left" /

Wydajność

Wydajność, wielowymiarowe tablice powinny być szybsze. Dużo szybciej, ale ze względu na naprawdę złą implementację CLR nie są.

 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 

Pierwszy wiersz to timingi postrzępionych tablic, drugi pokazuje tablice wielowymiarowe, a trzeci, tak powinno być. Program jest pokazany poniżej, FYI to było testowane uruchomienie mono. (Czasy okien są znacznie różne, głównie ze względu na różnice w implementacji CLR).

On windows, czasy postrzępionych tablic są znacznie lepsze, tak samo jak moja własna interpretacja tego, jak powinna wyglądać wielowymiarowa tablica, patrz'Single ()'. Niestety Windows JIT-kompilator jest naprawdę głupi, a to niestety utrudnia te dyskusje o wydajności, jest zbyt wiele niespójności.

To są timingi, które mam na Windowsie, to samo tutaj, pierwszy wiersz to postrzępione tablice, drugi wielowymiarowy, a trzeci moja własna implementacja wielowymiarowe, zauważ, o ile wolniej jest to w windows w porównaniu do mono.

  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

Kod źródłowy:

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

Po prostu wielowymiarowe tablice są podobne do tabeli w DBMS.
Array of Array (jagged array) pozwala każdemu elementowi trzymać inną tablicę tego samego typu o zmiennej długości.

Jeśli więc jesteś pewien, że struktura danych wygląda jak tabela (stałe wiersze/kolumny), możesz użyć tablicy wielowymiarowej. Postrzępione tablice są stałymi elementami i każdy element może posiadać tablicę o zmiennej długości

Np. Psuedocode:

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

Pomyśl o powyższym jako o 2x2 Tabela:

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

Pomyśl o powyższym, ponieważ każdy wiersz ma zmienną liczbę kolumn:

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

Przedmowa: Ten komentarz ma na celu adres odpowiedzi udzielonej przez okutane , ale z powodu głupiego systemu reputacji SO, nie mogę go zamieścić tam, gdzie jego miejsce.

Twoje twierdzenie, że jedna jest wolniejsza od drugiej z powodu wywołania metody, nie jest poprawne. Jeden jest wolniejszy od drugiego ze względu na bardziej skomplikowane algorytmy sprawdzania granic. Możesz to łatwo zweryfikować, patrząc nie na IL, ale na skompilowany zespół. Na przykład na mojej instalacji 4.5, dostęp do elementu (poprzez wskaźnik w edx) przechowywanego w dwuwymiarowej tablicy wskazywanej przez ecx z indeksami przechowywanymi w eax i edx wygląda następująco:

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]

Tutaj możesz zobaczyć, że nie ma żadnych kosztów z wywołań metod. Sprawdzanie granic jest po prostu bardzo zawiłe dzięki możliwości niezerowych indeksów, co jest funkcjonalnością niedostępną w przypadku postrzępionych tablic. Jeśli usuniemy sub,cmp i JMP dla niezerowych przypadków, kod praktycznie rozwiązuje się do (x*y_max+y)*sizeof(ptr)+sizeof(array_header). Obliczenie to jest mniej więcej tak szybko (jeden mnożnik może zostać zastąpiony przesunięciem, ponieważ to jest cały powód, dla którego wybieramy bajty jako potęgi dwóch bitów), jak Wszystko inne dla losowego dostępu do elementu.

Kolejną komplikacją jest to, że jest wiele przypadków, w których nowoczesny kompilator optymalizuje zagnieżdżone ograniczenia-sprawdzając dostęp do elementu podczas iteracji tablicy jednowymiarowej. Rezultatem jest kod, który w zasadzie po prostu przesuwa wskaźnik indeksu nad sąsiadującą pamięcią / align = "left" / Naiwna iteracja nad tablicami wielowymiarowymi zazwyczaj wymaga dodatkowej warstwy zagnieżdżonej logiki, więc kompilator jest mniej podatny na optymalizację operacji. Tak więc, nawet jeśli narzut sprawdzający granice dostępu do pojedynczego elementu zamortyzuje się do stałego trybu runtime w odniesieniu do wymiarów i rozmiarów tablicy, wykonanie prostego przypadku testowego do zmierzenia różnicy może potrwać wiele razy dłużej.

Chciałbym zaktualizować na ten temat, ponieważ w . Net Core wielowymiarowe tablice są szybsze niż postrzępione tablice . Przeprowadziłem testy z Johna Leidegrena i oto wyniki na.Net Core 2.0 preview 2. Zwiększyłem wartość wymiaru, aby wszelkie możliwe wpływy z aplikacji w tle były mniej widoczne.

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 

Zajrzałem do demontażu i oto co znalazłem

jagged[i][j][k] = i * j * k; potrzebne 34 instrukcje do wykonania

multi[i, j, k] = i * j * k; potrzebne 11 instrukcji do execute

single[i * dim * dim + j * dim + k] = i * j * k; potrzebne 23 instrukcje do wykonania

Nie byłem w stanie zidentyfikować, dlaczego tablice jednowymiarowe są nadal szybsze niż wielowymiarowe, ale domyślam się, że ma to związek z pewną optymalizacją wykonaną na CPU

Tablice wielowymiarowe są (n-1) macierzami wymiarowymi.

Więc int[,] square = new int[2,2] jest macierzą kwadratową 2x2, {[1] } jest macierzą sześcian-kwadrat 3x3. Proporcjonalność nie jest wymagana.

Postrzępione Tablice to po prostu tablica tablic - tablica, w której każda komórka zawiera tablicę.

Mogło to być wspomniane w powyższych odpowiedziach, ale nie jawnie: w przypadku tablicy postrzępionej możesz użyć array[row] do odwołania całego wiersza danych, ale nie jest to dozwolone dla tablic multi-D.

Oprócz innych odpowiedzi, zauważ, że tablica wielowymiarowa jest przydzielana jako jeden duży, masywny obiekt na stercie. Ma to pewne implikacje:

1. niektóre wielowymiarowe tablice zostaną przydzielone na stercie dużych obiektów (Large Object Heap, LOH), gdzie ich odpowiedniki z postrzępionymi tablicami inaczej by nie miały.
2. GC będzie musiał znaleźć pojedynczy przylegający wolny blok pamięci, aby przydzielić wielowymiarową tablicę, podczas gdy postrzępiona tablica może być w stanie wypełnić luki spowodowane fragmentacją sterty... zazwyczaj nie jest to problem w. Net z powodu zagęszczania, ale LOH nie jest domyślnie zagęszczany(musisz o to pytać i musisz pytać za każdym razem, gdy tego chcesz).
3. będziesz chciał przyjrzeć się <gcAllowVeryLargeObjects> dla tablic wielowymiarowych sposób zanim problem kiedykolwiek pojawi się, jeśli kiedykolwiek używasz tylko postrzępionych tablic.

Analizuję pliki. il generowane przez ildasm w celu zbudowania bazy asemnblies, klas, metod i procedur składowanych do użycia podczas konwersji. Natknąłem się na następujące, które złamały moje parsowanie.

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

<type>[] oznacza Wektor <type>,

<type>[<bounds> [<bounds>**] ] jest określana tablicą <type>

** środki mogą być powtórzone, [ ] oznacza opcjonalne.

Przykłady: Let <type> = int32.

1) int32[...,...] jest dwuwymiarową tablicą niezdefiniowanych dolnych granic i rozmiarów

2) int32[2...5] jest jednowymiarową tablicą o dolnej granicy 2 i wielkości 4.

3) int32[0...,0...] jest dwuwymiarową tablicą dolnych granic 0 i niezdefiniowanego rozmiaru.

Tom