Scala 中斐波那契流中的 OutOfMemoryError

Question

当我这样定义 fib 时 (1):

def fib(n: Int) = {
  lazy val fibs: Stream[BigInt] = 0 #:: 1 #:: fibs.zip(fibs.tail).map{n => n._1 + n._2}
  fibs.drop(n).head
}

我得到一个错误：

scala> fib(1000000)
java.lang.OutOfMemoryError: Java heap space

另一方面，这工作正常 (2)：

def fib = {
  lazy val fibs: Stream[BigInt] = 0 #:: 1 #:: fibs.zip(fibs.tail).map{n => n._1 + n._2}
  fibs
}

scala> fib.drop(1000000).head
res17: BigInt = 195328212...

此外，如果我按以下方式更改流定义，我可以在函数内调用 drop(n).head 并且也不会出现任何错误 (3):

def fib(n: Int) = {
  lazy val fibs: (BigInt, BigInt) => Stream[BigInt] = (a, b) => a #:: fibs(b, a+b)
  fibs(0, 1).drop(n).head
}

scala> fib(1000000)
res18: BigInt = 195328212...

能否解释一下（1）、（2）、（3）的相关区别？为什么 (2) 有效，而 (1) 无效？为什么我们不需要将 drop(n).head 移出 (3) 中的函数？

Answer 1

在第一种情况下，在计算元素编号 n 时存在对 fibs 流开头的引用 - 因此从 0 到 1000000 的所有值都必须保存在内存中。这是OutOfMemoryError.

的来源

在第二种情况下，对流开头的引用不会在任何地方保留，因此项目可以被垃圾收集（一次只需要在内存中保留一个项目）。

在第三种情况下，对流开头的引用不存在于任何地方（它可以在删除下一个值时被垃圾收集）。但是，如果我们将其更改为：

def fib(n: Int) = {
  lazy val fibs: (BigInt, BigInt) => Stream[BigInt] = (a, b) => a #:: fibs(b, a+b)
  val beg = fibs(0, 1)
  beg.drop(n).head
}

然后OutOfMemoryError又会出现

Scala 中斐波那契流中的 OutOfMemoryError

OutOfMemoryError in a Fibonacci stream in Scala

functional-programming

scala

stream

fibonacci