22

一位朋友在 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 在这种特殊情况下会更快更苗条？您是否有一个在速度和内存使用方面具有相似行为的 Scala 实现？

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

4

4 回答 4

37

首先，Scala 仅在您使用-optimise. 编辑：如果可以的话，Scala 似乎总是会优化尾调用递归，即使没有-optimise.

其次，Stream和Range是两个非常不同的东西。ARange有一个开始和一个结束，它的投影只有一个计数器和一个结束。AStream是一个将按需计算的列表。由于您要添加整体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

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

于 2009-08-31T20:20:09.403 回答
28

Clojure 的范围不会记忆，Scala 的 Stream 会。完全不同的数据结构具有完全不同的结果。Scala 确实有一个非记忆的 Range 结构，但目前以这种简单的递归方式使用它有点尴尬。这是我对整个事情的看法。

在较慢的旧机器上使用 Clojure 1.0，我得到 3.6 秒

user=> (defn sum [coll acc] (if (empty? coll) acc (recur (rest coll) (+ (first coll) acc))))
#'user/sum
user=> (time (sum (range 1 9999999) 0))
"Elapsed time: 3651.751139 msecs"
49999985000001

Scala 的直译需要我写一些代码

def time[T](x : => T) =  {
  val start = System.nanoTime : Double
  val result = x
  val duration = (System.nanoTime : Double) - start
  println("Elapsed time " + duration / 1000000.0 + " msecs")
  result
}

最好确保这是正确的

scala> time (Thread sleep 1000)
Elapsed time 1000.277967 msecs

现在我们需要一个与 Clojure 语义相似的非记忆范围

case class MyRange(start : Int, end : Int) {
  def isEmpty = start >= end
  def first = if (!isEmpty) start else error("empty range")
  def rest = new MyRange(start + 1, end)
}

从那个“添加”直接跟随

def add(a: MyRange, b: Long): Long = {
    if (a.isEmpty) b else add(a.rest, b + a.first)
}

它比 Clojure 在同一个盒子上的速度要快得多

scala> time(add(MyRange(1, 9999999), 0))
Elapsed time 252.526784 msecs
res1: Long = 49999985000001

使用 Scala 的标准库 Range，您可以进行折叠。它没有简单的原始递归那么快，但它的代码更少，并且仍然比 Clojure 递归版本快（至少在我的盒子上）。

scala> time((1 until 9999999 foldLeft 0L)(_ + _))
Elapsed time 1995.566127 msecs
res2: Long = 49999985000001

与记忆流上的折叠形成对比

time((Stream from 1 take 9999998 foldLeft 0L)(_ + _)) 
Elapsed time 3879.991318 msecs
res3: Long = 49999985000001
于 2009-08-31T20:53:46.560 回答
5

我怀疑这是由于 Clojure 如何处理尾缆优化。由于 JVM 本身并不执行此优化（Clojure 和 Scala 都在其上运行），因此 Clojure 通过recur关键字优化尾递归。从Clojure 网站：

在函数式语言中，循环和迭代是通过递归函数调用来替换/实现的。许多这样的语言保证在尾部位置进行的函数调用不会消耗堆栈空间，因此递归循环使用恒定空间。由于 Clojure 使用 Java 调用约定，它不能也不会做出相同的尾调用优化保证。相反，它提供了 recur 特殊运算符，该运算符通过重新绑定并跳转到最近的封闭循环或函数框架来执行恒定空间递归循环。虽然不像尾调用优化那样通用，但它允许大多数相同的优雅构造，并提供检查对 recur 的调用是否只能发生在尾部位置的优势。

编辑：Scala 也优化尾调用，只要它们采用某种形式。但是，正如前面的链接所示，Scala 只能在非常简单的情况下这样做：

事实上，这是 Scala 编译器的一个特性，称为尾调用优化。它优化了递归调用。不过，此功能仅适用于上述简单情况。例如，如果递归是间接的，则 Scala 无法优化尾调用，因为 JVM 指令集有限。

如果没有实际编译和反编译您的代码以查看生成的 JVM 指令，我怀疑这不是那些简单的情况之一（正如 Michael 所说，由于必须a.tail在每个递归步骤中获取），因此 Scala 无法优化它.

于 2009-08-31T19:07:52.920 回答
5

分析了你的这个例子，似乎这个类Stream（嗯......一些与之相关的匿名函数 - 因为visualvm在我身上崩溃而忘记了它的名字）占据了大部分堆。这与Scala 中的 s 确实泄漏内存的事实有关- 请参阅Scala Trac #692。修复将在 Scala 2.8 中到期。Stream. 编辑： Daniel的评论正确地指出它与这个错误无关。这是因为“val ints指向 Stream 头部，垃圾收集器无法收集任何东西” [丹尼尔]。我发现这个错误报告中关于这个问题的评论很好读。

在您的 add 函数中，您持有对 的引用a.head，因此垃圾收集器无法收集头部，导致最终包含 9999998 个元素的流，无法进行 GC-ed。

【一个小插曲】

你也可以保留你不断通过的尾巴的副本，我不知道如何Stream处理。如果您使用列表，则不会复制尾部。例如：

val xs =  List(1,2,3)
val ys = 1 :: xs
val zs = 2 :: xs

在这里，两者ys和zs“共享”相同的尾巴，至少在堆方面（ys.tail eq zs.tail，又名引用相等产生true）。

[这个小插曲是为了说明原则上传递很多尾巴并不是一件坏事:)，它们不会被复制，至少对于列表而言]

另一种实现（运行速度非常快，我认为它比纯函数式更清晰）是使用命令式方法：

def addTo(n: Int, init: Int): Long = {
  var sum = init.toLong
  for(i <- 1 to n) sum += i
  sum
}

scala> addTo(9999998, 0)

在 Scala 中，为了性能和清晰度，使用命令式方法是完全可以的（至少对我来说，这个版本的add意图更清楚）。为了更简洁，你甚至可以写

(1 to 9999998).reduceLeft(_ + _)

（运行有点慢，但仍然合理，不会炸毁内存）

我相信 Clojure 可能会更快，因为它功能齐全，因此可以进行比 Scala 更多的优化（它融合了函数式、OO 和命令式）。虽然我对 Clojure 不是很熟悉。

希望这可以帮助 ：）

于 2009-08-31T20:00:44.217 回答