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
而使用流几乎相同......这是怎么回事?
您是正确的,您的第一个解决方案将在内存中创建一个列表来存储反向序列。您可以简单地使用 reduceLeft
(在范围上没有这个问题),但它会以相反的方向通过范围。如果出于某种原因你想从大端开始,但保持reduceLeft
的懒惰,你可以创建一个向后Range
:
def fact(n: Int) = (BigInt(n) to 1 by -1).reduceLeft(_ * _)
可能还有其他方法可以轻松优化此功能。
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)
}
(正如特拉维斯指出的那样,先将小数字相乘会更快,这将需要额外的一行)。
尝试改用reduceLeft
。 reduceRight
从流的末尾开始,从而强制评估每个元素 - 这正是您想要避免的。
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
。