scala – 减少大流量,无堆栈溢出

发布时间：2020-12-16 19:02:33 所属栏目：安全来源：网络整理

导读：1我试图做出一个无限制的阶乘函数(只是出于好奇心).这适用于大的n(尝试达到100000,似乎工作,虽然我无法检查输出值是否正确,因为,这是大的！) (BigInt(1) to n).reduceRight(_*_) 但是我恐怕整个BigInt(1)到n的范围都可能在内存中,而我只需要一个元素的reduce

1我试图做出一个无限制的阶乘函数(只是出于好奇心).这适用于大的n(尝试达到100000,似乎工作,虽然我无法检查输出值是否正确,因为,这是大的！)

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

但是我恐怕整个BigInt(1)到n的范围都可能在内存中,而我只需要一个元素的reduceRight元素.看看Scala的标准库代码,它看起来像BigInt(1),实际上输出整个范围而不是一个懒惰的流,但我发现Stream.range,我可以这样使用(注意n 1,流范围是排他的)

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

它适用于n = 10000(由于某些原因,它需要一点点更长！这让我认为也许正常范围实际上是一个流？)但是对于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)到n).reduceRight(_ * _)不溢出大n,几乎相同使用流…这里发生了什么？

解决方法

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所指出的那样,首先要乘以小数,这样会更快).

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!