4

オイラーの問題をコーディングしているときに、奇妙だと思うものに出くわしました。

toString.mapメソッドはtoString.toArray.mapよりも低速です。

次に例を示します。

def main(args: Array[String]) 
{
    def toDigit(num : Int) = num.toString.map(_ - 48) //2137 ms
    def toDigitFast(num : Int) = num.toString.toArray.map(_ - 48) //592 ms

    val startTime = System.currentTimeMillis;

    (1 to 1200000).map(toDigit)

    println(System.currentTimeMillis - startTime)
}

文字列のメソッドマップは、配列上のマップにフォールバックするべきではありませんか？なぜそのような顕著な違いがあるのですか？（数を増やすと、アレイ以外の場合でもスタックオーバーフローが発生することに注意してください）。

4

2 に答える 2

6

オリジナル

を解決するために暗黙を使用しているのに対し、暗黙をtoString.map使用していることが原因である可能性があります。WrappedStringtoString.toArray.mapWrappedArraymap

mapで定義されているように、見てみましょうTraversableLike：

def map[B, That](f: A => B)(implicit bf: CanBuildFrom[Repr, B, That]): That = {
  val b = bf(repr)
  b.sizeHint(this)
  for (x <- this) b += f(x)
  b.result
}

WrappedStringStringBuilderビルダーとしてを使用します：

def +=(x: Char): this.type = { append(x); this }

def append(x: Any): StringBuilder = {
  underlying append String.valueOf(x)
  this
}

のString.valueOf呼び出しでは、インスタンスでAnyJavaを使用し、場合によっては最初にボックス化されます。これらの余分な操作は、アレイビルダーのおそらく短いコードパスとは対照的に、速度の違いの原因となる可能性があります。Object.toStringChar

これは推測ですが、測定する必要があります。

編集

toDigit改訂後も一般的なポイントは変わりませんが、メソッドが読み間違えたときに翻訳された文字列ではなくIntシーケンス（または同様のもの）を返すため、間違った暗黙を参照しました。

toDigitLowPriorityImplicits.fallbackStringCanBuildFrom[T]: CanBuildFrom[String, T, immutable.IndexedSeq[T]]、withを使用T = Intします。これは、一般的なIndexedSeqビルダーに依存します。

toDigitFastタイプが暗黙の直接配列を使用しCanBuildFrom[Array[_], T, Array[T]]ます。これは間違いなく高速です。

次のCBFをtoDigit明示的に渡すと、2つのメソッドがパーになります。

object FastStringToArrayBuild {

  def canBuildFrom[T : ClassManifest] = new CanBuildFrom[String, T, Array[T]] {
    private def newBuilder = scala.collection.mutable.ArrayBuilder.make()
    def apply(from: String) = newBuilder
    def apply() = newBuilder
  }  

}
于 2012-05-21T12:13:47.700 に答える
2

あなたはメモリ不足にだまされています。このtoDigitバージョンでは、より多くの中間オブジェクトが作成されますが、十分なメモリがある場合、GCに大きな影響はありません（すべてが高速に実行されます）。たとえば、120万の数値を作成する代わりに、12k 100xを連続して作成すると、2つの方法でほぼ同じ回数が得られます。1.2kの5桁の数字を1000倍続けて作成すると、toDigit約5％高速になります。

このメソッドが不変toDigitのコレクションを生成することを考えると、推論が容易であるため、他のすべてが等しい場合に適しています。また、非常に要求の厳しいタスクを除くすべてのタスクで他のすべてが等しいことを考えると、ライブラリは本来あるべきものであると思います。

もちろん、パフォーマンスを向上させようとするときは、あらゆる種類のトリックを念頭に置く必要があります。これらの1つは、配列は、Scalaライブラリの派手なコレクションよりも、既知の長さのコレクションに対して優れたメモリ特性を備えていることです。また、地図は物事を成し遂げるための最速の方法ではないことを知っておく必要があります。これを本当に速くしたいのなら、

final def toDigitReallyFast(num: Int, accum: Long = 0L, iter: Int = 0): Array[Byte] = {
  if (num==0) {
    val ans = new Array[Byte](math.max(1,iter))
    var i = 0
    var ac = accum
    while (i < ans.length) {
      ans(ans.length-i-1) = (ac & 0xF).toByte
      ac >>= 4
      i += 1
    }
    ans
  }
  else {
    val next = num/10
    toDigitReallyFast(next, (accum << 4) | (num-10*next), iter+1)
  }
}

私のマシンでは、他のどのマシンよりも4倍高速です。そして、すべてをLongのままにして、次を使用する代わりに結果を配列にパックすると、さらにほぼ3倍速くなる可能性があります1 to N。

final def toDigitExtremelyFast(num: Int, accum: Long = 0L, iter: Int = 0): Long = {
  if (num==0) accum | (iter.toLong << 48)
  else {
    val next = num/10
    toDigitExtremelyFast(next, accum | ((num-10*next).toLong<<(4*iter)), iter+1)
  }
}

// loop, instead of 1 to N map, for the 1.2k number case
{ 
  var i = 10000
  val a = new Array[Long](1201)
  while (i<=11200) { 
    a(i-10000) = toDigitReallyReallyFast(i)
    i += 1
  }
  a
}

多くのことと同様に、パフォーマンスの調整は、正確に何をしたいかに大きく依存します。対照的に、ライブラリの設計では、さまざまな懸念事項のバランスを取る必要があります。ライブラリがパフォーマンスに関して最適ではないところに注目する価値があると思いますが、これは実際にはIMOのケースの1つではありません。一般的なユースケースでは、柔軟性はそれだけの価値があります。

于 2012-05-21T17:50:47.300 に答える