Tablice wielowymiarowe a wydajność

Wyróżniamy trzy rodzaje tablic:

  • tablice wielowymiarowe
  • tablice tablic (jagged array)
  • tablica unsafe.

Tablica wielowymiarowa

int[,] array = new int[x, y];

Alokacja tablicy jest najszybsza z pośród trzech wyminionych – to tylko jeden obiekt. Dostęp do tych tablic jest wolny. Podczas każdego obiegu pętli wykonywane są przez CLR dodatkowe obliczenia, które sprawdzają czy dany indeks nie wyszedł po za zakres.

if(0 >= a.GetLowerBound(0)) && ((i) <= a.GetUpperBound(0)) 

W przypadku tablic jednowymiarowych najczęściej sprawdzanie indeksu wykonywane jest jeden raz tuż przed wykonaniem pętli.

 if(0 >= a.GetLowerBound(0)) && ((elementsCount – 1) <= a.GetUpperBound(0))

W każdej iteracji CLR oblicza prawidłowy indeks dostępu.

Tablica tablic (jagged array)

int[][] array = new int[x][];
for (int i = 0; i < array.Length; i++)
{
  array[i] = new int[y];
}

Dostęp do tej tablicy jest najszybszy, ponieważ tablica ta zachowuje się jak jednowymiarowa. Alokacja takiej tablicy jest zdecydowanie wolniejsza od tablicy wielowymiarowej. Tworzone jest wiele obiektów, na których pracuje GC. Ilość tworzonych obiektów to x + 1. Jest to najlepsze rozwiązanie dla sytuacji gdy tablica tworzona jest tylko raz po czym wielokrotnie uzyskiwany jest dostęp do elementów tej tablicy.

Tablica unsafe

int[,] array = new int[x, y];
fixed (int* pointer = array) { }

Szybsza inicjalizacaja niż jagged array. Jest to rozwiązanie gdzie dostęp do obiektów jest szybszy od tablicy wielowymiarowej ale trochę wolniejszy od tablicy tablic. Rozwiązanie to jest po środku pomiędzy jagged array a tablicami wielowymiarowymi. Wadą jest to, że łatwo popełnić błąd i wyjść po za zakres tablic.

Przykładowy kod

Program mierzący czasy dla powyższych trzech rodzajów tablic możecie zobaczyć na GitHub: Multidimensional Arrays Performance.

Przykładowe wyniki skopiowane z ekranu programu:

Size X: 10000; Size: Y: 10000

Creating - Multidimensional array: 1767 count of ticks of processor.
Access - Multidimensional array: 691133 count of ticks of processor.

Creating - Jagged array: 1240819 count of ticks of processor.
Access - Jagged array: 88661 count of ticks of processor.

Creating - Unsafe array: 1755 count of ticks of processor.
Access - Unsafe array: 343454 count of ticks of processor.

Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Wyloguj /  Zmień )

Zdjęcie na Google+

Komentujesz korzystając z konta Google+. Wyloguj /  Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Wyloguj /  Zmień )

Zdjęcie na Facebooku

Komentujesz korzystając z konta Facebook. Wyloguj /  Zmień )

Connecting to %s