Scala-Äquivalent von java.util.ArrayList

Lesezeit: 6 Minuten

Benutzer-Avatar
bleiben13

Ich mache ein Projekt in Scala, bin aber ziemlich neu in der Sprache und habe einen Java-Hintergrund. Ich sehe, dass Scala keine ArrayList hat, also frage ich mich, wie Scalas Äquivalent zu Javas ArrayList heißt und ob es wichtige Unterschiede zwischen der Java- und der Scala-Version gibt.

BEARBEITEN: Ich suche weniger nach einem bestimmten Verhalten als vielmehr nach einer internen Darstellung (in einem Array gespeicherte Daten, aber das gesamte Array ist nicht sichtbar, nur der Teil, den Sie verwenden).

  • Was wäre der Unterschied zwischen dem sichtbaren gesamten Array und dem Teil, den Sie verwenden?

    – Daniel C. Sobral

    27. November 2011 um 18:42 Uhr

  • @Daniel, der Hauptunterschied für mich besteht darin, dass ArrayList die Größe für mich handhabt (dh wenn ich nicht weiß, was es im Voraus sein wird oder weiß, dass es sich ändern wird, muss ich mir keine Gedanken darüber machen, zusätzlichen Speicherplatz zuzuweisen und zu behalten verfolgen, wie viel Platz ich tatsächlich verbrauche).

    – bleiben13

    27. November 2011 um 21:21 Uhr

Benutzer-Avatar
Daniel C. Sobral

Mir fallen 3 spezifischere Fragen ein, die ich auf deine ansprechen könnte:

  • Was ist die Standardsammlung von Scala?
  • Welche Scala-Kollektion hat ähnliche Eigenschaften ArrayList?
  • Wofür ist ein guter Ersatz Array in Scala?

Hier also die Antworten dazu:

Was ist die Standardsammlung von Scala?

Scalas Äquivalent zu Java List Schnittstelle ist die Seq. Es gibt auch eine allgemeinere Schnittstelle, nämlich die GenSeq — der Hauptunterschied besteht darin, dass a GenSeq Je nach Implementierung können Operationen seriell oder parallel verarbeitet werden.

Denn Scala ermöglicht Programmierern die Nutzung Seq Als Fabrik machen sie sich oft nicht die Mühe, eine bestimmte Implementierung zu definieren, es sei denn, sie kümmern sich darum. Wenn sie das tun, wählen sie normalerweise entweder Scala’s aus List oder Vector. Sie sind beide unveränderlich und Vector hat eine gute indizierte Zugriffsleistung. Auf der anderen Seite, List macht sehr gut die Operationen, die es gut macht.

Welche Scala-Kollektion hat ähnliche Eigenschaften ArrayList?

Das wäre scala.collection.mutable.ArrayBuffer.

Wofür ist ein guter Ersatz Array in Scala?

Nun, die gute Nachricht ist, dass Sie es einfach verwenden können Array in Scala! Auf Java, Array wird oft wegen seiner generellen Unverträglichkeit mit Generika gemieden. Es ist eine Kovarianten-Sammlung, während Generika unveränderlich sind, sie sind änderbar – was ihre Kovarianz zu einer Gefahr macht, sie akzeptiert Primitive, wo Generika dies nicht tun, und sie hat einen ziemlich begrenzten Satz von Methoden.

In Scala, Array – was immer noch so ist Array wie in Java — ist unveränderlich, wodurch die meisten Probleme verschwinden. Scala akzeptiert AnyVal (das Äquivalent zu Primitiven) als Typen für seine “Generika”, obwohl es Auto-Boxing durchführt. Und durch das Muster “Meine Bibliothek bereichern”, ALLE von Seq Methoden stehen zur Verfügung Array.

Also, wenn Sie eine stärkere wollen Arrayverwenden Sie einfach ein Array.

Was ist mit einer Sammlung, die schrumpft und wächst?

Die Standardmethoden, die für alle Sammlungen verfügbar sind, produzieren alle Neu Sammlungen. Wenn ich das zum Beispiel mache:

val ys = xs filter (x => x % 2 == 0)

Dann ys wird ein … sein Neu Sammlung, während xs wird immer noch die gleiche sein wie vor diesem Befehl. Dies ist wahr, egal was xs war: Array, Listetc.

Das hat natürlich seinen Preis – immerhin Sie sind eine neue Kollektion produzieren. Die unveränderlichen Sammlungen von Scala können diese Kosten viel besser bewältigen, weil sie es sind hartnäckigaber es hängt davon ab, welche Operation ausgeführt wird.

