Tablica, Lista, for, foreach- kiedy używać?

W pogoni za optymalizacją

Często nie zwracamy uwagi na wydajność naszego kodu, ponieważ terminy gonią, a często taniej jest dołożyć więcej RAM-u czy wymienić procesor na lepszy, niż poświęcić czas programisty. Jednak warto poprzez proste kroki sprawić, by kod był zoptymalizowany. Dzisiaj sprawdzimy czy poprzez odpowiednie stosowanie List czy tablic oraz for i foreach możemy przyspieszyć nasz kod.

Benchmarki

Pusty przebieg

Test, który nie do końca ma sens w normalnym programownaiu, bo kto używa pustych pętli? Jednak przeprowadziłem go, aby zobaczyć co na „czysto” jest szybsze.

Dictionary<Type, List<long>> results = new Dictionary<Type, List<long>>
{
{Type.ArrayFor, new List<long>()},
{Type.ArrayForeach, new List<long>()},
{Type.ListFor, new List<long>()},
{Type.ListForeach, new List<long>()}
};

for (int j = 0; j < 1000; j++)
{
const int size = 10000000;
int[] arrayvals = new int[size];
for (int i = 0; i < size; i++)
{
arrayvals[i] = 1;
}
List<int> listvals = arrayvals.ToList();

Stopwatch stopwatch = Stopwatch.StartNew();
foreach (var val in arrayvals)
{
}
stopwatch.Stop();
results[Type.ArrayForeach].Add(stopwatch.ElapsedMilliseconds);

stopwatch.Restart();
foreach (var val in listvals)
{
}
stopwatch.Stop();
results[Type.ListForeach].Add(stopwatch.ElapsedMilliseconds);

stopwatch.Restart();
for (int i = 0; i < arrayvals.Length; i++)
{
}
stopwatch.Stop();
results[Type.ArrayFor].Add(stopwatch.ElapsedMilliseconds);

stopwatch.Restart();
for (int i = 0; i < listvals.Count; i++)
{
}
stopwatch.Stop();
results[Type.ListFor].Add(stopwatch.ElapsedMilliseconds);
}

Console.WriteLine("Array, foreach: {0}", results[Type.ArrayForeach].Average());
Console.WriteLine("List, foreach: {0}", results[Type.ListForeach].Average());
Console.WriteLine("Array, for: {0}", results[Type.ArrayFor].Average());
Console.WriteLine("List, for: {0}", results[Type.ListFor].Average());

Średnia z 1000 testów (dane w milisekundach):

Tablica List
for 3.43 3.44
foreach 6.75 32.43

Pętla for ma praktycznie identyczne wyniki dla tablicy jak i listy. Różnica pojawia się w pętli foreach. Dla list foreach działa 9 razy wolniej niż w przypadku for.

Dostęp do zmiennej

Bardziej „produkcyjny” przykład. W każdej z pętli jest dostęp do wartości pod konkretnym indeksem.

Dictionary<Type, List<long>> results = new Dictionary<Type, List<long>>
{
{Type.ArrayFor, new List<long>()},
{Type.ArrayForeach, new List<long>()},
{Type.ListFor, new List<long>()},
{Type.ListForeach, new List<long>()}
};

for (int j = 0; j < 1000; j++)
{
int sum = 0;
const int size = 10000000;
int[] arrayvals = new int[size];
for (int i = 0; i < size; i++)
{
arrayvals[i] = 1;
}
List<int> listvals = arrayvals.ToList();

Stopwatch stopwatch = Stopwatch.StartNew();
foreach (var val in arrayvals)
{
sum += val;
}
stopwatch.Stop();
results[Type.ArrayForeach].Add(stopwatch.ElapsedMilliseconds);

sum = 0;
stopwatch.Restart();
foreach (var val in listvals)
{
sum += val;
}
stopwatch.Stop();
results[Type.ListForeach].Add(stopwatch.ElapsedMilliseconds);

sum = 0;
stopwatch.Restart();
for (int i = 0; i < arrayvals.Length; i++)
{
sum += arrayvals[i];
}
stopwatch.Stop();
results[Type.ArrayFor].Add(stopwatch.ElapsedMilliseconds);

sum = 0;
stopwatch.Restart();
for (int i = 0; i < listvals.Count; i++)
{
sum += listvals[i];
}
stopwatch.Stop();
results[Type.ListFor].Add(stopwatch.ElapsedMilliseconds);
}

Console.WriteLine("Array, foreach: {0}", results[Type.ArrayForeach].Average());
Console.WriteLine("List, foreach: {0}", results[Type.ListForeach].Average());
Console.WriteLine("Array, for: {0}", results[Type.ArrayFor].Average());
Console.WriteLine("List, for: {0}", results[Type.ListFor].Average());

Średnia z 1000 testów (dane w milisekundach):

Tablica List
for 7.62 14.95
foreach 6.96 33.23

Wyniki mogą już zaskakiwać. Najszybsza we wcześniejszym teście para tablica i for nie jest już najszybsza. Dzieje się tak, ponieważ w pętli foreach mamy od razu dostęp do wartości pod danym indeksem. W pęli for musimy po niego sięgnąć. W przypadku list, wynik dla pętli foreach za bardzo się nie zmienił, jednak nadal działa on najwolniej.

Kiedy używać

Przeprowadzone powyżej testy dają nam pogląd co kiedy najlepiej stosować. Tablice są szybsze niż listy, jednak mają swoje ograniczenia (stała liczba elementów).

W przypadku gdy mamy małą kolekcję obiektów (do 1000 elementów), różnica pomiędzy wynikami jest znikoma i nie ma znaczenia co zastosujemy.

Reklamy

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