为什么 Scala 的 for 循环比处理不同对象序列的 while 循环快得多？

Question

我最近读到 post 一篇关于运行ge 整数的 for 循环比相应的 while 循环慢的文章，这是真的，但我想看看是否同样适用于迭代在现有序列上，惊讶地发现完全相反的结果。

首先，我使用以下函数进行计时：

def time[A](f: => A) = {
    val s = System.nanoTime
    val ret = f
    println("time: " + (System.nanoTime - s) / 1e6 + "ms")
    ret
}

我正在使用一个简单的整数序列：

val seq = List.range(0, 10000)

（我还尝试通过其他几种方式创建此序列，以防访问此序列的方式影响运行时间。使用 Range 类型肯定会影响。这应该确保每个项目在序列中是一个独立的对象。）

我运行以下：

time {
  for(item <- seq) {
    println(item)
  }
}

和

time {
  var i = 0
  while(i < seq.size) {
    println(seq(i))
    i += 1
  }
}

我打印了结果，以确保我们实际上访问了两个循环中的值。第一个代码片段运行s 在我的机器上平均 33 ms。第二个平均需要 305 毫秒.

我尝试将可变变量 i 添加到 for 循环中，但它只增加了几毫秒。正如预期的那样，map 函数获得与 for 循环相似的性能。无论出于何种原因，如果我使用数组（将上面定义的 seq 转换为 seq.toArray），这似乎不会发生。在这种情况下，for 循环需要 90 毫秒，而 while 循环需要 40 毫秒。

造成这种主要性能差异的原因是什么？

Answer 1

原因是：复杂性。 seq(i) 是 List 的 Θ(i)，这意味着您的整个循环需要二次方时间。然而，foreach 方法是线性的。

如果使用 -optimize 编译，for 循环版本可能会更快，因为 List.foreach 应该是内联的，消除了 lambda 的成本。

为什么 Scala 的 for 循环比处理不同对象序列的 while 循环快得多？

Why are Scala for loops so much faster than while loops for processing a sequence of distinct objects?

performance

scala