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

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

4

2 回答 2

6

原来的

可能是因为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使用 aStringBuilder作为构建器：

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

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

String.valueOf调用在实例上Any使用 Java ，可能首先被装箱。这些额外的操作可能是速度差异的原因，而不是 Array 构建器的所谓较短的代码路径。Object.toStringChar

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

编辑

修改后，一般观点仍然存在，但我提到了错误的隐含，因为这些toDigit方法返回一个 Int 序列（或类似），而不是我误读的翻译字符串。

toDigit使用LowPriorityImplicits.fallbackStringCanBuildFrom[T]: CanBuildFrom[String, T, immutable.IndexedSeq[T]]， with T = Int，它只是遵循一般的 IndexedSeq 构建器。

toDigitFast使用 type 的直接 Array 隐式CanBuildFrom[Array[_], T, Array[T]]，这无疑是更快的。

显式传递以下 CBFtoDigit会使这两种方法相提并论：

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，则这两种方法的时间大致相等。如果我连续创建 1.2k 5 位数字 1000 倍，我发现这toDigit大约快 5%。

鉴于该toDigit方法产生了一个不可变的集合，当所有其他条件都相同时它会更好，因为它更容易推理，并且考虑到除高要求任务之外的所有其他条件都是相同的，我认为该库应该是它应该的样子。

在尝试提高性能时，当然需要牢记各种技巧；其中之一是对于已知长度的集合，数组具有比 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 的真正案例之一；对于常见的用例，灵活性是值得的。

于 2012-05-21T17:50:47.300 回答