wake-up-neo.com

Wann sollte ich in Scala Vector wählen?

Es scheint, als wäre Vector zu spät zur Scala -Sammlungsparty gekommen, und alle einflussreichen Blog-Beiträge waren bereits abgereist.

In Java ArrayList ist die Standardauflistung - ich verwende möglicherweise LinkedList, aber nur, wenn ich einen Algorithmus durchdacht und die Optimierung sorgfältig genug durchgeführt habe. Sollte ich in Scala Vector als Standard Seq verwenden oder versuchen, herauszufinden, wann List tatsächlich angemessener ist?

182
Duncan McGregor

Standardmäßig wird Vector verwendet. Es ist schneller als List für fast und speichereffizienter für Sequenzen, die nicht nur unbedeutend sind. Siehe hierzu Dokumentation der relativen Leistung von Vector im Vergleich zu den anderen Sammlungen. Es gibt einige Nachteile, die mit Vector verbunden sind. Speziell:

  • Aktualisierungen am Kopf 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 der Mustererkennung für List besser war, aber dies wurde in 2.10 mit generalisierten +: Und :+ Korrigiert. Extraktoren.

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

Wenn ich eine Sequenz vom Typ List[A] Habe, behaupte ich effektiv zwei Dinge. Erstens ist mein Algorithmus (und meine Daten) vollständig stapelstrukturiert. Zweitens behaupte ich, dass die einzigen Dinge, die ich mit dieser Sammlung tun werde, voll sind, O(n) Durchquerungen. Diese beiden gehen wirklich Hand in Hand. Umgekehrt, wenn ich Ich habe etwas vom Typ Vector[A], das only ist, dass meine Daten eine genau definierte Reihenfolge und eine endliche Länge haben. Daher sind die Aussagen bei Vector schwächer, was zu einer größeren Flexibilität führt.

257
Daniel Spiewak

Nun, ein List kann unglaublich schnell sein, wenn der Algorithmus nur mit ::, head und tail implementiert werden kann. Ich hatte kürzlich eine Objektstunde darüber, als ich Javas split durch Generieren eines List anstelle eines Array besiegte, und konnte das mit nichts anderem übertreffen.

List hat jedoch ein grundlegendes Problem: Es funktioniert nicht mit parallelen Algorithmen. Ich kann ein List nicht effizient in mehrere Segmente aufteilen oder zurückverketten.

Es gibt andere Arten von Sammlungen, die Parallelität viel besser verarbeiten können - und Vector ist eine davon. Vector hat auch eine großartige Lokalität - was List nicht tut - was für einige Algorithmen ein echtes Plus sein kann.

Alles in allem ist Vector die beste Wahl außer Sie haben spezielle Überlegungen, die eine der anderen Sammlungen bevorzugen - zum Beispiel könnten Sie Stream wählen. wenn Sie eine verzögerte Auswertung und Zwischenspeicherung wünschen (Iterator ist schneller, zwischenspeichert aber nicht), oder List, wenn der Algorithmus natürlich mit den von mir erwähnten Operationen implementiert wird.

Übrigens ist es vorzuziehen, Seq oder IndexedSeq zu verwenden, es sei denn, Sie möchten ein bestimmtes Stück API (wie List::) Oder sogar GenSeq oder GenIndexedSeq, wenn Ihr Algorithmus parallel ausgeführt werden kann.

87

Wenn Sie für unveränderliche Sammlungen eine Sequenz wünschen, entscheiden Sie sich hauptsächlich für die Verwendung eines IndexedSeq oder eines LinearSeq, die unterschiedliche Leistungsgarantien bieten. Ein IndexedSeq bietet schnellen Direktzugriff auf Elemente und eine schnelle Längenoperation. Ein LinearSeq bietet nur über head einen schnellen Zugriff auf das erste Element, verfügt jedoch auch über eine schnelle tail -Operation. (Aus der Seq-Dokumentation entnommen.)

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

Für ein LinearSeq würden Sie normalerweise ein List oder sein faules Äquivalent Stream wählen. Andere Beispiele sind Queues und Stacks.

