Dlaczego dołączanie do listy w Scali ma złożoność czasową O (n)?

Właśnie przeczytałem, że czas wykonania operacji dołączania dla List(: +) rośnie liniowo wraz z rozmiarem pliku List.

Dołączanie do Listwydaje się dość powszechną operacją. Dlaczego idiomatycznym sposobem na to jest przygotowanie komponentów, a następnie odwrócenie listy? Nie może to być również błąd projektu, ponieważ implementacja może zostać zmieniona w dowolnym momencie.

Z mojego punktu widzenia zarówno dodawanie, jak i dodawanie powinno być O (1).

Czy jest to uzasadniony powód?

— DPM
źródło

Zależy od twojej definicji „uzasadnionego”. Scala jest mocno zaangażowana w niezmienne struktury danych, wszechobecne anonimowe listy, skład funkcjonalny itp. Domyślna implementacja listy (bez dodatkowego modyfikowalnego wskaźnika do końca listy) działa dobrze dla tego stylu. Jeśli potrzebujesz bardziej wydajnej listy, przynajmniej bardzo łatwo jest napisać własny kontener, który jest prawie nie do odróżnienia od standardowych.

— Kilian Foth,

Powiązane z wieloma witrynami - Dodanie elementu na końcu listy w Scali - jest trochę o jego charakterze. To wydaje się , że lista w Scala jest niezmienna, a więc trzeba go skopiować, która jest O (N).

Możesz użyć jednej z wielu dostępnych, modyfikowalnych struktur danych lub niezmiennych struktur danych z O (1) czasem dołączania (Vector), który zapewnia Scala. List[T]zakłada, że używasz go tak, jak w czysto funkcjonalnym języku - na ogół pracując od głowy z dekonstrukcją i przygotowując.

— KChaloux,

Przygotowywanie spowoduje umieszczenie następnego wskaźnika węzła nowej głowy na istniejącej niezmiennej liście - której nie można zmienić. To O (1).

Do przełomowej pracy i analizy na ogólny temat pomiarów złożoności struktury danych w czystym FP zapoznaj się z tezą Okasaki, która została później opublikowana jako książka. Jest to bardzo ceniona i bardzo dobra lektura dla każdego, kto uczy się FP, aby zrozumieć, jak myśleć o organizowaniu danych w FP. Jest również dobrze napisany i łatwy do odczytania i śledzenia, więc w sumie tekst wysokiej jakości.

— Jimmy Hoffa

Rozbuduję trochę mój komentarz. Struktura List[T]danych from scala.collection.immutablejest zoptymalizowana do działania w taki sposób, aby działała niezmienna lista w czysto funkcjonalnym języku programowania. Ma bardzo krótki czas przygotowania i zakłada się, że będziesz pracować nad głową prawie przez cały swój dostęp.

Niezmienne listy mogą mieć bardzo krótkie czasy prepend, ponieważ modelują one swoje połączone listy jako serię „komórek przeciw”. Komórka definiuje pojedynczą wartość i wskaźnik do następnej komórki (klasyczny styl pojedynczo połączonych list):

Cell [Value| -> Nil]

Kiedy przechodzisz do listy, tak naprawdę tworzysz tylko jedną nową komórkę, a reszta istniejącej listy jest wskazywana:

Cell [NewValue| -> [Cell[Value| -> Nil]]

Ponieważ lista jest niezmienna, możesz to zrobić bez faktycznego kopiowania . Nie ma niebezpieczeństwa zmiany starej listy i spowodowania, że wszystkie wartości na nowej liście staną się nieprawidłowe. Jednak tracisz możliwość posiadania zmiennego wskaźnika na końcu listy jako kompromis.

To bardzo dobrze nadaje się do rekurencyjnej pracy nad listami. Załóżmy, że zdefiniowałeś własną wersję filter:

def deleteIf[T](list : List[T])(f : T => Boolean): List[T] = list match {
  case Nil => Nil
  case (x::xs) => f(x) match {
    case true => deleteIf(xs)(f)
    case false => x :: deleteIf(xs)(f)
  }
}

Jest to funkcja rekurencyjna, która działa wyłącznie na początku listy i wykorzystuje dopasowanie wzorca za pomocą :: ekstraktora. To jest coś, co często widuje się w językach takich jak Haskell.

Jeśli naprawdę chcesz mieć szybkie dodatki, Scala oferuje wiele zmiennych i niezmiennych struktur danych do wyboru. Po stronie zmiennej możesz zajrzeć ListBuffer. Alternatywnie, Vectorod scala.collection.immutablema szybki czas dołączania.

— KChaloux
źródło

teraz rozumiem! Ma to całkowity sens.

— DPM,

Nie znam żadnej Scali, ale czy to nie elsejest nieskończona pętla? Myślę, że tak powinno być x::deleteIf(xs)(f).

— svick,

@svick Uh ... tak. Tak to jest. Napisałem go szybko i nie zweryfikowałem swojego kodu, ponieważ miałem spotkanie, na które można się udać: p (powinno być teraz naprawione!)

— KChaloux,

@Jubbat Ponieważ headi taildostęp z tego rodzaju listą jest bardzo szybki - szybszy niż przy użyciu dowolnej mapy lub tablicy opartej na haszowaniu - jest to doskonały typ dla funkcji rekurencyjnych. To jeden z powodów, dla których listy są podstawowym typem w większości języków funkcjonalnych (np. Haskell lub Scheme)

— itsbruce

Doskonała odpowiedź. Być może dodałbym TL; DR, która po prostu mówi „ponieważ należy dodawać, a nie dodawać” (może pomóc wyjaśnić podstawowe założenia większości programistów dotyczące Lists i dołączania / dodawania).

— Daniel B