performance - 为什么 Scala for 循环在处理一系列不同对象时比 while 循环快得多？

Question

我最近读了一篇关于在一系列整数上的 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
  }
}

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

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

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

Answer 1

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

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