Witam,
tak jak w temacie, chciałbym się dowiedzieć kiedy lepiej jest użyć list a kiedy zwykłej tablicy.
Pozdrawiam
Witam,
tak jak w temacie, chciałbym się dowiedzieć kiedy lepiej jest użyć list a kiedy zwykłej tablicy.
Pozdrawiam
Ale do czego?
Tablicy możesz użyć jak z góry znasz liczbę elementów i nie będzie ona zmienna.
W reszcie przypadków raczej łatwiej użyć listy.
Do jednych zastosowań lepsza będzie tablica, a do innych lista. Generalnie tablica jest dobra kiedy znasz z góry rozmiar, a lista w przeciwnym wypadku.
Powinieneś wiedzieć, że lista to tak naprawdę tablica o pewnym (domyślnie niewielkim) rozmiarze. Jeżeli dodawanie elementów wyczerpie miejsce, wówczas jej rozmiar jest podwajany.
Sarrus napisał(a):
Do jednych zastosowań lepsza będzie tablica, a do innych lista. Generalnie tablica jest dobra kiedy znasz z góry rozmiar, a lista w przeciwnym wypadku.
Powinieneś wiedzieć, że lista to tak naprawdę tablica o pewnym (domyślnie niewielkim) rozmiarze. Jeżeli dodawanie elementów wyczerpie miejsce, wówczas jej rozmiar jest podwajany.
Dlatego, gdy ktoś tworzy listę i +- wie ile będzie elementów, to lepiej zrobić new List<T>(size)
niż new List<T>()
Bo wtedy nie będzie tracił na tym rozszerzeniu listy, co na początku dzieję się bardzo często, a dokładnie przy 0, a dalej 2^n +1 (n >= 2) elementów.
Całkowity koszt rozszerzania i tak jest liniowy, więc zainicjalizowanie listy z określoną wielkością nie zmieni złożoności dodawania elementów do niej (za to trochę zmniejszy stałą w oszacowaniu złożoności).
Elementy tablicy musiałyby być obliczane w bardzo tani sposób, by całkowity czas działania algorytmu był odczuwalnie niższy na tablicach niż na listach.
Wibowit napisał(a):
Całkowity koszt rozszerzania i tak jest liniowy
Śmiem twierdzić że jednak jest liniowo logarytmiczny (e: jest liniowa), bo do rozszerzania musi być utworzonych tych lg n tabel, i muszą być z nich kopiowane elementy przy każdym rozszerzaniu. Już nie wspominając o traceniu pamięci na te tymczasowe tabele i zwiększaniu presji na GC.
Co zresztą ładnie widać na tym benchamrku:
[Benchmark(Baseline = true)]
public int[] Array()
{
int[] tablica = new int[Size];
for (int i = 0; i < Size; i++)
{
tablica[i] = i;
}
return tablica;
}
[Benchmark]
public List<int> List1()
{
List<int> tablica = new List<int>(Size);
for (int i = 0; i < Size; i++)
{
tablica.Add(i);
}
return tablica;
}
[Benchmark]
public List<int> List2()
{
List<int> tablica = new List<int>();
for (int i = 0; i < Size; i++)
{
tablica.Add(i);
}
return tablica;
}
Method | Size | Mean | Error | StdDev | Scaled | Allocated |
---|---|---|---|---|---|---|
Array | 1000000 | 1.610 ms | 1.678 ms | 0.0948 ms | 1.00 | 3.81 MB |
List1 | 1000000 | 5.059 ms | 3.883 ms | 0.2194 ms | 3.15 | 3.82 MB |
List2 | 1000000 | 7.328 ms | 3.107 ms | 0.1755 ms | 4.56 | 8 MB |
wyniki dla tablica.Add(Math.Log(i));
Method | Size | Mean | Error | StdDev | Scaled | Allocated |
---|---|---|---|---|---|---|
Array | 1000000 | 13.96 ms | 4.058 ms | 0.2293 ms | 1.00 | 7.63 MB |
List1 | 1000000 | 17.13 ms | 22.698 ms | 1.2825 ms | 1.23 | 7.63 MB |
List2 | 1000000 | 19.13 ms | 11.921 ms | 0.6736 ms | 1.37 | 16 MB |
Smiem twierdzić że jednak jest liniowo logarytmiczny, bo do rozszerzania musi być utworzonych tych lg n tabel, i muszą być z nich kopiowane elementy przy każdym rozszerzaniu. Już nie wspominając o traceniu pamięci na te tymczasowe tabele i zwiększaniu presji na GC.
Jeżeli tablice rosną o stały współczynnik to sumaryczny rozmiar tabel jest liniowy, podobnie ilość elementów kopiowanych (bo elementy nie są nadpisywane).
Załóżmy, że za każdy razem tablica pod listą rozszerza się dwukrotnie. Po wrzuceniu N elementów tablica ma rozmiar X, gdzie X jest potęgą dwójki i X < N * 2. Przed ostatnim rozszerzeniem tablicy ta miała rozmiar X/2, wcześniej było to X/4, jeszcze wcześniej X/8, itd Sumaryczny rozmiar tablic możemy obliczyć na podstawie sumy ciągu geometrycznego https://pl.wikipedia.org/wiki/Ci%C4%85g_geometryczny . X + X/2 + X/4 + ... + 1 = 2 * X - 1 czyli około 2 * X. Stąd całkowity rozmiar zaalokowanej pamięci jest < N * 4 (a 4 to oczywiście stała, a nie żaden logarytm).
Suma ciągu geometrycznego to zagadnienie co najwyżej na poziomie liceum, więc przypomnienie sobie tego powinno być proste :]
W takich tematach tylko się potwierdza, że quicksort na rozmowach rekrutacyjnych nie jest głupim pomysłem…
Ja bym poszedł krok dalej i na początek dał jakąś prostą czytankę + test z treści. Coś w rodzaju: "Ala ma kota, a kot ma Alę" i pytanie: "Co ma Ala?" z odpowiedziami:
a) Alę;
b) kota;
c) psa;
d) dzięcioł.
No bo w sumie jakby ludzie umieli czytać, to by chyba nie mylili złożoności obliczeniowej z czasem wykonania.
No bo w sumie jakby ludzie umieli czytać, to by chyba nie mylili złożoności obliczeniowej z czasem wykonania.
Spróbuj się odnieść do czegoś konkretnego zamiast rzucać jakieś dziwne hasła. Masz sporo postów do zacytowania - wybierz sobie co chcesz.
uzywaj listy, chyba ze sie nie da.