Odpowiedzi:
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::SetElementAtKorzystają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.
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.595Kod ź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!
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:
<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 managedKsiąż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
double[,]to tablica prostokątna, adouble[][]znana jest jako „tablica poszarpana”. Pierwszy będzie miał taką samą liczbę „kolumn” dla każdego wiersza, podczas gdy drugi (potencjalnie) będzie miał inną liczbę „kolumn” dla każdego wiersza.