Dagegen kann keine Sammlung viel ausrichten filteraber ein List hat eine hervorragende Leistung beim Generieren einer neuen Sammlung, indem ein Element vorangestellt oder der Kopf entfernt wird – die grundlegenden Operationen eines Stacks, um genau zu sein. Vector hat eine gute Leistung bei einer Reihe von Operationen, aber es zahlt sich nur aus, wenn die Sammlung nicht klein ist. Bei Sammlungen von beispielsweise bis zu hundert Elementen könnten die Gesamtkosten die Gewinne übersteigen.

Sie können also tatsächlich Elemente zu einer hinzufügen oder entfernen Arrayund Scala erzeugt a Neu Array für Sie, aber Sie zahlen die Kosten für eine vollständige Kopie, wenn Sie dies tun.

Veränderliche Scala-Sammlungen fügen einige andere Methoden hinzu. Insbesondere die Sammlungen, die vergrößert oder verkleinert werden können – ohne eine neue Sammlung zu erstellen – implementieren die Growable und Shrinkable Züge. Sie garantieren zwar keine gute Leistung bei diesen Vorgängen, weisen Sie jedoch auf die Sammlungen hin, die Sie auschecken möchten.

  • Hier ist ein Online-Test, der demonstriert ArrayList etwa 3 mal schneller als LinkedList, trotz der notwendigen Umschichtungen. Ich musste reduzieren N damit es online funktioniert. Mit N = 50000000 auf meiner eigenen Maschine, ArrayList ist etwa 10 mal schneller als LinkedList. Welche Ergebnisse erhalten Sie auf Ihrer Maschine? Ich würde mich wirklich wundern, wenn LinkedList war schneller, weil es mehr Zuweisungen pro Einfügung (Zeit) benötigt und jedes Element ein zusätzliches Node-Objekt (Platz) benötigt.

    – fredoverflow

    12. März 2013 um 16:26 Uhr


  • @DanielC.Sobral: Hier ist ein Follow-up-Online-Test, der zeigt ArrayList 12 mal schneller als LinkedList für Einsätze in der Mitte. LinkedList erscheint nur schneller beim Einfügen am Anfang.

    – Muhende Ente

    12. März 2013 um 17:02 Uhr


  • @DanielC.Sobral: wächst an ArrayList die sich bei jeder Neuzuordnung verdoppelt, bedeutet, dass Sie höchstens doppelt so viele Kopien erstellen, wie Elemente vorhanden sind – oder mit anderen Worten, jedes Element wird im Durchschnitt kopiert zweimal. Das heißt, egal, wie stark Sie das Array vergrößern. Und im Gegenzug erhalten Sie eine effizientere Datenstruktur mit viel besseren Lokalitäts- und Cache-Eigenschaften. Eine verknüpfte Liste ist praktisch noch nie Schneller. Wenn du noch nie Elemente nachschlagen müssen, und Sie noch nie müssen über die Datenstruktur iterieren, dann eine verknüpfte Liste kann sei schneller. Andernfalls? Nein.

    – jalf

    12. März 2013 um 19:45 Uhr

  • @DanielC.Sobral: In diesen Fällen ArrayList Wille normalerweise immer noch schneller sein, weil es weniger Zuweisungen, weniger Indirektion, bessere Speicherlokalität gibt. Beachten Sie das Einfügen in die Mitte einer Liste erfordert, dass Sie iterieren, um die Mitte zu finden. Und das ist viel langsamer für eine verknüpfte Liste. Als Faustregel gilt: „Bei manchen Dingen ist das selbstverständlich ArrayList ist schneller. Für andere Dinge ist es überraschend, dass ArrayList ist schneller”. 🙂

    – jalf

    13. März 2013 um 9:11 Uhr

  • Das war nicht immer so, aber die Lücke zwischen CPU- und Speicherleistung ist extrem groß geworden. Ein wahlfreier Speicherzugriff ist schmerzhaft langsam, und verknüpfte Listen sind es alle zufällige Zugriffe. ArrayList (oder jede andere dynamische Array-Datenstruktur) hat praktisch keine wahlfreien Zugriffe. Aus Hardware-Sicht ist das a riesig Vorteil, fast egal, welche Operationen Sie an Ihrer Datenstruktur durchführen

    – jalf

    13. März 2013 um 9:14 Uhr

Es ist ArrayBuffer aus scala.collection.mutable. Sie können die Scaladocs finden hier.

Es ist schwer, genau zu sagen, was Sie tun sollten, weil Sie nicht gesagt haben, welches Verhalten Sie haben ArrayList Sie interessieren sich für die Verwendung. Es ist sinnvoller, darüber nachzudenken, welche Scala-Merkmale Sie nutzen möchten. Hier ist eine gute Erklärung: http://grahamhackingscala.blogspot.com/2010/02/how-to-convert-java-list-to-scala-list.html.

Das heißt, Sie möchten wahrscheinlich eine Art von IndexedSeq.

1179620cookie-checkScala-Äquivalent von java.util.ArrayList

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy