Czemu lista nie jest listą? - rozważania filozoficzne :)

Tak się zastanawiam, dlaczego w C# lista (List<T>) nie jest typową listą, tylko wrapperem na tablicę. Przecież można by zrobić prawdziwą listę za pomocą np. takiej klasy reprezentującej jej elementy:

class ListItem<T>
{
  public ListItem<T> Prev { get; set; }
  public ListItem<T> Next { get; set; }
  public T Value { get; set; }
}

W C++ vector jest chyba szybszy niż list, ale tylko do pewnego rozmiaru, z tego co wiem. Więc nie do końca tu chyba chodzi o kwestie optymalizacyjne, zwłaszcza, że w .NET nie ma typowej sterty, tylko zarządzana i przypomina bardziej stos (nowe elementy tworzone są na końcu sterty, a nie w wolnych miejscach).

Dlaczego więc w C# nie ma typowej listy?

w .NET nie ma typowej sterty, tylko zarządzana i przypomina bardziej stos (nowe elementy tworzone są na końcu sterty, a nie w wolnych miejscach).

Tak działa pierwsza generacja obiektów. Po odpaleniu GC obiekty przemieszczają się w dowolne miejsca.

Dlaczego więc w C# nie ma typowej listy?

Przejrzałem MSDNa na szybko i wychodzi na to, że LinkedList w C# istnieje, ale nie implementuje interfejsu IList. Trochę dziwna ta hierarchia dziedziczenia.

bo random access na List jest duzo szybszy niz przy LinkedList, jest to tez powodem na brak implementacji IList na liscie polaczonej (IList gwarantuje miedzy innymi dostep po indeksie)

Ale to nie ma znaczenia. To jest normalna różnica między listą, a tablicą.

@Juhas, ale w czym problem? W .NET są obie listy: węzłowa i tablicowa, i w zależności od potrzeb możesz użyć tej, która lepiej pasuje.

Dlaczego więc w C# nie ma typowej listy?

Ależ ma, tak jak @Wibowit wspomniał LinkedList (o ile jest to dla Ciebie typowa lista).
List<> po prostu bardziej się przydaje, wszak w typowej pracy rzadko piszę się Sneaka ;) Tutaj masz trochę o wydajności: http://www.pzielinski.com/?p=1760

LinkedList w C# istnieje, ale nie implementuje interfejsu IList. Trochę dziwna ta hierarchia dziedziczenia.

Żeby było ciekawej, to Array też dziedziczy z IList ;) Przez IList powinniśmy rozumieć (za MSDN):

collection of objects that can be individually accessed by index

Ale to nie ma znaczenia. To jest normalna różnica między listą, a tablicą.

lista polaczona jest dosc rzadko uzywana kodujac w c#, w praktyce najczesciej potrzebna jest tablica ktora stosunkowo rzadko bedzie sie powiekszac - i wlasnie to zapewnia List - nie musisz recznie realokowac tej tablicy bo masz to zgrabnie ukryte :)

Wiem jak działa list. Chociaż faktycznie o LinkedList nie wiedziałem. W sumie nigdy nie potrzebowałem :D
Ale moim zdaniem takie nazewnictwo wprowadza jednak w błąd. No bo człowiek spodziewa się listy, a dostaje tablicę (więc mogliby to nazwać np. SmartArray, a nie List).

Poza tym zwykłą listę też można indeksować. Nie jest to w prawdzie optymalne, ale jak najbardziej do osiągnięcia. Więc też mnie teraz dziwi, że LinkedList nie implementuje IList.

Przeczytałem podlinkowany przez @mstl artykuł i widzę tu jakąś logikę. Myślałem, że lista działa tak, że zawsze zwiększa swoją rezerwę o jednakową ilość elementów. A wychodzi z tego, że im więcej do niej dodajemy, tym większa rezerwa. Z drugiej strony nie oszczędza to pamięci, ale w sumie od zawsze jest wybór: szybkość, albo pamięć.

Ale to w jaki sposób dana struktura została zaimplementowana nie musi wpływać na jej nazwę. C# posiada też Stack<> i jego implementacja też wewnętrznie używa tablicy. Dlaczego więc nie czepiasz się nazwy tej struktury danych? ;)
Ponadto nie wiem dlaczego uważasz, że lista to w domyślnie lista łączona. Wiki podaje co innego:
https://en.wikipedia.org/wiki/List_(abstract_data_type)

Bo arraylist sa lepsze w jakiś 99%:
Get, set: O(1)
append: O(1);
Push: O(n);
insert: O(n).
Linked lists:
Get, set: O(n);
Append, push: O(1);
Insert: O(n).
Nie wspominajac, ze komputery, duuuzo bardziej lubia tablice, niz struktury wskaznikowe.

@lion137: linked list insert O(n)? Przecież to kwestia przepisania wskaźników. Z drugiej strony trzeba najpierw znaleźć odpowiedni element. Ale jeśli mamy już odpowiedni element, to wtedy będzie to O(1), zgadza się?
Też jeśli chodzi o listę, to append nie zawsze będzie O(1). W momencie, gdy musimy skopiować tablicę, bo zabrakło miejsca, no to złożoność jest większa.

mstl napisał(a):

Ale to w jaki sposób dana struktura została zaimplementowana nie musi wpływać na jej nazwę. C# posiada też Stack<> i jego implementacja też wewnętrznie używa tablicy. Dlaczego więc nie czepiasz się nazwy tej struktury danych? ;)

Bo czepiłem się innej ;)

Ponadto nie wiem dlaczego uważasz, że lista to w domyślnie lista łączona. Wiki podaje co innego:
https://en.wikipedia.org/wiki/List_(abstract_data_type)

