Wann sollte ich Vector in Scala wählen?

200

Es scheint, dass Vectores zu spät zur Scala-Sammlungsparty war und alle einflussreichen Blog-Beiträge bereits abgereist waren.

In Java ArrayListist die Standardsammlung - ich kann sie verwenden, LinkedListaber nur, wenn ich einen Algorithmus durchdacht habe und mich genug um die Optimierung kümmere. Sollte ich in Scala Vectormeine Standardeinstellung verwenden Seqoder versuchen, herauszufinden, wann dies Listtatsächlich angemessener ist?

Duncan McGregor
quelle
1
Ich denke, was ich hier meine ist, dass ich in Java List<String> l = new ArrayList<String>()Scala-Blogs schreiben würde. Würden Sie glauben, dass jeder List verwendet, um dauerhafte Sammlungsgüte zu erhalten - aber ist Vector allgemein genug, dass wir es anstelle von List verwenden sollten?
Duncan McGregor
9
@ Debilski: Ich frage mich, was du damit meinst. Ich bekomme eine, Listwenn ich Seq()bei REPL tippe.
fehlender Faktor
1
Hmm, das steht in den Dokumenten. Vielleicht gilt das nur für IndexedSeq.
Debilski
1
Der Kommentar zum Standardbetontyp Seqist über drei Jahre alt. Ab Scala 2.11.4 (und früher), der Standard - Betontyp Seqist List.
Mark Canlas
3
Für den Direktzugriff ist der Vektor besser. Für den Kopf-, Schwanzzugang ist die Liste besser. Für Massenoperationen wie Map, Filter und Vektor wird bevorzugt, da der Vektor mit 32 Elementen als Block organisiert ist, während die Liste die Elemente mit Zeigern aufeinander organisiert. Es gibt keine Garantie dafür, dass diese Elemente nahe beieinander liegen.
Johnsam

Antworten:

280

In der Regel standardmäßig verwenden Vector. Es ist schneller als Listfür fast alles und speichereffizienter für Sequenzen, die größer als trivial sind. In dieser Dokumentation wird die relative Leistung von Vector im Vergleich zu den anderen Sammlungen beschrieben. Es gibt einige Nachteile Vector. Speziell:

  • Updates an der Spitze sind langsamer als List(wenn auch nicht so viel, wie Sie vielleicht denken)

Ein weiterer Nachteil vor Scala 2.10 war, dass die Unterstützung für die Mustererkennung besser Listwar, dies wurde jedoch in 2.10 mit Generalized +:und :+Extractors behoben .

Es gibt auch eine abstraktere, algebraischere Herangehensweise an diese Frage: Welche Art von Sequenz haben Sie konzeptionell ? Und was machst du konzeptionell damit? Wenn ich eine Funktion sehe, die eine zurückgibt Option[A], weiß ich, dass diese Funktion einige Lücken in ihrer Domäne hat (und daher teilweise ist). Wir können dieselbe Logik auf Sammlungen anwenden.

Wenn ich eine Sequenz von Typ habe List[A], behaupte ich effektiv zwei Dinge. Erstens sind mein Algorithmus (und meine Daten) vollständig stapelstrukturiert. Zweitens behaupte ich, dass die einzigen Dinge, die ich mit dieser Sammlung machen werde, voll sind, O (n) Durchquerungen. Diese beiden gehen wirklich Hand in Hand. Umgekehrt, wenn ich etwas vom Typ habe Vector[A], behaupte ich nur , dass meine Daten eine genau definierte Reihenfolge und eine endliche Länge haben. Somit sind die Behauptungen mit schwächer Vector, und dies führt zu seiner größeren Flexibilität.

