string - toString.map 和 toString.toArray.map 的性能差异

Question

在编写 Euler 问题时，我遇到了我认为很奇怪的事情:

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

不应该将 String 回退的方法映射到数组上的映射吗？为什么会有如此明显的差异？ (请注意，增加数字甚至会导致非数组情况下的堆栈溢出)。

Answer 1

原装

可能是因为 toString.map使用 WrappedString隐式，而 toString.toArray.map使用 WrappedArray隐式解析 map .

让我们看看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
}

WrappedString使用 StringBuilder作为 build 者:

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

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

String.valueOf调用 Any使用 Java Object.toString在 Char实例，可能首先被装箱。这些额外的操作可能是速度差异的原因，而 Array builder 的代码路径可能较短。

虽然这是一个猜测，但必须衡量。

编辑

修改后，大意依旧，但我提到了错误的隐含，因为 toDigit方法返回一个 Int 序列(或类似的)，而不是我误读的翻译字符串。
toDigit用途 LowPriorityImplicits.fallbackStringCanBuildFrom[T]: CanBuildFrom[String, T, immutable.IndexedSeq[T]] , 与 T = Int ，这只是遵循一般的 IndexedSeq 构建器。
toDigitFast使用类型为 CanBuildFrom[Array[_], T, Array[T]] 的直接数组隐式，这无疑更快。

为 toDigit 传递以下 CBF明确地使这两种方法相提并论:

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
  }  

}