0

这是欧拉项目第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以查看它是否实际终止。

没有answeras a的原因lazy val是因为它的评估方式。length调用startingFromNumbers强制它评估一个值。何时val answers是严格的，整个计算startingFromNumbers发生在每次迭代中。对于像 100 这样的小值，这种低效率不会被注意到，但在较大的值下，每次迭代重新计算似乎会永远运行。使用lazy val answer结果startingFromNumbers被记忆以避免重复计算。因此，正如您发现和 Ryan 回答的那样，让他们都变得懒惰或让他们都变得严格。

减少问题会有所帮助，添加一个println(n)作为第一个调用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, ?)))

在第一个示例中，我们可以看到所有值都是在每次迭代时计算的。在第二个示例中，仅计算第一个值，其余的被延迟到需要时，即懒惰。如果 answer(i)._2使用 进行评估，toList我们可以看到与第一个示例中相同的数字。

于 2012-12-06T21:06:51.187 回答
0

我能够在 Scala 2.9.2 上重现该问题。但是，如果我将您的代码更改为使用 List[Int] 而不是 Stream[Int]，那么非惰性版本根本不会与 CPU 挂钩。

于 2012-12-06T18:35:16.167 回答