Daniel Spiewak
quelle
2
2.10 ist schon eine Weile nicht mehr verfügbar. Ist der Listenmusterabgleich immer noch besser als bei Vector?
Tim Gautier
3
Der Listenmusterabgleich ist nicht mehr besser. In der Tat ist es ganz im Gegenteil. Zum Beispiel, um Kopf und Schwanz zu bekommen, kann man tun case head +: tailoder case tail :+ head. Um gegen leer zu spielen, können Sie tun case Seq()und so weiter. Alles, was Sie brauchen, ist in der API enthalten, die vielseitiger ist als List's
Kai Sellgren
Listwird mit einer einfach verknüpften Liste implementiert. Vectorist so etwas wie Java implementiert ArrayList.
Josiah Yoder
6
@JosiahYoder Es ist nichts wie ArrayList implementiert. ArrayList umschließt ein Array, dessen Größe dynamisch geändert wird. Vektor ist ein Versuch , bei dem die Schlüssel die Indexe der Werte sind.
John Colanduoni
1
Ich entschuldige mich. Ich ging auf eine Webquelle, die über die Details vage war. Soll ich meine frühere Aussage korrigieren? Oder ist das eine schlechte Form?
Josiah Yoder
93

Nun, ein Listkann unglaublich schnell sein , wenn der Algorithmus mit nur umgesetzt werden kann ::, headund tail. Ich hatte vor kurzem eine Objektstunde davon, als ich Javas schlug, indem ich splitein Liststatt eines generierte Array, und das mit nichts anderem schlagen konnte.

Hat Listjedoch ein grundlegendes Problem: Es funktioniert nicht mit parallelen Algorithmen. Ich kann a nicht Listeffizient in mehrere Segmente aufteilen oder wieder verketten.

Es gibt andere Arten von Sammlungen, die viel besser mit Parallelität umgehen können - und Vectoreine davon. Vectorhat auch eine großartige Lokalität - was Listnicht der Fall ist - was für einige Algorithmen ein echtes Plus sein kann.

Alles in allem Vectorist dies die beste Wahl, es sei denn, Sie haben bestimmte Überlegungen, die eine der anderen Sammlungen vorzuziehen machen. Sie können beispielsweise auswählen, Streamob Sie eine verzögerte Auswertung und Zwischenspeicherung wünschen ( Iteratorist schneller, aber nicht zwischengespeichert) oderList ob Der Algorithmus wird natürlich mit den von mir erwähnten Operationen implementiert.

Übrigens ist es vorzuziehen, eine bestimmte API (z. B. 's ) zu verwenden Seqoder es IndexedSeqsei denn, Sie möchten eine bestimmte API (z. B. List' s ::) oder sogar GenSeqoder GenIndexedSeqwenn Ihr Algorithmus parallel ausgeführt werden kann.

Daniel C. Sobral
quelle
3
Danke für die Antwort. Was meinst du mit "hat große Lokalität"?
Ngoc Dao
10
@ngocdaothanh Dies bedeutet, dass Daten im Speicher eng zusammen gruppiert sind, wodurch die Wahrscheinlichkeit erhöht wird, dass sich Daten bei Bedarf im Cache befinden.
Daniel C. Sobral
1
@ user247077 Ja, Listen können Vektoren in der Leistung unter Berücksichtigung der von mir erwähnten Angaben übertreffen. Und nicht alle Aktionen von Vektoren werden O (1) amortisiert. Bei unveränderlichen Datenstrukturen (was der Fall ist) werden alternative Einfügungen / Löschungen an beiden Enden überhaupt nicht amortisiert. In diesem Fall ist der Cache unbrauchbar, da Sie den Vektor immer kopieren.
Daniel C. Sobral
1
@ user247077 Vielleicht wissen Sie nicht, dass Vectores sich bei Scala um eine unveränderliche Datenstruktur handelt?
Daniel C. Sobral
1
@ user247077 Es ist viel komplizierter als das, einschließlich einiger intern veränderbarer Dinge, um das Anhängen billiger zu machen, aber wenn Sie es als Stapel verwenden, was ein unveränderliches listenoptimales Szenario ist, haben Sie am Ende immer noch die gleichen Speichereigenschaften einer verknüpften Liste, aber mit einem viel größeren Speicherzuordnungsprofil.
Daniel C. Sobral
29

