스택 오버플로없이 큰 스트림 줄이기

Question

1 제한이없는 계승 함수를 만들려고합니다. (호기심에서 벗어났습니다.)이 값은 대용량 인 n (최대 100000을 시도했는데 작동 할 수 있지만 작동하지 않습니다. 음, LARGE입니다 때문에! 정확성에 대한 출력 값을 확인)

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

하지만 난 그냥 reduceRight 위해 요소에 의해 그것을 요소를 필요로하는 동안은 전체 BigInt(1) to n 범위는 메모리에있을 수 있습니다 두려워 해요. BigInt(1) to n 실제로 전체 Range 아니라 게으른 Stream 출력하지만 난 이런 식으로 사용할 수 Stream.range을 발견 것 같습니다 스칼라의 표준 라이브러리의 코드를 살펴보고 촬영하면

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

합니다 (n+1 알, 스트림의 범위는 독점) 그것은 하지만 n=100000 내가이 스택 오버 플로우를 얻을 수 (저? 아마 정상 범위가 너무 실제로 Stream이라고 생각한다이 조금 더 걸리는 몇 가지 이유!에 대한) n=10000 작동

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

그리고 이렇게 스택 오버 플로우처럼 자신을 호출하는 것이 명백하다. 나는 tail-call을 최적화하지 않았다고 가정한다. 왜냐하면 tail-call은 값을 반환하기 전에 먼저 줄이거 나 동작하기 때문에 최적화되지 않는다. 그러면이 문제에 어떻게 접근 할 수 있습니까? 기능적 접근 방식을 배제하고 줄이기위한 맞춤형 명령형 코드를 목표로해야합니까?

매우 이상한 점은 큰 n에 대해 (BigInt(1) to n).reduceRight(_*_)이 오버플로하지 않는다는 것입니다. 스트림을 사용하면 거의 동일하지만 ... 여기 무슨 일이 있습니까?

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과 잘 작동합니다.