为什么流折叠操作抛出内存异常？
我有以下简单的代码
def fib(i:Long,j:Long):Stream[Long] = i #:: fib(j, i+j)
(0l /: fib(1,1).take(10000000)) (_+_)并抛出OutOfMemmoryError异常。我不能理解为什么，因为我认为所有部分都使用常量内存，即惰性求值流和foldLeft……
这些代码也不能工作
fib(1,1).take(10000000).sum or max, min e.t.c.如何正确实现无限流并在其上进行迭代操作？
Scala版本: 2.9.0
scala javadoc还说，foldLeft操作对于流来说是内存安全的
/** Stream specialization of foldLeft which allows GC to collect
* along the way.
*/
@tailrec
override final def foldLeft[B](z: B)(op: (B, A) => B): B = {
if (this.isEmpty) z
else tail.foldLeft(op(z, head))(op)
}编辑：
使用迭代器的实现仍然没有用，因为它抛出了${domainName}异常
def fib(i:Long,j:Long): Iterator[Long] = Iterator(i) ++ fib(j, i + j)如何在Scala中正确定义无限流/迭代器？
EDIT2:我不关心int overflow，我只想了解如何在scala中创建无限的流/迭代器等，而不会产生副作用。
回答 5
Stack Overflow用户
发布于 2011-09-05 17:32:30
使用Stream而不是Iterator的原因是，您不必重复计算系列中的所有小项。但这意味着您需要存储一千万个流节点。不幸的是，这些内存非常大，因此可能足以溢出默认内存。克服这个问题的唯一现实的方法是从更多的内存开始(例如scala -J-Xmx2G)。(另外，请注意，您将使Long大量溢出；斐波那契数列增长非常快。)
附注:我心目中的迭代器实现完全不同；你不能用串联的单例Iterator来构建它：
def fib(i: Long, j: Long) = Iterator.iterate((i,j)){ case (a,b) => (b,a+b) }.map(_._1)现在，当您折叠时，可以丢弃过去的结果。
Stack Overflow用户
发布于 2011-09-05 18:58:22
OutOfMemoryError的发生与您使用Stream的事实无关。正如Rex Kerr上面提到的，Stream --与Iterator不同--将所有内容存储在内存中。List的不同之处在于Stream的元素是懒算的，但一旦达到10000000，就会有10000000个元素，就像List一样。
尝试使用new Array[Int](10000000)，您将遇到相同的问题。
要像上面那样计算斐波那契数，您可能想要使用不同的方法。您可以考虑这样一个事实，即您只需要两个数字，而不是到目前为止发现的整个fibonacci数字。
例如：
scala> def fib(i:Long,j:Long): Iterator[Long] = Iterator(i) ++ fib(j, i + j)
fib: (i: Long,j: Long)Iterator[Long]例如，为了得到第一个超过1000000的斐波纳契数的指数：
scala> fib(1, 1).indexWhere(_ > 1000000)
res12: Int = 30编辑:我添加了以下几行代码来处理StackOverflow
如果你真的想处理第一百万个斐波纳契数，上面的迭代器定义也不适用于StackOverflowError。以下是我目前最好的想法：
class FibIterator extends Iterator[BigDecimal] {
var i: BigDecimal = 1
var j: BigDecimal = 1
def next = {val temp = i
i = i + j
j = temp
j }
def hasNext = true
}
scala> new FibIterator().take(1000000).foldLeft(0:BigDecimal)(_ + _)
res49: BigDecimal = 82742358764415552005488531917024390424162251704439978804028473661823057748584031
0652444660067860068576582339667553466723534958196114093963106431270812950808725232290398073106383520
9370070837993419439389400053162345760603732435980206131237515815087375786729469542122086546698588361
1918333940290120089979292470743729680266332315132001038214604422938050077278662240891771323175496710
6543809955073045938575199742538064756142664237279428808177636434609546136862690895665103636058513818
5599492335097606599062280930533577747023889877591518250849190138449610994983754112730003192861138966
1418736269315695488126272680440194742866966916767696600932919528743675517065891097024715258730309025
7920682881137637647091134870921415447854373518256370737719553266719856028732647721347048627996967...Stack Overflow用户
发布于 2012-02-26 09:33:14
@yura的问题：
def fib(i:Long,j:Long):Stream[Long] = i #:: fib(j, i+j)
(0l /: fib(1,1).take(10000000)) (_+_)除了使用一个不可能容纳10,000,000的斐波纳契数的长整型，它确实可以工作。也就是说，如果foldLeft被写成：
fib(1,1).take(10000000).foldLeft(0L)(_+_)看一下Streams.scala源代码，foldLeft()显然是为垃圾收集而设计的，但是/:并没有定义。
其他答案暗示了另一个问题。1000万的斐波纳契数是一个很大的数字，如果使用BigInt，而不是像长的那样溢出，绝对巨大的数字会一次又一次地添加到每个数字上。
由于Stream.foldLeft针对GC进行了优化，因此它看起来确实像是解决非常大的斐波纳契数的方法，而不是使用压缩或尾递归。
// Fibonacci using BigInt
def fib(i:BigInt,j:BigInt):Stream[BigInt] = i #:: fib(j, i+j)
fib(1,0).take(10000000).foldLeft(BigInt("0"))(_+_)上述代码的结果: 10,000,000是一个8位数。fib(10000000)中有多少个数字？2,089,877
https://stackoverflow.com/questions/7306083
复制相似问题
腾讯云开发者
