Scala efficiency

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. Запуск всего лишь 1000 предметов только один раз довольно бессмысленен из-за накладных расходов JIT и так далее.

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} 
}