performance - Scala Collection 排序、sortWith 和 sortBy 性能

Question

Scala 在标准库中包含了几种对列表进行排序的方法，例如对列表列表进行排序，可以使用:

list.sorted
list.sortWith(_<_)
list.sortBy(x=>x)

虽然这些可能是对列表进行排序的最简单方法，但我发现对于较大的列表，它们具有显着的性能缺陷。

例如，要对一百万个整数进行排序，sorted 平均需要 500 毫秒，而 sortWith 和 sortBy 大约需要 700 毫秒。与之相比，scala.util.Sorting.quickSort 大约需要 120 毫秒，java.util.Arrays.sort 大约需要 100 毫秒。对于较大的列表，随着我们进一步扩展，会观察到这种多因素差异。模式如下图所示。



这种性能滞后的原因是什么？为什么标准方法不使用更有效的算法/实现？

Answer 1

注意线条如何具有相同的斜率，但彼此偏移？使用对数刻度，我们正在查看一个恒定的因子差异。 sorted和 friend 支付转换 List 的费用到 Array ，排序(实际上是 java.util.Arrays.sort)，然后转换回 List . scala.util.Sorting.quickSort和 java.util.Arrays.sort直接对数组进行操作。 log n快速排序的因素n log n性能在很大程度上是无关紧要的，因此创建数组和结果列表所需的线性时间最终会得到恒定的因子差异。性能差五倍可能看起来很糟糕，但请记住 List每个元素都有一个 cons 单元格，这在创建 Array 时会产生大量随机访问。 ，然后创建新的 List需要花费时间分配内存，并且很可能需要一个或两个垃圾收集周期。

对于原语列表，情况更糟。 List是通用的，所以任何原语都必须被装箱，这增加了另一层间接性。不幸的是Array创建的也包含盒装值。实际上，您最终会排序 Array[java.lang.Integer]当你真的想对 Array[Int] 进行排序时.

总结一下:排序算法是相同的，但是可变数组优于不可变单链表是有充分理由的。