Tablice vs Listy

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

wyniki dla tablica.Add(Math.Log(i));

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.