Riduzione di un flusso di grandi dimensioni senza sovraccarico dello stack

Question

1 Sto cercando di realizzare una funzione fattoriale priva di limiti (solo per curiosità.) Funziona per il grande n (provato fino a 100000 e sembra funzionare, anche se non posso controllare il valore di output per la correttezza, perché, beh, è ​​GRANDE!)

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

Ma temo che tutta la gamma BigInt(1) to n potrebbe essere in memoria, mentre ho solo bisogno elemento per elemento per reduceRight. Dando uno sguardo al codice di libreria standard di Scala sembra BigInt(1) to n uscite effettivamente la totalità Range e non un pigro Stream ma ho trovato Stream.range che posso usare come questo (notare la n+1, gamma stream è esclusiva)

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

E ' funziona per n=10000 (per qualche ragione ci vuole un po 'più a lungo! che mi fa pensare che forse il range di normalità è in realtà un Stream troppo?), ma per n=100000 ottengo questo overflow dello stack

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

E 'ovvio che reduceRight si sta chiamando come questo

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

E così l'overflow dello stack. Presumo che non sia ottimizzato il tail-call perché prima riduce e poi opera prima di restituire il valore, quindi non può essere ottimizzato. Come potrei affrontare questo problema allora? Devo abbandonare l'approccio funzionale e puntare a un codice personalizzato in stile imperativo da ridurre?

Ciò che mi colpisce è una cosa molto strana è che il (BigInt(1) to n).reduceRight(_*_) non ha un overflow per il grande n mentre quasi lo stesso usando un flusso non ... Cosa sta succedendo qui?

Answer 1

reduceLeft viene implementato per calcolare mentre procede su flussi (e chiama in ordine). È possibile verificare come segue:

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

Oppure si può usare la ricorsione in coda:

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

(come sottolinea Travis, sarebbe più veloce di moltiplicare i piccoli numeri primi, che richiederebbe un extra linea).

Answer 2

Provare a utilizzare reduceLeft invece. reduceRight inizia dalla fine dello stream e quindi impone la valutazione di ogni elemento, esattamente ciò che si desidera evitare.

Answer 3

È corretto che la prima soluzione will create a list in memory memorizzi la sequenza inversa. Potresti semplicemente usare reduceLeft (che non ha questo problema sugli intervalli), ma che passerà attraverso l'intervallo nella direzione opposta. Se per qualche ragione si vuole iniziare alla grande fine, ma mantenere la pigrizia di reduceLeft, è possibile creare un all'indietro Range:

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

Ci possono essere other ways è possibile ottimizzare facilmente questa funzione.

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) 

funziona anche con take(10000).toList.