Scala quickSort使用Ordering [T]速度慢10倍

Question

我正在根据自定义排序对整数索引进行一些排序.我发现这里使用的Ordering [T]使用直接调用compare方法比使用手工制作的quickSort慢至少10倍.这看起来非常昂贵!

val indices: Array[Int] = ...

class OrderingByScore extends Ordering[Int] { ... }

time { (0 to 10000).par.foreach(x => {
  scala.util.Sorting.quickSort[Int](indices.take(nb))(new OrderingByScore)
})}
// Elapsed: 30 seconds

与手工制作的sortArray相比,此处可以修改以添加ord: Ordering[Int]参数:

def sortArray1(array: Array[Int], left: Int, right: Int, ord: Ordering[Int]) = ...

time { (0 to 10000).par.foreach(x => {
  sortArray1(indices.take(nb), 0, nb - 1, new OrderingByScore)
})}
// Elapsed: 19 seconds

最后,相同的代码片段,但使用精确类型而不是(ord: OrderingByScore):

def sortArray2(array: Array[Int], left: Int, right: Int, ord: OrderingByScore) = ...

time { (0 to 10000).par.foreach(x => {
  sortArray2(indices.take(nb), 0, nb - 1, new OrderingByScore)
})}
// Elapsed: 1.85 seconds

我很惊讶地发现每个版本之间存在这样的差异!

在我的示例中,indices数组基于在包含组合分数的另一个Doubles数组中找到的值进行排序.此外,排序是稳定的,因为它使用索引本身作为次要比较.另外,为了使测试可靠,我必须在并行循环中使用"indices.take(nb)",因为排序会修改输入数组.与我带来的问题相比,这种惩罚可以忽略不计.对要点的完整代码在这里.

您的建议非常受欢迎,以改善..但尽量不要改变索引和分数数组的基本结构.

注意:我在scala 2.10 REPL中运行.

Answer 1

问题是scala.math.Ordering不专业.因此,每次使用类似原语调用compare方法时Int,类型的两个参数Int都被装箱java.lang.Integer.这会产生许多短暂的物体,这会大大减慢速度.

该尖顶库有订货称为专用版本spire.algebra.Order应该会快很多.您可以尝试在代码中替换它并再次运行基准测试.

尖顶中还有排序算法.所以也许只是试试那些.

基本上,无论何时你想以高性能的方式用基元进行数学运算,尖顶都是可行的方法.

此外,如果您想要信任结果,请使用适当的微基准测试工具(如Thyme或JMH)进行基准测试.