Why does a flush operation throw an exception out of memory?

Question

I have a simple code

def fib(i:Long,j:Long):Stream[Long] = i #:: fib(j, i+j) (0l /: fib(1,1).take(10000000)) (_+_) 

And it throws an OutOfMemmoryError exception. I cannot understand why, because I think that all parts use constant memmory, i.e. lazy evaluation threads and foldLeft ...

This code also does not work.

 fib(1,1).take(10000000).sum or max, min etc 

How to correctly implement infinite streams and perform iterative operations on it?

Scala version: 2.9.0

Also scala javadoc said foldLeft operation is memmory safe for threads

  /** 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) } 

EDIT:

An iterator implementation is still not useful as it throws an exception $ $ domainName}

  def fib(i:Long,j:Long): Iterator[Long] = Iterator(i) ++ fib(j, i + j) 

How to correctly define an infinite stream / iterator in Scala?

EDIT2: I don't care about int overflow, I just want to understand how to create an infinite stream / iterator, etc. In scala, no side effects.

Answer 1

The reason you use Stream instead of Iterator is because you don't need to compute all the small members in the series again. But that means you need to store ten million stream nodes. Unfortunately, they are quite large, which may be enough for the default memory overflow. The only realistic way to overcome this is to start with more memory (e.g. scala -J-Xmx2G ). (Also note that you overwhelm Long with a huge margin; the Fibonacci series is growing very fast.)

PS The implementation of the iterator, which I mean, is completely different; you do not create it from Iterator s concatenated singlet:

 def fib(i: Long, j: Long) = Iterator.iterate((i,j)){ case (a,b) => (b,a+b) }.map(_._1) 

Now that you add up, past results can be discarded.

Answer 2

OutOfMemoryError occurs no matter what you use Stream. As Rex Kerr mentioned, Stream - unlike Iterator - stores everything in memory. The difference with List is that Stream elements are calculated lazily, but once you reach 10,000,000, there will be 10,000,000 elements, like List.

Try with new Array[Int](10000000) , you will have the same problem.

To calculate the fibonacci number as stated above, you can use a different approach. You can take into account the fact that you only need to have two numbers, and not all the fibonacci numbers found so far.

For instance:

 scala> def fib(i:Long,j:Long): Iterator[Long] = Iterator(i) ++ fib(j, i + j) fib: (i: Long,j: Long)Iterator[Long] 

And to get, for example, the index of the first Fibonacci number in excess of 1,000,000:

 scala> fib(1, 1).indexWhere(_ > 1000000) res12: Int = 30 

Edit: I added the following lines to handle StackOverflow

If you really want to work with the 1 millionth fibonacci number, the definition of the iterator above will not work for a StackOverflowError either. The following is the best that I have in mind at the moment:

  class FibIterator extends Iterator[BigDecimal] { var i: BigDecimal = 1 var j: BigDecimal = 1 def next = {val temp = ii = 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... 

Answer 3

@Yura problem:

 def fib(i:Long,j:Long):Stream[Long] = i #:: fib(j, i+j) (0l /: fib(1,1).take(10000000)) (_+_) 

In addition, using Long, which cannot hold Fibonacci at 10,000,000, it works. That is, if foldLeft is written as:

 fib(1,1).take(10000000).foldLeft(0L)(_+_) 

Looking at Streams.scala , foldLeft () is explicitly designed for the Garbage Collection, but /: is undefined.

Other answers refer to another problem. Fibonacci of 10 million is a large number, and if BigInt is used, instead of just overflowing like with Long, absolutely huge numbers are added to them again and again.

Since Stream.foldLeft optimized for GC, it really looks like a solution method for really large Fibonacci numbers, instead of using zip or tail recursion.

 // Fibonacci using BigInt def fib(i:BigInt,j:BigInt):Stream[BigInt] = i #:: fib(j, i+j) fib(1,0).take(10000000).foldLeft(BigInt("0"))(_+_) 

The results of the above code: 10,000,000 is an 8-digit number. How many digits are in fib (10,000,000)? 2,089,877

Answer 4

fib(1,1).take(10000000) is the " this " of the /: method, it is likely that the JVM will consider the link alive as long as this method is executed, even if in this case it can get rid of it, So that way, you keep a reference to the head of the stream all the time, therefore, to the whole stream when you create it for 10M elements.

Answer 5

You can just use recursion, which is about as simple:

 def fibSum(terms: Int, i: Long = 1, j: Long = 1, total: Long = 2): Long = { if (terms == 2) total else fibSum(terms - 1, j, i + j, total + i + j) } 

With this, you can “collapse” a billion elements in just a couple of seconds, but, as Rex points out, summing a sequence of Fibbonaci overflows Long very quickly.

If you really want to know the answer to your original problem and don’t mind sacrificing some accuracy, you can do this:

 def fibSum(terms: Int, i: Double = 1, j: Double = 1, tot: Double = 2, exp: Int = 0): String = { if (terms == 2) "%.6f".format(tot) + " E+" + exp else { val (i1, j1, tot1, exp1) = if (tot + i + j > 10) (i/10, j/10, tot/10, exp + 1) else (i, j, tot, exp) fibSum(terms - 1, j1, i1 + j1, tot1 + i1 + j1, exp1) } } scala> fibSum(10000000) res54: String = 2.957945 E+2089876