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

Jakie są różnice między tablicami wielowymiarowymi double[,]a tablicami tablic double[][]w języku C #?

Jeśli jest jakaś różnica, jakie jest najlepsze zastosowanie dla każdego z nich?

Tablice tablic (tablice postrzępione) są szybsze niż tablice wielowymiarowe i można je efektywniej wykorzystywać. Tablice wielowymiarowe mają ładniejszą składnię.

Jeśli napiszesz prosty kod za pomocą tablic postrzępionych i wielowymiarowych, a następnie sprawdzisz skompilowany zestaw za pomocą deasemblera IL, zobaczysz, że przechowywanie i pobieranie z tablic postrzępionych (lub jednowymiarowych) jest prostymi instrukcjami IL, podczas gdy te same operacje dla tablic wielowymiarowych są metodą inwokacje, które zawsze są wolniejsze.

Rozważ następujące metody:

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

Ich IL będzie następujący:

.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

Korzystając z tablic poszarpanych, można łatwo wykonywać takie operacje, jak zamiana wierszy i zmiana rozmiaru wierszy. Być może w niektórych przypadkach użycie tablic wielowymiarowych będzie bardziej bezpieczne, ale nawet Microsoft FxCop mówi, że tablice postrzępione powinny być używane zamiast wielowymiarowych, gdy używasz go do analizy swoich projektów.

Wielowymiarowa tablica tworzy ładny układ pamięci liniowej, a poszarpana tablica sugeruje kilka dodatkowych poziomów pośrednich.

Wyszukiwanie wartości jagged[3][6]w postrzępionej tablicy var jagged = new int[10][5]działa w następujący sposób: Wyszukaj element o indeksie 3 (który jest tablicą) i wyszukaj element o indeksie 6 w tej tablicy (która jest wartością). W tym przypadku dla każdego wymiaru istnieje dodatkowe wyszukiwanie (jest to drogi wzorzec dostępu do pamięci).

Wielowymiarowa tablica jest ułożona liniowo w pamięci, rzeczywistą wartość uzyskuje się poprzez pomnożenie indeksów. Jednak biorąc pod uwagę tablicę var mult = new int[10,30], Lengthwłaściwość tej wielowymiarowej tablicy zwraca całkowitą liczbę elementów, tj. 10 * 30 = 300.

RankWłasnością postrzępionych tablicy jest zawsze 1, ale wielowymiarowa tablica może mieć dowolną rangę. GetLengthSposób według tablicy mogą być używane, aby długość każdego wymiaru. Dla tablicy wielowymiarowej w tym przykładzie mult.GetLength(1)zwraca 30.

Indeksowanie tablicy wielowymiarowej jest szybsze. np. biorąc pod uwagę tablicę wielowymiarową w tym przykładzie mult[1,7]= 30 * 1 + 7 = 37, uzyskaj element o tym indeksie 37. Jest to lepszy wzorzec dostępu do pamięci, ponieważ zaangażowana jest tylko jedna lokalizacja pamięci, która jest adresem bazowym tablicy.

Tablica wielowymiarowa alokuje zatem ciągły blok pamięci, podczas gdy tablica poszarpana nie musi być kwadratowa, np. jagged[1].LengthNie musi być równa jagged[2].Length, co byłoby prawdą dla dowolnej tablicy wielowymiarowej.

Wydajność

Pod względem wydajności tablice wielowymiarowe powinny być szybsze. Są znacznie szybsze, ale z powodu naprawdę złej implementacji 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 rząd to czasy poszarpanych tablic, drugi pokazuje tablice wielowymiarowe, a trzeci, cóż, tak właśnie powinno być. Program pokazano poniżej, do przetestowania w trybie mono. (Czasy okien są znacznie różne, głównie ze względu na warianty implementacji CLR).

W Windowsach czasy poszarpanych tablic są znacznie lepsze, mniej więcej tak samo jak moja własna interpretacja tego, jak powinien wyglądać tablica wielowymiarowa, patrz „Single ()”. Niestety, kompilator JIT dla systemu Windows jest naprawdę głupi, a to niestety utrudnia dyskusje na temat wydajności, jest zbyt wiele niespójności.

Są to czasy, które mam na oknach, ta sama umowa tutaj, pierwszy rząd to postrzępione tablice, drugi wielowymiarowy, a trzeci moja własna implementacja wielowymiarowa, zauważ, o ile wolniej jest to w oknach 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 tablice wielowymiarowe są podobne do tabeli w DBMS.
Array of Array (postrzępiona tablica) pozwala, aby każdy element zawierał inną tablicę tego samego typu o zmiennej długości.

Jeśli więc masz pewność, że struktura danych wygląda jak tabela (stałe wiersze / kolumny), możesz użyć tablicy wielowymiarowej. Poszarpana tablica to stałe elementy i każdy element może pomieścić tablicę o zmiennej długości

Np. Kod Psuedocode:

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

Potraktuj powyższe jako tabelę 2x2:

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 odpowiedzieć na odpowiedź udzieloną przez okutane , ale z powodu głupiego systemu reputacji SO nie mogę opublikować go tam, gdzie należy.