Na studiach mnie uczyli, że lista to lista (domyślnie lista prosta jednokierunkowa), a nie struktura tablicowa.

Juhas napisał(a):

@lion137: linked list insert O(n)? Przecież to kwestia przepisania wskaźników. Z drugiej strony trzeba najpierw znaleźć odpowiedni element. Ale jeśli mamy już odpowiedni element, to wtedy będzie to O(1), zgadza się?
Też jeśli chodzi o listę, to append nie zawsze będzie O(1). W momencie, gdy musimy skopiować tablicę, bo zabrakło miejsca, no to złożoność jest większa.

Jak po O(n) krokow wykonasz O(1) to ile to razem?:)

Append jest O(1), mozna powiedziec, praktycznie O(1). Tak dziala arraylist, powiekszamy pamiec dwa razy, co kazda protege dwojki, 1, 2, 4, 8, ...., 4096,... , I przepisujemy. Dlatego mozna powiedziec, ze praktycznie sie tego nie zauwaza. Odsylam do CLRS.

lion137 napisał(a):

Juhas napisał(a):

@lion137: linked list insert O(n)? Przecież to kwestia przepisania wskaźników. Z drugiej strony trzeba najpierw znaleźć odpowiedni element. Ale jeśli mamy już odpowiedni element, to wtedy będzie to O(1), zgadza się?
Też jeśli chodzi o listę, to append nie zawsze będzie O(1). W momencie, gdy musimy skopiować tablicę, bo zabrakło miejsca, no to złożoność jest większa.

Jak po O(n) krokow wykonasz O(1) to ile to razem?:)

No napisałem, że jeśli mamy już znaleziony konkretny element w sensie, że np. zapisany w jakiejś zmiennej.

Append jest O(1), mozna powiedziec, praktycznie O(1). Tak dziala arraylist, powiekszamy pamiec dwa razy, co kazda protege dwojki, 1, 2, 4, 8, ...., 4096,... , I przepisujemy. Dlatego mozna powiedziec, ze praktycznie sie tego nie zauwaza. Odsylam do CLRS.

Eee, lista powiększa się proporcjonalnie, ale początkową wartością jest zdaje się 16. Przynajmniej w tej wersji.

@Juhas: w C# array list powieksza sie proporcjonalbie? To ciekawa implementacja, chcialbym to zobaczyc. W pythonie I javie jest klasyczna augmented array.

Jakie augmented array? W Javie tablica w ArrayLiście rośnie co połowę: http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/8u40-b25/java/util/ArrayList.java#ArrayList.grow%28int%29

Wewnętrznie List<T> również powiększa się dwukrotnie:

https://referencesource.microsoft.com/#mscorlib/system/collections/generic/list.cs,eb66b6616c6fd4ef

Swoją drogą w .NET istnieje też klasa ArrayList - niegeneryczna poprzedniczka List<T>. Obecnie praktycznie nieużywana.

Wibowit napisał(a):

Jakie augmented array? W Javie tablica w ArrayLiście rośnie co połowę: http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/8u40-b25/java/util/ArrayList.java#ArrayList.grow%28int%29

Hm..., rzeczywiscie wyglada, ze co polowe, ale mowia, ze amortized time maja O(1), ciekawe, popacze pozniej.

Wystarczy żeby powiększała się o stały współczynnik by mieć zamortyzowany czas stały. Czas byłby asymptotycznie większy niż stały gdyby tablica powiększała się o stałą wielkość, niezależną od obecnego rozmiaru tablicy.

Lista z węzłami (LinkedList) jest używana:

• jeśli często wstawiamy lub usuwamy na początku lub w środku listy (mając wskaźnik na odpowiedni element), i nie możemy tego zastąpić dopisywaniem na końcu (szczerze, nie pamiętam, kiedy miałem taki przypadek)
• w programowaniu funkcyjnym do implementacji pewnych ciekawych struktur niemutowalnych jak np. niemutowalne kolejki
• i jeszcze w paru niszowych zastosowaniach jak alokatory pamięci, tablice z haszowaniem zachowujące kolejność itp.

Poza tym ma niemal same wady.

Poza wadami w kwestii złożoności, które już tu były poruszane, jest też zwyczajnie bardzo nieprzyjazna nowoczesnym procesorom. Procesory uwielbiają płaskie struktury danych i nie znoszą struktur powiązanych wskaźnikami. Każde przejście po takim wskaźniku do następnego elementu to potencjalny cache-miss, a to potrafi kosztować 1000 cykli i więcej. 1000 cykli na element, to paskudny narzut, gdy tymczasem taki wektor / tablicę można w niektórych przypadkach przetwarzać np. po 8 (!) elementów w jednym cyklu.

Z ww powodu tablice/wektory opłacają się nawet często w sytuacjach, gdzie przegrywają złożonością, ale mocno nadrabiają różnicą w stałej. I tak okazyjne przepisanie całego wektora składającego się z małej liczby elementów aby wrzucić jeden element na początek czy w środek może być w ostateczności szybsze niż dopisanie tego elementu do listy, bo cały czas odzyska się na np. przeglądaniu wektora vs przeglądanie listy.

lion137 napisał(a):

Linked lists:
Get, set: O(n);
Insert: O(n).

Co do tych dwóch to mam wątpliwości gdyż:

Get/set można zoptymalizować do 1/2n, lecisz od prawej lub lewej strony listy, zależnie czy szukany element k, jest większy lub mniejszy od 1/2 wszystkich elementów n.

A Insert tak samo, w najbardziej pesymistycznym przypadku, jest 1/2n, a tak to, optymistycznym to 1, jeśli k jest pierwszym elementem.

W złożoności obliczeniowej stałe są pomijane.