0

これは、euler プロジェクトの問題 14 の解決策です。

しかし奇妙なことに、val answer が遅延として宣言されていない場合、このプログラムは終了しません。val が遅延している間、解決策は数​​秒で生成されます。それがなければ、Java VM は長時間 (おそらく永遠に) 100% の CPU 使用率になります。

package euler

object Problem14 {
//Which starting number, under one million, produces the longest chain?

    def startingNumbersFrom(n: Long): Stream[Long] = {
        if (n == 1) 
            Stream(1)
        else if (n % 2 == 0)
            n #:: startingNumbersFrom(n/2)
        else
            n #:: startingNumbersFrom(3*n+1)
    }

            //This has to be lazy for program to terminate
    lazy val answer = (
        for (n <- 1 to 1000000) yield 
        (n, startingNumbersFrom(n).length)
    ).maxBy(x=> x._2)._1


    def main(args: Array[String]) = {
        println(answer)
    }
}

直感的に、コンパニオン オブジェクトが init/tear down ループに巻き込まれていると推測できますが、なぜそうなるのかは明らかではありません。

4

2 に答える 2

1

プログラムは で終了しますval answer = ...が、そうなる前にリソースが不足する可能性があります。実際に終了することを確認する1000000ために、より小さな数に変更します。100

理由はそのままじゃないとうまくいかないanswer、というlazy valのが評価の仕方だからです。のlength呼び出しは、startingFromNumbers強制的に値に評価されます。厳密な場合は、各反復でval answersの計算全体が発生します。startingFromNumbers100 のような小さな値では、この非効率性は見過ごされますが、大きな値では、反復ごとに再計算が永久に実行されるように見えます。lazy val answer結果を使用すると、startingFromNumbers計算の繰り返しを避けるためにメモ化されます。したがって、あなたが発見し、ライアンが答えたように、両方を怠惰にするか、両方を厳密にします。

問題を軽減しprintln(n)、最初の呼び出しとしてa を追加すると、startingFromNumbersこれを視覚化するのに役立ちます。

scala> val answer = (for (n <- 1 to 3) yield (n, startingNumbersFrom(n).length))
1
2
1
3
10
5
16
8
4
2
1
answer: scala.collection.immutable.IndexedSeq[(Int, Int)] = Vector((1,1), (2,2), (3,8))

scala> val answer = (for (n <- 1 to 3) yield (n, startingNumbersFrom(n)))
1
2
3
answer: scala.collection.immutable.IndexedSeq[(Int, Stream[Long])] = Vector((1,Stream(1, ?)), (2,Stream(2, ?)), (3,Stream(3, ?)))

最初の例では、反復ごとにすべての値が計算されていることがわかります。2 番目の例では、最初の値のみが計算され、残りは必要になるまで遅延されます。answer(i)._2を で評価するとtoList、最初の例と同じ数値が表示されます。

于 2012-12-06T21:06:51.187 に答える
0

Scala 2.9.2 で問題を再現できました。ただし、Stream[Int] の代わりに List[Int] を使用するようにコードを変更すると、非遅延バージョンは CPU をまったくペグしません。

于 2012-12-06T18:35:16.167 に答える