这个备忘录是否正常工作？

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

Memoization在这里工作得很好.事实上,它运作良好,它填补了你的所有记忆.Collat​​z序列的中间术语变得非常大.发生在任何序列开始规模最大的一届1最多1000000是多少2974984576.所以这是您尝试在内存中构建的列表的长度.

另一方面,只是直接实现没有记忆的Collat​​z功能应该可以解决这个问题.