Zmniejszanie dużego strumienia bez przepełnienia stosu

Question

1Próbuję wykonać funkcję bez limitów silni (tylko z ciekawości). Działa to dla dużego n (próbowałem do 100000 i wydaje się działać, chociaż nie mogę sprawdzić wartość wyjściową dla poprawności, ponieważ dobrze, to duże!)

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

Ale obawiam się, że cała BigInt(1) to n zakres może być w pamięci, a po prostu trzeba to element po elemencie dla reduceRight. Przyjrzeniu standardowego kodu biblioteki Scala to wygląda BigInt(1) to n faktycznie wyprowadza cały Range a nie leniwy Stream ale znalazłem Stream.range których mogę użyć takiego (zawiadomienie n+1, zasięg strumienia jest wyłącznym)

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

To pracuje dla n=10000 (z jakiegoś powodu to zajmuje trochę dłużej! co sprawia, że ​​myślę, że może normalny zakres jest rzeczywiście Stream zbyt?), ale dla n=100000 uzyskać to przepełnienie stosu

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

To oczywiste, że reduceRight dzwoni sam jak ten

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

a zatem przepełnienia stosu. Zakładam, że nie jest to zoptymalizowany ogon, ponieważ najpierw zmniejsza, a następnie działa przed zwróceniem wartości, więc nie można go zoptymalizować. Jak więc mogę podejść do tego problemu? Czy powinienem zrezygnować z podejścia funkcjonalnego i dążyć do niestandardowego kodu stylu wymagającego ograniczenia?

Bardzo dziwne jest to, że (BigInt(1) to n).reduceRight(_*_) nie przepełnia się dla dużego n, podczas gdy prawie taki sam używa strumienia ... Co się tutaj dzieje?

Answer 1

reduceLeft jest zaimplementowany, aby obliczyć, jak dzieje się na strumieniach (i wywołuje w celu). Można sprawdzić w następujący sposób:

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

Albo można użyć rekurencji ogon:

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

(jak Travis zwraca uwagę, że to będzie szybciej pomnożyć małe liczby pierwsze, które podejmują dodatkowe linia).

Answer 2

Spróbuj użyć zamiast tego reduceLeft. reduceRight rozpoczyna się od końca strumienia, co zmusza każdy element do oceny - dokładnie to, czego chciałeś uniknąć.

Answer 3

Masz rację, że twoje pierwsze rozwiązanie will create a list in memory zachowuje odwróconą sekwencję. Możesz po prostu użyć reduceLeft (która nie ma tego problemu w zakresach), ale to przejdzie przez zakres w przeciwnym kierunku. Jeśli z jakiegoś powodu chcesz rozpocząć na dużą końcu jednak zachować lenistwo reduceLeft można utworzyć wstecz Range:

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

Nie może być other ways można łatwo zoptymalizować tę funkcję.

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) 

działa również z take(10000).toList.