在编写 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 回退的方法映射到数组上的映射吗?为什么会有如此明显的差异? (请注意,增加数字甚至会导致非数组情况下的堆栈溢出)。
最佳答案
原装
可能是因为 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
}
}
关于string - toString.map 和 toString.toArray.map 的性能差异,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/10684356/