0

Scala の効率性に関するあなたの意見に興味があります。Scala (およびその他の関数型プログラミング言語) は、コード作成効率と引き換えに効率性を犠牲にしているようです。以下のプログラムには、純粋な関数型アプローチとより古典的な C++ アプローチの両方のスタイルの挿入ソートを含む Scala プログラムのテストが含まれています。

出力からわかるように、関数型スタイルは 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))
}
4

1 に答える 1

1

これはより自然な関数型の実装であり、変更可能な実装よりも約 4 倍遅くなります。JVM を「ウォームアップ」するために、最初にソートを 1000 回実行したことに注意してください。たった 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}
}
于 2015-03-07T20:42:30.387 に答える