Różnica między Array i List w scali

W jakich przypadkach powinienem używać Array (Buffer) i List (Buffer). Jedyną różnicą, którą znam, jest to, że tablice są niezmienne, a listy są kowariantne. Ale co z wydajnością i innymi cechami?

Niezmienne struktury

Scala Listjest niezmienna rekurencyjne struktury danych, która jest taka zasadnicza struktura w Scala, które powinny (prawdopodobnie) będzie go używać znacznie więcej niż Array(co jest rzeczywiście zmienne - w niezmienny analogowy z Arrayto IndexedSeq).

Jeśli korzystasz z języka Java, oczywistą paralelą jest to, kiedy użyć LinkedListover ArrayList. Pierwsza z nich jest generalnie używana dla list, które są kiedykolwiek przeszukiwane (i których rozmiar nie jest znany z góry), podczas gdy druga powinna być używana do list, które mają znany rozmiar (lub maksymalny rozmiar) lub dla których ważny jest szybki losowy dostęp .

Zmienne struktury

ListBufferzapewnia konwersję w czasie stałym do a, Listktóra jest jedynym powodem do użycia, ListBufferjeśli taka późniejsza konwersja jest wymagana.

Skala Arraypowinna być implementowana w JVM przez tablicę Java, a zatem Array[Int]może być znacznie bardziej wydajna (jako int[]) niż a List[Int](która zapakuje zawartość, chyba że używasz najnowszych wersji Scali, które mają nową @specializedfunkcję) .

Uważam jednak, że użycie Arrays w Scali powinno być ograniczone do minimum, ponieważ wydaje się, że naprawdę musisz wiedzieć, co się dzieje pod maską, aby zdecydować, czy twoja tablica naprawdę będzie obsługiwana przez wymagany typ prymitywny, czy może być zapakowane jako typ opakowania.

Oprócz już opublikowanych odpowiedzi, oto kilka szczegółów.

Chociaż an Array[A]jest dosłownie tablicą Java, a List[A]jest niezmienną strukturą danych, która jest Nil(pusta lista) lub składa się z pary (A, List[A]).

Różnice w wydajności

                          Array  List
Access the ith element    θ(1)   θ(i)
Delete the ith element    θ(n)   θ(i)
Insert an element at i    θ(n)   θ(i)
Reverse                   θ(n)   θ(n)
Concatenate (length m,n)  θ(n+m) θ(n)
Count the elements        θ(1)   θ(n)

Różnice w pamięci

                          Array  List
Get the first i elements  θ(i)   θ(i)
Drop the first i elements θ(n-i) θ(1)
Insert an element at i    θ(n)   θ(i)
Reverse                   θ(n)   θ(n)
Concatenate (length m,n)  θ(n+m) θ(n)

Więc jeśli nie potrzebujesz szybkiego losowego dostępu, musisz liczyć elementy lub z jakiegoś powodu potrzebujesz destrukcyjnych aktualizacji, a Listjest lepsze niż Array.

Tablica jest zmienna, co oznacza, że ​​możesz zmienić wartości każdego indeksu, podczas gdy lista (domyślnie) jest niezmienna, co oznacza, że ​​nowa lista jest tworzona za każdym razem, gdy wykonujesz modyfikację. W większości przypadków jest to bardziej „funkcjonalny” styl pracy z niezmiennych typów danych i powinieneś spróbować skorzystać lista z konstrukcjami takimi jak yield, foreach, matchi tak dalej.

Ze względu na charakterystykę wydajności tablica jest szybsza z losowym dostępem do elementów, podczas gdy lista jest szybsza, gdy poprzedza (dodaje) nowe elementy. Iterowanie po nich jest porównywalne.