Dlaczego dołączanie do listy jest złe?

Question

Niedawno zacząłem uczyć się scala i natknąłem się na funkcję :: (minusy), która poprzedza listę.
w książce „Programowanie w Scala” stwierdza, że ​​nie ma funkcji append ponieważ dołączenie do listy ma Ø (N), natomiast poprzedzenie ma wydajność od O (1)

Coś po prostu wydaje mi się źle o to oświadczenie.

Czy wydajność nie zależy od wdrożenia? Czy nie można po prostu zaimplementować listy z łączami do przodu i do tyłu i przechowywać pierwszy i ostatni element w kontenerze?

Drugie pytanie, przypuszczam, jest takie, co powinienem zrobić, gdy mam listę, powiedzmy 1,2,3 i chcę dodać 4 na końcu tego?

Answer 1

Kluczem jest to, że x :: somelist nie zmutowuje somelist, ale tworzy nową listę, która zawiera x, a następnie wszystkie elementy z somelist. Można to zrobić w czasie O (1), ponieważ wystarczy ustawić somelist jako następcę x na nowo utworzonej, pojedynczo połączonej liście.

Jeśli zamiast tego użyto podwójnie połączonych list, x również musiałby zostać ustawiony jako poprzednik głowy somelist, co zmodyfikowałoby somelist. Jeśli chcemy mieć możliwość wykonania :: w O (1) bez modyfikowania oryginalnej listy, możemy używać tylko pojedynczo połączonych list.

Odnośnie drugiego pytania: można użyć :::, aby połączyć listę pojedynczych elementów na końcu listy. Jest to operacja O (n).

List(1,2,3) ::: List(4) 

Answer 2

poprzedzenie jest szybsza, ponieważ wymaga tylko dwie operacje:

1. Tworzenie nowej listy węzeł
2. że nowy punkt węzeł do istniejącej listy

dołączenie wymaga więcej operacji, bo trzeba przejść do końca listy, ponieważ masz tylko wskaźnik do głowy.

Nigdy wcześniej zaprogramowane w Scala, ale można spróbować List Buffer

Answer 3

języki najbardziej funkcjonalnych widocznym miejscu zorientować się pojedynczo-linked-list struktury danych, jak to poręczne niezmienna typu kolekcji. Kiedy mówisz "list" w języku funkcjonalnym, zazwyczaj masz na myśli to, co masz na myśli (lista pojedynczo połączona, zwykle niezmienna). W przypadku takiego typu, dodatek jest O (n) natomiast minus to O (1).

Answer 4

Inne odpowiedzi dały dobre wyjaśnienia tego zjawiska. Jeśli dodajesz wiele pozycji do listy w podprocedurze, lub jeśli tworzysz listę przez dołączanie elementów, idiomem funkcjonalnym jest tworzenie listy w odwrotnej kolejności, za wyjątkiem pozycji na liście z przodu z listy , a następnie odwróć go na końcu. To daje wydajność O (n) zamiast O (n²).

Answer 5

Ponieważ pytanie zostało właśnie zaktualizowane, warto zauważyć, że sytuacja się tutaj zmieniła.

W dzisiejszej Scali można po prostu użyć xs :+ x, aby dołączyć element na końcu dowolnej kolekcji sekwencyjnej. (Jest też x +: xs do poprzedź. Mnemonik dla wielu 2.8+ operacji zbierania Scala jest to, że kol na przechodzi obok col lekcja.)

To będzie O (n) z domyślnie połączona implementacja List lub Seq, ale jeśli używasz Vector lub IndexedSeq, będzie to faktycznie stały czas. Scala's Vector jest prawdopodobnie najbardziej użyteczną kolekcją w stylu Scala - w przeciwieństwie do Javy Vector, która w większości przypadków jest bezużyteczna.

Jeśli pracujesz w wersji Scala 2.8 lub wyższej, collections introduction jest koniecznością.