Scala性能:命令式与功能性风格

Question

我是Scala的新手,只是阅读Scala By Example.在第2章中,作者有2个不同版本的Quicksort.

一个是势在必行的风格:

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

这取决于.如果您在斯卡拉来源看,往往是为了使用"引擎盖下"是高性能势在必行的风格-但在很多情况下,正是这些调整让你编写高性能的功能代码.所以通常你可以提出一个足够快的功能解决方案,但你必须小心并知道你做了什么(特别是关于你的数据结构).例如,第二个例子中的数组concat不是很好,但可能不是太糟糕 - 但是在这里使用Lists并用:::连接它们会有点过分.

但是,如果你没有真正衡量绩效,那只不过是受过教育的猜测.在复杂的项目中,很难预测性能,特别是对象创建和方法调用等事情越来越多地被编译器和JVM优化.

我建议从功能风格开始.如果它太慢,请对其进行分析.通常有一个更好的功能解决方案.如果没有,您可以使用命令式(或两者兼而有之)作为最后的手段.