9

n1制限のない階乗関数を作成しようとしています(単なる好奇心からです)。大きい！）

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

しかし、範囲全体BigInt(1) to nがメモリ内にある可能性があるのではないかと心配していますが、reduceRight. Scala の標準ライブラリ コードを見ると、実際には遅延ではなくBigInt(1) to n全体を出力しているように見えますが、このように使用できるものを見つけました (ストリーム範囲は排他的であることに注意してください)。RangeStreamStream.rangen+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 に答える