为什么在处理一系列不同对象时，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.toArray转换上面定义的seq），这种情况似乎不会发生。在这种情况下，for循环需要90毫秒，而while循环只需要40毫秒。

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

- Kat

Answer 1

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

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

- sjrd

---

seq.size 是 List 的一个更大的开销。 - som-snytt

@sjrd，编译器不应该处理这样的错误吗？ - axiom

简短回答：不，编译器不能使你避免完全错误的复杂度类！长答案需要一个完整的问题来回答，而且甚至无法适应SO的格式（开放式问题，不是具体的编程问题等）。 - sjrd

@sjrd 我的意思是 seq.size 只是一个 O(n) 的调用。如果编译器足够聪明，可以将此调用优化掉（如果尚未发生），则代码的复杂度将保持为 O(n)。 - axiom

代码的复杂度仍然是O(n^2)，因为seq(i)本身就是O(n)。此外，编译器不知道seq.size永远不会改变，所以它无法将其从循环中提取出来。 - sjrd