Scala 集合已排序、sortWith 和 sortBy 性能

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

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

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

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

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

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

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

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