scala - 为什么 Clojure 在递归添加函数上比 Scala 快得多？

Question

一位 friend 在 Clojure 中给了我这段代码片段

(defn sum [coll acc] (if (empty? coll) acc (recur (rest coll) (+ (first coll) acc))))
(time (sum (range 1 9999999) 0))

并问我它与类似的 Scala 实现相比如何。

我编写的 Scala 代码如下所示:

def from(n: Int): Stream[Int] = Stream.cons(n, from(n+1))
val ints = from(1).take(9999998)

def add(a: Stream[Int], b: Long): Long = {
    if (a.isEmpty) b else add(a.tail, b + a.head)
}

val t1 = System.currentTimeMillis()
println(add(ints, 0))
val t2 = System.currentTimeMillis()
println((t2 - t1).asInstanceOf[Float] + " msecs")

底线是:Clojure 中的代码在我的机器上运行大约 1.8 秒，使用的堆不到 5MB，Scala 中的代码运行大约 12 秒，512MB 的堆还不够(如果我设置堆到 1GB)。

所以我想知道为什么 Clojure 在这种特殊情况下会更快更 slim ？您是否有在速度和内存使用方面具有类似行为的 Scala 实现？

请不要发表宗教言论，我的兴趣主要在于找出在这种情况下是什么让 clojure 如此之快，以及在 scala 中是否有更快的算法实现。谢谢。

Answer 1

首先，Scala 只有在你使用 -optimise 调用它时才会优化尾调用。 . 编辑 : 如果可以的话，Scala 似乎总是会优化尾调用递归，即使没有 -optimise .

二、Stream和 Range是两个非常不同的东西。一个 Range有一个开始和一个结束，它的投影只有一个计数器和一个结束。一个 Stream是一个将按需计算的列表。由于您要添加整个 ints ，您将计算并因此分配整个 Stream .

更接近的代码是:

import scala.annotation.tailrec

def add(r: Range) = {
  @tailrec 
  def f(i: Iterator[Int], acc: Long): Long = 
    if (i.hasNext) f(i, acc + i.next) else acc

  f(r iterator, 0)
}

def time(f: => Unit) {
  val t1 = System.currentTimeMillis()
  f
  val t2 = System.currentTimeMillis()
  println((t2 - t1).asInstanceOf[Float]+" msecs")
}

正常运行:

scala> time(println(add(1 to 9999999)))
49999995000000
563.0 msecs

在 Scala 2.7 上，您需要“ elements ”而不是“ iterator ”，并且没有“ tailrec ”注解——该注解仅用于提示无法通过尾递归优化定义——所以您需要从代码中删除“ @tailrec”以及“ import scala.annotation.tailrec”。

此外，关于替代实现的一些注意事项。最简单的:

scala> time(println(1 to 9999999 reduceLeft (_+_)))
-2014260032
640.0 msecs

平均而言，这里有多次运行，它会更慢。这也是不正确的，因为它只适用于 Int。一个正确的:

scala> time(println((1 to 9999999 foldLeft 0L)(_+_)))
49999995000000
797.0 msecs

还是比较慢，跑这里。老实说，我没想到它会运行得更慢，但是每次交互都会调用正在传递的函数。一旦你考虑到这一点，与递归版本相比，这是一个相当不错的时机。