Reducción de un flujo grande sin desbordamiento de pila

Question

1 Estoy tratando de hacer una función factorial sin límite (solo por curiosidad) Esto funciona para el gran n (probado hasta 100000 y parece funcionar, aunque no puedo comprobar el valor de salida para la corrección porque, bueno, es GRANDE!)

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

Pero me temo que toda la gama BigInt(1) to n podría estar en la memoria, mientras que yo sólo necesito elemento por elemento para reduceRight. Echando un vistazo a código de la biblioteca estándar de Scala parece que BigInt(1) to n productos realmente todo el Range y no un vago Stream pero me pareció Stream.range que puedo usar como esto (nota la n+1, rango de corriente es exclusiva)

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

Se que funciona para n=10000 (por alguna razón se necesita un poco más de tiempo! que me hace pensar que tal vez el rango normal es en realidad un Stream también?), pero para n=100000 consigo este desbordamiento de pila

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

Es obvio que reduceRight está llamando a sí mismo como esto

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

Y así el desbordamiento de pila. Supongo que no es una optimización de la cola porque primero se reduce y luego funciona antes de devolver el valor, por lo que no se puede optimizar. ¿Cómo podría abordar este problema entonces? ¿Debería abandonar el enfoque funcional y aspirar a un código personalizado de estilo imperativo para reducir?

Lo que me parece extraño es que el (BigInt(1) to n).reduceRight(_*_) no se desborda para el gran n, mientras que casi el mismo uso de una secuencia lo hace ... ¿Qué está pasando aquí?

Answer 1

reduceLeft se implementa para calcular a medida que avanza en las transmisiones (y llama en orden). Puede verificar la siguiente manera:

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

O puede utilizar la cola de recursión:

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

(como señala Travis, que sería más rápido para multiplicar los números pequeños en primer lugar, que tendría un extra línea).

Answer 2

Pruebe usar reduceLeft en su lugar. reduceRight comienza desde el final de la secuencia y obliga a que todos los elementos sean evaluados, exactamente lo que quería evitar.

Answer 3

Tiene razón en que su primera solución will create a list in memory almacena la secuencia invertida. Simplemente puede usar reduceLeft (que no tiene ese problema en los rangos), pero que pasará por el rango en la dirección opuesta. Si por alguna razón desea iniciar en el extremo grande pero mantener la pereza de reduceLeft, se puede crear un revés Range:

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

Puede haber other ways puede optimizar fácilmente esta función.

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) 

funciona bien con take(10000).toList también.