你能对一个可变的 Scala 集合进行适当的排序吗?

Can you sort a mutable Scala collection in place?

是否可以就地对 ArrayBuffer 或其他可变 Scala 集合进行排序?我看到 ArrayBuffer.sorted(和 sortBy)returns 一个新集合,Sorting.quicksort 确实对数组进行了排序,但不适用于 ArrayBuffers。

我问的原因是我在 Spark 中使用 combineByKey 来构建大小有限的评分对象集合(如 "top ten" 按键列表)。如果我合并一个新对象并且集合已经满了,我需要删除得分最低的对象。我可以使用像 PriorityQueue 或 SortedSet 这样的排序集合,但我不需要一直保持集合排序,只有在集合填满的情况下才需要。

那么有什么方法可以对 ArrayBuffer 或 ListBuffer 进行适当的排序吗?或者是否有其他一些支持就地追加和排序的集合?我确信有更好的方法可以做到这一点,但我是 Scala 的新手。

您可以使用 Java 的排序实用程序。

这是一个例子:

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

在 REPL:

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

如果您拥有的是 Scala ArrayBuffer,则调用 toArray 将其转换为数组。

当然,ArrayBuffer 上的toArray 会再次引入处理整个Buffer 的成本。如果这样做的成本很高,请检查您是否可以在 Array 而不是 ArrayBuffer 中获得初始结果。如果结果是固定长度的并且不太可能增长,那么你不需要 ArrayBuffer.

的动态扩展功能。

目前还没有对馆藏进行分类的设施。也就是说,如果您希望极少进行排序,则可以调查分别支持这两种情况,例如作为 Either[PriorityQueue[A], ArrayBuffer[A]];或者,如果您希望排序相当普遍,您应该使用一种数据结构,在这种结构中您每次添加元素时都不会付出这样的代价——这意味着只需使用 SortedSetPriorityQueue。否则你会变得很慢 真的 很快。 (n^2 log n 变大很快,如果每次添加新元素时都进行完整排序,就会得到这种结果。)

您可以使用 Scala 的 JavaConverters 通过 1 行代码委托给 Java 的 Arrays.sort

假设您在可变缓冲区中有 Foo 的实例,您希望使用比较器 fooComparator.

对其进行排序
import scala.collection.mutable
import scala.collection.JavaConverters._

…

val buffer = mutable.ArrayBuffer[Foo]()

…

buffer.asJava.sort(fooComparator) // sort "in place" (actually hides 1 copy)

然而,对于极端性能而言,ArrayBuffer 似乎无法使用,普通固定大小 Array 是可行的方法。好处是 JavaConverters.asJava 不会复制项目。但是 Java 的 List.sort 方法在内部将项目复制到 Array 并调用 Arrays.sort。 (然后它将排序的项目分配回原始集合)

也许 "full solution" 将定义您自己的 Scala ArrayBuffer 版本,它公开用于排序的底层数组。由于 Scala 的集合库的设置方式,在 Scala 中实现您自己的集合类型可以做所有相同的事情,再加上您自己的技巧通常很容易。