Почему операция складывания потока вызывает исключение "Недостаточно памяти"?

Question

У меня следующий простой код

 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

Также в javaadoc сказано, что операция 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)
  }

EDIT:

Реализация с итераторами по-прежнему бесполезна, поскольку она вызывает исключение $ {domainName}

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

Как правильно определить бесконечный поток / итератор в Scala?

EDIT2:Меня не волнует переполнение int, я просто хочу понять, как создать бесконечный поток / итератор и т. Д. В scala без побочных эффектов.

Answer 1

Причина использования Stream вместо Iterator заключается в том, что вам не нужно снова вычислять все маленькие члены в серии. Но это означает, что вам нужно хранить десять миллионов потоковых узлов. К сожалению, они довольно большие, поэтому их может быть достаточно для переполнения памяти по умолчанию. Единственный реальный способ преодолеть это - начать с увеличения памяти (например, scala -J-Xmx2G). (Также обратите внимание, что вы собираетесь переполнить Long с огромным запасом; ряд Фибоначчи довольно быстро увеличивается.)

P.S. Реализация итератора, которую я имею в виду, совершенно другая; вы не строите его из сцепленного синглтона Iterator s:

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

Теперь, когда вы сбросите карты, прошлые результаты могут быть отброшены.

Answer 2

@ проблема Юры:

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 () явно предназначен для сборки мусора, но /: не является определением'd.

В других ответах упоминается другая проблема.Число Фибоначчи в 10 миллионов - это большое число, и если используется BigInt, вместо того, чтобы просто переполняться, как с помощью Long, к каждому снова и снова добавляются абсолютно огромные числа.

Так как Stream.foldLeft оптимизирован дляGC выглядит как способ найти действительно большие числа Фибоначчи, а не использовать рекурсию по zip или хвосту.

// 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-значное число.Сколько цифр в фибе (10000000)? 2 089 877

Answer 3

Ошибка OutOfMemoryError происходит независимо от того, что вы используете Stream. Как упоминал Рекс Керр, Stream, в отличие от Iterator, хранит все в памяти. Разница с List в том, что элементы Stream рассчитываются лениво, но как только вы достигнете 10000000, будет 10000000 элементов, как и List.

Попробуйте с new Array[Int](10000000), у вас будет такая же проблема.

Для вычисления числа Фибоначчи, как указано выше, вы можете использовать другой подход. Вы можете принять во внимание тот факт, что вам нужно иметь только два числа вместо целых чисел Фибоначчи, открытых до сих пор.

Например:

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

Если вы действительно хотите работать с 1-миллионным числом Фибоначчи, приведенное выше определение итератора также не будет работать для 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...

Answer 4

Вы можете просто использовать рекурсию, что примерно так просто:

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

При этом вы можете «сложить» миллиард элементов всего за пару секунд, но, как указывает Рекс, суммирование последовательности Фиббоначи очень быстро переполняет Long.

Если вы действительно хотели узнать ответ на свою первоначальную задачу и не отказались от некоторой точности, вы можете сделать это:

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

Answer 5

fib(1,1).take(10000000) - это "this" метода /:, вполне вероятно, что JVM будет считать ссылку действующей до тех пор, пока метод работает, даже если в этом случае он может избавиться от него , Таким образом, вы сохраняете ссылку на начало потока, следовательно, на весь поток, когда вы создаете его для элементов 10M.