Уменьшение большого потока без переполнения стека

Question

1 Я пытаюсь сделать факториальную функцию без ограничения (только из любопытства.) Это работает для больших n (проверено до 100000 и кажется, что работает, хотя я не могу проверьте выходное значение для правильности, потому что, ну, это БОЛЬШОЕ!)

(BigInt(1) to n).reduceRight(_*_) 

Но я боюсь, что все BigInt(1) to n диапазона может быть в памяти, в то время как мне просто нужно его поэлементен для reduceRight. Взглянув на стандартном коде библиотеки в Scala он выглядит BigInt(1) to n фактически выводит весь Range и не ленивый Stream, но я нашел Stream.range, которые я могу использовать, как это (обратите внимание n+1, диапазон потока эксклюзивна)

Stream.range[BigInt](BigInt(1), BigInt(n+1)).reduceRight(_*_) 

Это работает n=10000 (по какой-то причине она занимает немного больше времени!, который заставляет меня думать, что, может быть, нормальный диапазон на самом деле Stream тоже?), но для n=100000 я получаю это переполнение стека

java.lang.StackOverflowError 
    at java.math.BigInteger.add(Unknown Source) 
    at scala.math.BigInt.$plus(BigInt.scala:161) 
    at scala.math.Numeric$BigIntIsIntegral$class.plus(Numeric.scala:28) 
    at scala.math.Numeric$BigIntIsIntegral$.plus(Numeric.scala:40) 
    at scala.math.Numeric$BigIntIsIntegral$.plus(Numeric.scala:40) 
    at scala.math.Numeric$Ops.$plus(Numeric.scala:208) 
    at scala.collection.immutable.Stream$$anonfun$range$1.apply(Stream.scala:695) 
    at scala.collection.immutable.Stream$$anonfun$range$1.apply(Stream.scala:695) 
    at scala.collection.immutable.Stream$Cons.tail(Stream.scala:634) 
    at scala.collection.immutable.Stream$Cons.tail(Stream.scala:626) 
    at scala.collection.LinearSeqOptimized$class.reduceRight(LinearSeqOptimized.scala:130) 
    at scala.collection.immutable.Stream.reduceRight(Stream.scala:47) 
    at scala.collection.LinearSeqOptimized$class.reduceRight(LinearSeqOptimized.scala:131) 
    at scala.collection.immutable.Stream.reduceRight(Stream.scala:47) 
    at scala.collection.LinearSeqOptimized$class.reduceRight(LinearSeqOptimized.scala:131) 
    at scala.collection.immutable.Stream.reduceRight(Stream.scala:47) 
    ... 

Очевидно, что reduceRight называет себя, как этот

reduceRight(reduceRight(first, second, op), third, op)... 

И, таким образом, переполнение стека. Я предполагаю, что это не оптимизация хвоста, потому что он сначала уменьшает, а затем работает до возврата значения, поэтому его нельзя оптимизировать. Как я могу подойти к этой проблеме? Должен ли я отказаться от функционального подхода и стремиться к сокращению пользовательского кода императивного стиля?

Что мне кажется очень странным, так это то, что (BigInt(1) to n).reduceRight(_*_) не переполняется для больших n, в то время как почти то же самое с использованием потока ... Что здесь происходит?

Answer 1

reduceLeft реализован для вычисления, когда он идет по потокам (и он вызывает в порядке). Вы можете проверить следующим образом:

Stream.range(1,10).map(i => print(i)).reduceLeft((a,b) => println("r")) 

Или вы можете использовать хвостовую рекурсию:

final def fac(n: BigInt, prod: BigInt = BigInt(1)): BigInt = { 
    if (n<2) prod else fac(n-1,prod*n) 
} 

(а Трэвис указывает, что было бы быстрее, чтобы умножить небольшое число первых, которые будут принимать дополнительные линия).

Answer 2

Попробуйте вместо этого использовать reduceLeft. reduceRight начинается с конца потока и, таким образом, заставляет каждый элемент оцениваться - именно то, чего вы хотели избежать.

Answer 3

Вы правы, что ваше первое решение will create a list in memory для хранения обратной последовательности. Вы можете просто использовать reduceLeft (который не имеет этой проблемы на диапазонах), но это пройдет через диапазон в противоположном направлении. Если по какой-то причине вы хотите, чтобы начать на тупом конце, но сохранить леность reduceLeft, вы можете создать назад Range:

def fact(n: Int) = (BigInt(n) to 1 by -1).reduceLeft(_ * _) 

Там может быть other ways вы можете легко оптимизировать эту функцию.

Answer 4

def fac (n: BigInt=1, m:BigInt=1): Stream[BigInt] = 
    Stream.cons (n, fac (n * m, m+1)) 

fac().take (10).toList 
res27: List[BigInt] = List(1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880) 

хорошо работает с take(10000).toList тоже.