9

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而使用流几乎相同......这里发生了什么？

4

4 回答 4

8

您是正确的，您的第一个解决方案将在内存中创建一个列表来存储相反的序列。您可以简单地使用reduceLeft（在范围上没有这个问题），但这将通过相反方向的范围。如果出于某种原因你想从大端开始但保持 的懒惰reduceLeft，你可以创建一个倒退Range：

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

您可能还有其他方法可以轻松优化此功能。

于 2012-04-19T14:58:27.903 回答
7

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

（正如 Travis 指出的那样，首先将小数相乘会更快，这将需要额外的一行）。

于 2012-04-19T14:53:09.313 回答
4

尝试reduceLeft改用。reduceRight从流的末尾开始，因此强制评估每个元素——这正是你想要避免的。

于 2012-04-19T14:53:18.830 回答
1 
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。

于 2012-04-19T15:05:39.243 回答