Scala 性能 : imperative vs functional style

Question

我是 Scala 新手，刚刚阅读 Scala By Example 。在第2章中，作者有2个不同版本的快速排序。

一种是命令式:

def sort(xs: Array[Int]) {
    def swap(i: Int, j: Int) {
        val t = xs(i); xs(i) = xs(j); xs(j) = t
    }
    def sort1(l: Int, r: Int) {
        val pivot = xs((l + r) / 2)
        var i = l; var j = r
        while (i <= j) {
            while (xs(i) < pivot) i += 1
            while (xs(j) > pivot) j -= 1
            if (i <= j) {
                swap(i, j)
                i += 1
                j -= 1
            }
        }
        if (l < j) sort1(l, j)
        if (j < r) sort1(i, r)
    }
    sort1(0, xs.length - 1)
}

一种是函数式风格:

def sort(xs: Array[Int]): Array[Int] = {
  if (xs.length <= 1) xs
  else {
    val pivot = xs(xs.length / 2)
    Array.concat(
      sort(xs filter (pivot >)),
           xs filter (pivot ==),
      sort(xs filter (pivot <)))
  }
}

函数式风格相对于命令式风格的明显优势是简洁。但性能呢？由于它使用递归，我们是否会像在 C 等其他命令式语言中那样为性能损失付出代价？或者，Scala 作为一种混合语言，“Scala 方式”(函数式)是首选，因此更高效。

注意:作者确实提到函数式风格确实会占用更多内存。

Answer 1

这要看情况。如果您查看 Scala 源代码，通常会在“幕后”使用命令式样式来提高性能 - 但在许多情况下，正是这些调整允许您编写高性能的函数式 em> 代码。因此，通常您可以想出一个足够快的功能解决方案，但您必须小心并知道您在做什么(特别是关于您的数据结构)。例如。第二个示例中的数组连接不太好，但可能也不算太糟糕 - 但在这里使用列表并用::: 连接它们就有点矫枉过正了。

但是，如果您没有实际测量性能，那么这只不过是有根据的猜测。在复杂的项目中，预测性能确实很难，特别是当对象创建和方法调用等事情被编译器和 JVM 越来越优化时。

我建议从函数式风格开始。如果速度太慢，请对其进行分析。通常有更好的功能解决方案。如果没有，您可以使用命令式(或两者的混合)作为最后的手段。