Scala斐波那契流中的OutOfMemoryError

Question

当我像这样定义fib时:

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

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

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

在第三种情况下，对流开始的引用没有显式存在(当next值被丢弃时，它可以被垃圾收集)。但是如果我们把它改成:

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将再次出现