Einige der Aussagen hier sind verwirrend oder sogar falsch, insbesondere die Idee, dass unveränderlich. Vector in Scala ist so etwas wie eine ArrayList. List und Vector sind unveränderliche, persistente (dh "billig, um eine modifizierte Kopie zu erhalten") Datenstrukturen. Es gibt keine vernünftige Standardauswahl, wie sie für veränderbare Datenstrukturen gelten könnte, sondern es hängt vielmehr davon ab, was Ihr Algorithmus tut. List ist eine einfach verknüpfte Liste, während Vector eine Basis-32-Ganzzahl-Trie ist, dh eine Art Suchbaum mit Knoten des Grades 32. Mit dieser Struktur kann Vector die häufigsten Operationen relativ schnell bereitstellen, dh in O (log_32 ( n)). Das funktioniert für das Voranstellen, Anhängen, Aktualisieren, Direktzugriff und Zerlegen in Kopf / Schwanz. Die Iteration in sequentieller Reihenfolge ist linear. Die Liste hingegen bietet nur eine lineare Iteration und eine konstante Zeitvoraussetzung sowie eine Zerlegung in Kopf / Schwanz.

Dies mag so aussehen, als wäre Vektor in fast allen Fällen ein guter Ersatz für List, aber Voranstellen, Zerlegen und Iterieren sind häufig die entscheidenden Operationen für Sequenzen in einem Funktionsprogramm, und die Konstanten dieser Operationen sind für den fälligen Vektor (viel) höher zu seiner komplizierteren Struktur. Ich habe einige Messungen durchgeführt, sodass die Iteration für Listen etwa doppelt so schnell ist, das Voranstellen von Listen etwa 100-mal schneller ist, die Zerlegung in Kopf / Schwanz in Listen etwa 10-mal schneller ist und die Generierung aus einem Traversable für Vektoren etwa 2-mal schneller ist. (Dies liegt wahrscheinlich daran, dass Vector Arrays mit 32 Elementen gleichzeitig zuweisen kann, wenn Sie es mit einem Builder erstellen, anstatt Elemente einzeln voranzustellen oder anzuhängen.)

Welche Datenstruktur sollten wir also verwenden? Grundsätzlich gibt es vier häufige Fälle:

  • Wir müssen Sequenzen nur durch Operationen wie Map, Filter, Fold usw. transformieren: Grundsätzlich spielt es keine Rolle, wir sollten unseren Algorithmus generisch programmieren und könnten sogar davon profitieren, parallele Sequenzen zu akzeptieren. Für sequentielle Operationen ist List wahrscheinlich etwas schneller. Aber Sie sollten es vergleichen, wenn Sie optimieren müssen.
  • Wir brauchen viel Direktzugriff und verschiedene Updates, also sollten wir Vektor verwenden, Liste wird unerschwinglich langsam sein.
  • Wir bearbeiten Listen auf klassische funktionale Weise und erstellen sie durch Voranstellen und Iterieren durch rekursive Zerlegung: Verwenden Sie die Liste, der Vektor ist um einen Faktor von 10-100 oder mehr langsamer.
  • Wir haben einen leistungskritischen Algorithmus, der im Grunde genommen unerlässlich ist und viel zufälligen Zugriff auf eine Liste bietet, so etwas wie eine schnelle Sortierung: Verwenden Sie eine zwingende Datenstruktur, z. B. ArrayBuffer, lokal und kopieren Sie Ihre Daten von und nach dieser.
dth
quelle
24

Wenn Sie für unveränderliche Sammlungen eine Sequenz wünschen, ist Ihre Hauptentscheidung, ob Sie eine IndexedSeqoder eine verwenden LinearSeq, die unterschiedliche Leistungsgarantien bieten . Ein IndexedSeq bietet einen schnellen Direktzugriff auf Elemente und eine Operation mit schneller Länge. Ein LinearSeq bietet schnellen Zugriff nur auf das erste Element über head, hat aber auch einen schnellen tailBetrieb. (Entnommen aus der Seq-Dokumentation.)

Für ein IndexedSeq würden Sie normalerweise eine wählen Vector. Ranges und WrappedStrings sind auch IndexedSeqs.

Für a LinearSeqwürden Sie normalerweise ein Listoder sein faules Äquivalent wählenStream . Andere Beispiele sind Queues und Stacks.

