4

我一直在 Haskell 中解决Project Euler #14一段时间，但由于某种原因，我无法让它工作。不久前我使用 Groovy 解决了这个问题，我想我在这里使用的方法基本相同。然而，即使只是找到前 10,000 个长度，程序运行速度也非常慢，我现在真的不知道为什么。我认为我正在使用记忆化，但即使 GHCI 中的数据集很小，我的内存也会用完。

到目前为止，这是我想出的。

collatz = (map collatz' [0..] !!)
    where collatz' n
        | n == 1 = 1
        | n `mod` 2 == 0 = 1 + collatz (n `div` 2)
        | otherwise = 1 +  collatz (3 * n + 1)

我会跑去map collatz [1..1000000]寻找问题的答案，但map collatz [1..10000]给了我一个内存不足的错误，并且还需要几秒钟才能完成运行。

如果有人能给我一些关于这个程序的问题的见解，那就太好了！我已经尝试了很多东西，但我只是卡住了，需要帮助。

谢谢！

4

1 回答 1

6

记忆在这里工作得很好。事实上，它运行得如此之好，以至于它填满了你所有的记忆。Collat​​z 序列的中间项变得相当大。1以up开头的任何序列中出现的最大项1000000是 number 2974984576。所以这是您尝试在内存中构建的列表的长度。

另一方面，直接实现 Collat​​z 函数而不进行记忆应该可以很好地解决这个问题。

于 2012-08-07T16:30:49.533 回答