减少大流而不会出现堆栈溢出

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(在范围上没有那个问题),但是它会以相反的方向通过范围.如果由于某种原因你想从大端开始但保持懒惰reduceLeft,你可以创建一个向后Range:

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

您可以通过其他方式轻松优化此功能.

Answer 2

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

(正如特拉维斯指出的那样,首先乘以小数字会更快,这需要额外的一条线).