Also in Java-Begriffen, ArrayListähnlich wie bei Scala Vectorund LinkedListähnlich wie bei Scala List. In Scala würde ich List jedoch häufiger verwenden als Vector, da Scala Funktionen, die das Durchlaufen der Sequenz umfassen, wie Mapping, Folding, Iteration usw., viel besser unterstützt. Sie werden diese Funktionen tendenziell verwenden, um die Liste als zu bearbeiten ganz, anstatt zufällig auf einzelne Elemente zuzugreifen.

Luigi Plinge
quelle
Aber wenn die Iteration von Vector schneller ist als die von List und ich auch Fold usw. abbilden kann, dann scheint List, abgesehen von einigen speziellen Fällen (im Wesentlichen all jene FP-Algorithmen, die auf List spezialisiert sind), im Wesentlichen Legacy zu sein.
Duncan McGregor
@Duncan wo hast du gehört, dass die Iteration von Vector schneller ist? Zunächst müssen Sie den aktuellen Index verfolgen und aktualisieren, was bei einer verknüpften Liste nicht erforderlich ist. Ich würde die Listenfunktionen nicht als "Spezialfälle" bezeichnen - sie sind das A und O der funktionalen Programmierung. Wenn Sie sie nicht verwenden, versuchen Sie, Java ohne For- oder While-Schleifen zu programmieren.
Luigi Plinge
2
Ich bin mir ziemlich sicher , dass Vector‚s Iteration ist schneller, aber jemand Bedürfnisse Benchmark es sicher zu sein.
Daniel Spiewak
Ich denke, dass (?) Elemente im VectorRAM physisch in Gruppen von 32 zusammen existieren, die besser in den CPU-Cache passen ... also gibt es weniger Cache-
Fehler
2

In Situationen, die viel zufälligen Zugriff und zufällige Mutation beinhalten, scheint a Vector(oder - wie die Dokumente sagen - a Seq) ein guter Kompromiss zu sein. Dies legen auch die Leistungsmerkmale nahe .

Außerdem Vectorscheint die Klasse in verteilten Umgebungen ohne große Datenverdoppelung gut zu spielen, da für das gesamte Objekt kein Copy-on-Write erforderlich ist. (Siehe: http://akka.io/docs/akka/1.1.3/scala/stm.html#persistent-datastructures )

Debilski
quelle
1
So viel zu lernen ... Was bedeutet Vector als Standard-Seq? Wenn ich Seq (1, 2, 3) schreibe, erhalte ich List [Int] und nicht Vector [Int].
Duncan McGregor
2
Wenn Sie wahlfreien Zugriff haben, verwenden Sie eine IndexedSeq. Welches ist auch Vector, aber das ist eine andere Sache.
Daniel C. Sobral
@ DuncanMcGregor: Vektor ist die Standardeinstellung, IndexedSeqdie implementiert wird Seq. Seq(1, 2, 3)ist eine, LinearSeqdie mit implementiert wird List.
Pathikrit
0

Wenn Sie unveränderlich programmieren und wahlfreien Zugriff benötigen, ist Seq der richtige Weg (es sei denn, Sie möchten ein Set, was Sie häufig tatsächlich tun). Andernfalls funktioniert List gut, außer dass die Operationen nicht parallelisiert werden können.

Wenn Sie keine unveränderlichen Datenstrukturen benötigen, bleiben Sie bei ArrayBuffer, da dies die Scala ist, die ArrayList entspricht.

Joshua Hartman
quelle
Ich halte mich an das Reich der unveränderlichen, beständigen Sammlungen. Mein Punkt ist, dass Vector List effektiv ersetzt hat, auch wenn ich keinen wahlfreien Zugriff benötige?
Duncan McGregor
2
Kommt etwas auf den Anwendungsfall an. Vektoren sind ausgeglichener. Die Iteration ist schneller als die Liste und der Direktzugriff ist viel schneller. Updates sind langsamer, da es sich nicht nur um ein Listenvoranstellen handelt, es sei denn, es handelt sich um ein Massenupdate aus einer Falte, das mit einem Builder durchgeführt werden kann. Trotzdem denke ich, dass Vector die beste Standardauswahl ist, da es so vielseitig ist.
Joshua Hartman
Ich denke, das bringt meine Frage auf den Punkt - Vektoren sind so gut, dass wir sie genauso gut dort verwenden können, wo Beispiele normalerweise Liste zeigen.
Duncan McGregor