java - Scala 效率

Question

我对您对 Scala 效率的看法很感兴趣。看起来 Scala(和其他函数式编程语言)以效率换取代码编写效率。下面的程序包含对 Scala 程序的测试，该程序包含纯函数方法和更经典的 C++ 方法风格的插入排序。

从输出中可以看出，函数式风格的效率比 C++ 风格低一个数量级。我可以对功能风格进行改进吗？

package Algorithms

case object Sorter {
 def mutableInsertSort(a: Vector[Int]): Vector[Int] = {
    var ar = a.toArray
    for (j<-1 to ar.size - 1) {
      val k = ar(j)
      var i = j
      while ((i>0) && (ar(i-1)) > k) {
        ar(i) = ar(i-1)
        i = i - 1
      }
      ar(i) = k
    }
    ar.toVector
  }

 def insertSort(a: Vector[Int]): Vector[Int] = {
    def immutableInsertSort(target: Vector[Int], i: Int): Vector[Int] = {
      if (i == target.size) target
      else { 
        val split = target.splitAt(i)    // immutable overhead
        val sorted = split._1.takeWhile(x=>x<target(i))
        val newTarget = sorted ++ Vector(target(i)) ++ split._1.slice(sorted.size, split._1.size) ++ split._2.tail  //last two segments are immutable overheads
        immutableInsertSort(newTarget, i + 1)   //immutable overhead
      }
    }
    immutableInsertSort(a, 1)
  }
}

object Sorting extends App {
  val a = (1 to 1000).toVector.map(x=>(math.random*2000).toInt)
  val t1 = System.nanoTime
  Sorter.insertSort(a)
  println ("I" + (System.nanoTime - t1))
  val t2 = System.nanoTime
  Sorter.mutableInsertSort(a)
  println ("M" + (System.nanoTime - t2))
}

Answer 1

这是一种更自然的函数式实现，并且比可变实现慢大约 4 倍。注意，我首先运行了 1000 次排序来“预热”JVM。由于 JIT 开销等原因，仅运行一次 1000 个项目是相当没有意义的。

def insertSort2(a: Seq[Int]):Seq[Int] = {
    def insertOne(b:Seq[Int], x:Int):Seq[Int] = {
       val (before, after) = b.span(_ < x)
       before ++ (x +: after)
    }
    a.foldLeft(Seq[Int]()) {insertOne}
}