Also in Java) Begriffen, ArrayList ähnlich wie in Scala Vector und LinkedList ähnlich wie in Scala List. Aber in Scala Ich würde eher List als Vector verwenden, da Scala Funktionen, die das Durchlaufen der Sequenz beinhalten, wie Mapping, Folding, Iterieren usw. Mit diesen Funktionen können Sie in der Regel die Liste als Ganzes bearbeiten, anstatt auf einzelne Elemente nach dem Zufallsprinzip zuzugreifen.

Einige der Aussagen hier sind verwirrend oder sogar falsch, insbesondere die Idee, dass unveränderlich.Vektor in Scala ist so etwas wie eine ArrayList. List und Vector sind beide unveränderlich, persistent (dh "billig, um eine zu bekommen") modifizierte Kopie ") Datenstrukturen. Es gibt keine vernünftige Standardauswahl, da dies für veränderbare Datenstrukturen der Fall sein könnte, sondern vielmehr davon abhängt, was Ihr Algorithmus tut. Liste ist eine einfach verknüpfte Liste, während Vektor eine Ganzzahl zur Basis 32 ist. Das heißt, es ist eine Art Suchbaum mit Knoten des Grades 32. Mit dieser Struktur kann Vector die gebräuchlichsten Operationen relativ schnell bereitstellen, dh in O (log_32 (n)). Dies funktioniert für das Voranstellen, Anhängen, Aktualisieren, wahlfreien Zugriff und Zerlegen Die Iteration in sequentieller Reihenfolge ist linear, die Auflistung dagegen liefert nur lineare Iteration und konstante Vorlaufzeit, die Zerlegung in Kopf/Schwanz, alles andere nimmt generell lineare Zeit in Anspruch.

Dies könnte so aussehen, als wäre Vector in fast allen Fällen ein guter Ersatz für List, aber Präpendieren, Zerlegen und Iterieren sind häufig die entscheidenden Operationen für Sequenzen in einem Funktionsprogramm, und die Konstanten dieser Operationen sind für vector (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 Präpendieren für Listen etwa 100-mal schneller ist, die Zerlegung in Kopf/Schwanz für 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 sie mit einem Builder erstellen, anstatt den Elementen nacheinander vorangestellt oder angehängt zu werden.) Natürlich sind alle Operationen, die für Listen eine lineare Zeit, für Vektoren jedoch eine konstante Zeit (als Direktzugriff oder Anhängen) benötigen, für große Listen unerschwinglich langsam.

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: Im Grunde ist es egal, wir sollten unseren Algorithmus generisch programmieren und könnten sogar von der Annahme paralleler Sequenzen profitieren. Für sequentielle Operationen ist List wahrscheinlich etwas schneller. Sie sollten es jedoch bewerten, wenn Sie optimieren müssen.
  • Wir brauchen viele zufällige Zugriffe und verschiedene Aktualisierungen, daher sollten wir vector verwenden, da die Liste unerschwinglich langsam sein wird.
  • Wir bearbeiten Listen auf eine klassische funktionale Art und Weise, indem wir sie durch rekursive Zerlegung voranstellen und iterieren: use list, vector wird um einen Faktor 10-100 oder mehr langsamer.
  • Wir haben einen leistungskritischen Algorithmus, der im Grunde genommen unerlässlich ist und eine Menge zufälliger Zugriffe auf eine Liste ausführt, etwa beim schnellen Sortieren an Ort und Stelle: Verwenden Sie eine unerlässliche Datenstruktur, z. ArrayBuffer, lokal und kopieren Sie Ihre Daten von und zu ihm.
20
dth

In Situationen, in denen viel zufälliger Zugriff und zufällige Mutation vorkommen, scheint ein Vector (oder - wie im docs - ein Seq) ein guter Kompromiss zu sein. Dies ist auch das, was die Leistungsmerkmale vorschlagen.

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

2
Debilski

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

Wenn Sie keine unveränderlichen Datenstrukturen benötigen, halten Sie sich an ArrayBuffer, da es Scala entspricht ArrayList.

0
Joshua Hartman