QuickSort传统与功能风格是什么导致这种差异？

Question

我正在比较用scala语言编写的两个代码.

package chapter01

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

  def sortTraditionl(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 main(args: Array[String]): Unit = {

    val arr = Array.fill(100000) { scala.util.Random.nextInt(100000 - 1) }
    var t1 = System.currentTimeMillis
    sortFunctional(arr)
    var t2 = System.currentTimeMillis
    println("Functional style : " + (t2-t1))

    t1 = System.currentTimeMillis
    sortTraditionl(arr)
    t2 = System.currentTimeMillis
    println("Traditional style : " + (t2-t1))
  }

}

第一个块是以功能样式编写的,第二个块是传统的快速排序.这些例子来自奥德斯基的书.

传统与功能之间存在巨大差异.

Functional style : 450
Traditional style : 30

我只是想知道造成这种差异的原因.我不知道scala的深度,但我最初的猜测是传统的使用没有变异和任何闭包.我们可以做些什么来改善功能风格的表现？

Answer 1

好吧,你的功能排序有点不对劲.它有效,但它会调用xs.filter三次!因此,在每次通话中,您都会遍历列表三次,而不是一次.

考虑这个实现:

def sort(ls: List[Int]): List[Int] = {
  ls match {
    case Nil => Nil
    case pivot :: tail => {
      val (less, greater) = tail.partition(_ < pivot)
      sort(less) ::: pivot :: sort(greater)
    }
  }
}

我不确定它会给你所需的性能,但它避免了不必要的遍历列表.

更多信息,您可以阅读此处描述的答案,了解使用该实现的实现foldLeft

Answer 2

它在书中提到:

命令性和功能性实现都具有相同的渐近复杂度 - 在平均情况下为O(N log(N)),在最坏情况下为O(N2).但是,通过修改参数数组来执行命令式实现,函数实现返回一个新的排序数组并保持参数数组不变.因此,功能实现需要比命令性存储器更多的瞬态存储器.

传统的传统操作在原始阵列上进行,因此不需要复制,也不需要额外的内存.功能部件分配新阵列并在每次调用时复制大量数据.