wake-up-neo.com

Unterschied zwischen Array und Liste in scala

In welchen Fällen sollte ich Array (Buffer) und List (Buffer) verwenden. Der einzige Unterschied, den ich kenne, ist, dass Arrays nicht variant und Listen kovariant sind. Aber was ist mit der Leistung und einigen anderen Merkmalen?

126
Jeriho

Unveränderliche Strukturen

Die Scala List ist eine unveränderliche rekursive Datenstruktur, die in Scala eine so grundlegende Struktur darstellt, dass Sie sie (wahrscheinlich) viel mehr als eine Array verwenden sollten. ] (das ist eigentlich veränderlich - das unveränderliche Analog von Array ist IndexedSeq) .

Wenn Sie aus einem Java Hintergrund kommen, ist die offensichtliche Parallele, wenn Sie LinkedList über ArrayList verwenden. Ersteres wird im Allgemeinen für Listen verwendet, die nur sind jemals durchlaufen (und deren Größe im Voraus nicht bekannt ist), wobei letztere für Listen verwendet werden sollte, die entweder eine bekannte Größe (oder eine maximale Größe) haben oder für Welcher schneller wahlfreier Zugriff ist wichtig?.

Veränderbare Strukturen

ListBuffer bietet eine zeitlich konstante Konvertierung in eine List, weshalb nur ListBuffer verwendet werden sollte, wenn eine solche spätere Konvertierung erforderlich ist.

Ein scala Array sollte auf der JVM durch ein Java Array und daher ein Array[Int] kann viel performanter sein (als int[]) als ein List[Int] (der den Inhalt enthält, es sei denn, Sie verwenden die neuesten Versionen von Scala mit dem neuen @specialized Feature).

Ich bin jedoch der Meinung, dass die Verwendung von Array in Scala) auf ein Minimum beschränkt werden sollte, da man das Gefühl hat, dass man wirklich wissen muss, was unter der Haube vor sich geht, um zu entscheiden Gibt an, ob Ihr Array wirklich vom erforderlichen primitiven Typ unterstützt wird oder ob es als Wrapper-Typ verpackt ist.

144
oxbow_lakes

Zusätzlich zu den bereits veröffentlichten Antworten finden Sie hier einige Besonderheiten.

Während ein Array[A] Buchstäblich ein Java Array ist, ist ein List[A] Eine unveränderliche Datenstruktur, die entweder Nil (die leere Liste) oder ist besteht aus einem Paar (A, List[A]).

Leistungsunterschiede

                          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)

Speicherunterschiede

                          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)

Wenn Sie also keinen schnellen Direktzugriff benötigen, Elemente zählen müssen oder aus irgendeinem Grund destruktive Aktualisierungen benötigen, ist ein List besser als ein Array.

126
Apocalisp

Ein Array ist veränderlich, dh Sie können die Werte der einzelnen Indizes ändern, während eine Liste (standardmäßig) unveränderlich ist. Dies bedeutet, dass bei jeder Änderung eine neue Liste erstellt wird. In den meisten Fällen ist es "funktionaler", mit unveränderlichen Datentypen zu arbeiten, und Sie sollten wahrscheinlich versuchen, eine Liste mit Konstrukten wie yield, foreach, match und so weiter zu verwenden her.

Bei Leistungsmerkmalen ist ein Array schneller mit wahlfreiem Zugriff auf Elemente, wohingegen eine Liste schneller ist, wenn neue Elemente vorangestellt (hinzugefügt) werden. Über sie zu iterieren ist vergleichbar.

17
leonm