该memoization是否正常工作？

Question

我已经在Haskell致力于解决Project Euler #14有一段时间了，但由于某些原因，我无法让它工作。不久前我使用Groovy解决了这个问题，我想我在这里使用的基本上是相同的方法。然而，即使只找到前10,000个长度，程序的运行速度也令人难以置信地慢，我现在真的不知道为什么。我认为我使用memoization是正确的，但即使在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]会给我一个内存不足的错误，而且也需要几秒钟才能完成运行。

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

谢谢!

Answer 1

记忆化在这里运行得很好。事实上，它工作得如此之好，以至于它填满了你所有的记忆。Collatz序列的中间项变得相当大。从1开始直到1000000的任何序列中出现的最大项是数字2974984576。这就是你试图在内存中构建的列表的长度。

另一方面，直接实现Collatz函数而不使用memoization应该可以很好地解决这个问题。