Twoje twierdzenie, że jedno jest wolniejsze od drugiego z powodu wywołań metod, jest nieprawidłowe. Jeden jest wolniejszy od drugiego z powodu bardziej skomplikowanych algorytmów sprawdzania granic. Możesz to łatwo zweryfikować, patrząc nie na IL, ale na skompilowany zestaw. Na przykład, w 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 narzutu wywołania metod. Sprawdzanie granic jest po prostu bardzo skomplikowane dzięki możliwości indeksów niezerowych, co jest funkcją niedostępną w przypadku tablic poszarpanych. Jeśli usuniemy napisy sub, cmp i jmps dla przypadków niezerowych, kod prawie się rozwiązuje (x*y_max+y)*sizeof(ptr)+sizeof(array_header). Obliczenia te są prawie tak szybkie (jeden mnożnik można zastąpić przesunięciem, ponieważ to właśnie dlatego wybieramy bajty, które mają być wielkościami dwóch bitów), jak wszystko inne w celu losowego dostępu do elementu.

Inną komplikacją jest to, że istnieje wiele przypadków, w których nowoczesny kompilator zoptymalizuje sprawdzanie zagnieżdżonych granic pod kątem dostępu do elementów podczas iteracji po tablicy jednowymiarowej. Wynikiem jest kod, który zasadniczo przesuwa wskaźnik indeksu nad ciągłą pamięcią tablicy. Naiwna iteracja w przypadku tablic wielowymiarowych zazwyczaj wymaga dodatkowej warstwy zagnieżdżonej logiki, więc kompilator ma mniejsze szanse na optymalizację operacji. Tak więc, nawet jeśli narzut związany z dostępem do pojedynczego elementu amortyzuje się do stałego czasu działania w odniesieniu do wymiarów i rozmiarów tablicy, wykonanie prostej próby testowej w celu zmierzenia różnicy może potrwać wiele razy dłużej.

Chciałbym to zaktualizować, ponieważ w .NET Core tablice wielowymiarowe są szybsze niż tablice poszarpane . Przeprowadziłem testy od Johna Leidegrena i są to wyniki podglądu .NET Core 2.0. Zwiększiłem wartość wymiaru, aby wszelkie możliwe wpływy 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 dezasemblacji i właśnie to 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 wykonania

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

Nie byłem w stanie zidentyfikować, dlaczego tablice jednowymiarowe były nadal szybsze niż wielowymiarowe, ale zgaduję, że ma to związek z pewną optymalizacją procesora

Tablice wielowymiarowe są matrycami (n-1) -dimension.

Tak więc int[,] square = new int[2,2]macierz kwadratowa 2x2, int[,,] cube = new int [3,3,3]to macierz kwadratowa 3x3. Proporcjonalność nie jest wymagana.

Poszarpane tablice to po prostu tablica tablic - tablica, w której każda komórka zawiera tablicę.

Więc MDA są proporcjonalne, JD może nie być! Każda komórka może zawierać tablicę o dowolnej długości!

Mogło to zostać wspomniane w powyższych odpowiedziach, ale nie wprost: w tablicy poszarpanej można użyć array[row]do odwołania całego wiersza danych, ale nie jest to dozwolone w przypadku tablic multi-d.

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

1. Niektóre tablice wielowymiarowe zostaną przydzielone na stos dużych obiektów (LOH), gdzie w przeciwnym razie ich równoważne odpowiedniki w postaci poszarpanej tablicy nie byłyby dostępne.
2. GC będzie musiał znaleźć pojedynczy ciągły wolny blok pamięci, aby przydzielić tablicę wielowymiarową, podczas gdy tablica poszarpana może być w stanie wypełnić luki spowodowane fragmentacją sterty ... to zwykle nie jest problem w .NET z powodu zagęszczenia , ale LOH nie jest domyślnie kompaktowany (musisz o to poprosić i musisz pytać za każdym razem, gdy chcesz).
3. Będziemy chcieli przyjrzeć się <gcAllowVeryLargeObjects>na wielowymiarowych tablicach sposób zanim sprawa zostanie kiedykolwiek wymyślić, jeśli tylko kiedykolwiek wykorzystać postrzępione tablic.

Analizuję pliki .il generowane przez ildasm, aby zbudować bazę danych zestawów, klas, metod i procedur przechowywanych na potrzeby konwersji. Natknąłem się na następujące, które przerwały moją analizę.

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

Książka Expert .NET 2.0 IL Assembler autorstwa Serge Lidin, Apress, opublikowana w 2006 r., Rozdział 8, Typy pierwotne i podpisy, s. 149-150.

<type>[]jest nazywany wektorem <type>,

<type>[<bounds> [<bounds>**] ] jest nazywany tablicą <type>

**środki mogą być powtarzane, [ ]środki opcjonalne.

Przykłady: Let <type> = int32.

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

2) int32[2...5]jest jednowymiarową tablicą dolnej granicy 2 i rozmiaru 4.

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

Tomek