Scala性能：命令式风格 vs 函数式风格

Question

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

其中一个是命令式风格：

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方式"（函数式）更受青睐，因此更高效。注意：作者确实提到函数式风格会使用更多内存。

- sivabudh

---

可能是重复的问题：Scala函数式编程比传统编程慢吗？ - missingfaktor

“简洁”并不等同于“可读性”。证据：J编程语言。 - JUST MY correct OPINION

我现在认为Scala By Example的作者试图展示另一种更简洁的解决问题的方式。总结一下：您在代码的所有部分中尽可能地编写简洁的程序，以便获得最大的简洁性和生产力。然后运行您的应用程序，如果它太慢，请对瓶颈部分进行剖析和优化。 - sivabudh

Answer 1

这要看情况而定。如果你查看Scala源代码，通常会在“底层”使用命令式风格以提高性能, 但在许多情况下，正是这些调整允许您编写性能良好的功能性代码。因此，通常可以想出一个足够快速的函数式解决方案，但必须小心并知道自己在做什么（特别是涉及数据结构时）。例如，第二个示例中的数组连接不太好，但可能还不至于很糟糕，但在此使用列表，并使用 ::: 连接它们，则过于浪费。

但如果你不实际“测量”性能，那就只是有教养地猜测。在复杂项目中，很难预测性能，特别是当对象创建和方法调用由编译器和JVM进行优化时。

我建议从函数式风格开始。如果太慢，请对其进行分析。通常会有更好的函数式解决方案。如果没有，您可以将命令式风格（或两种风格的混合）作为最后手段。

- Landei

---

但这有点违背初衷，不是吗？我的意思是，Scala被誉为首个将函数式编程和面向对象编程桥接起来的语言。但是，如果你不能确定以函数式编程的方式进行编程会很高效，那么那些关心性能的人最终会用“Java”的方式来使用Scala？ - sivabudh

看一下例子。哪一个更容易理解？函数式风格实际上告诉你算法做了什么：“选择一个枢轴元素，对较小的元素进行排序，对较大的元素进行排序，然后将所有东西放在一起”。这是与命令式示例相比的巨大优势，后者主要关注循环变量和数组索引。因此，如果函数式风格运作良好，我们通常会非常顺利，但我们仍然可以使用命令式风格作为备用方案。然而，请不要将面向对象等同于命令式风格。在函数式上下文中，类和对象可以很好地发挥作用。 - Landei

在任何大型项目中，你都会发现实际上只有很少的代码需要非常高效。在这种情况下，你经常需要退回到命令式结构。Scala 支持这一点。其余的时间，最好以使你的设计在代码中尽可能清晰明显的方式编码。这可以是函数式的、过程式的、面向对象的，或者它们的某种组合。Scala 支持所有这些。 - Dave Griffith

@ShaChris23 你期望什么？当然，你不能确定以函数式编程的方式编写程序总是高效的，就像以命令式或面向对象的方式编写程序也不总是高效的一样。函数式编程并不是一个银弹，它不会自动使你的程序高效，这与Scala本身无关。在任何编程风格中，你都不能免费获得高效性，你仍然需要自己考虑它。 - Jesper

感谢@Landei、@Dave和@Jesper的所有热心评论。 - sivabudh