Können Sie eine veränderbare Scala-Sammlung an Ort und Stelle sortieren?

Question

Ist es möglich, einen ArrayBuffer oder eine andere veränderbare Scala-Sammlung zu sortieren? Ich sehe, dass ArrayBuffer.sorted (und sortBy) eine neue Sammlung zurückgibt und Sorting.quicksort ein Array an Ort und Stelle sortiert, aber nicht mit ArrayBuffers.

Der Grund, warum ich frage, ist, dass ich combineByKey in Spark verwende, um Sammlungen von gewerteten Objekten zu erstellen, die in der Größe begrenzt sind (wie eine "Top-Ten" -Liste nach Schlüssel). Wenn ich ein neues Objekt einfüge und die Sammlung bereits voll ist, muss ich das Objekt mit der niedrigsten Punktzahl fallen lassen. Ich könnte eine sortierte Sammlung wie eine PriorityQueue oder SortedSet verwenden, aber ich muss die Sammlungen nicht ständig sortiert halten, sondern nur dann, wenn eine Sammlung voll ist.

Gibt es eine Möglichkeit, einen ArrayBuffer oder ListBuffer zu sortieren? Oder gibt es eine andere Sammlung, die das Anhängen und Sortieren unterstützt? Ich bin mir sicher, dass es einen besseren Weg dafür gibt, aber ich bin neu in Scala.

Answer 1

Es gibt derzeit keine Einrichtungen zum Sortieren von Sammlungen vorhanden. Das heißt, wenn Sie erwarten, dass Sie extrem selten sortieren müssen, könnten Sie untersuchen, ob Sie beide separat unterstützen, z. als Either[PriorityQueue[A], ArrayBuffer[A]]; oder wenn Sie erwarten, dass die Sortierung relativ häufig vorkommt, sollten Sie eine Datenstruktur verwenden, bei der Sie nicht jedes Mal, wenn Sie ein Element hinzufügen, eine solche Strafe zahlen - also einfach die oder PriorityQueue verwenden. Sonst wirst du langsam wirklich schnell. (n^2 log n wird schnell groß, was Sie bekommen, wenn Sie eine vollständige Sortierung jedes Mal tun, wenn Sie ein neues Element hinzufügen.)

Answer 2

Sie können die Sortierwerkzeuge von Java verwenden. Hier

ein Beispiel:

val myArray = Array(1,12,5,6) 
java.util.Arrays.sort(myArray) 

Am REPL:

> myArray 
res3: Array[Int] = Array(1, 5, 6, 12) 

Wenn das, was Sie haben eine Scala ist ArrayBuffer dann toArray nennen es in ein Array zu konvertieren.

Natürlich die toArray on ArrayBuffer induziert die Kosten für die Bewältigung der gesamten Puffer wieder. Wenn dies kostspielig ist, überprüfen Sie, ob Sie Ihre ersten Ergebnisse in einer Array statt einer ArrayBuffer erhalten können. Wenn die Ergebnisse eine feste Länge haben und unwahrscheinlich wachsen, benötigen Sie keine dynamischen Erweiterungsfunktionen von ArrayBuffer.