这个记忆化是否正常工作？

Question

我一直在使用Haskell解决Project Euler #14问题，但出现了问题，无法运行。之前我用Groovy解决过这个问题，我认为我在这里基本上使用了相同的方法。然而，即使只是找到前10000个长度，程序运行得非常慢，我真的很迷茫为什么会这样。我认为我正在正确地使用记忆化，但即使在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]会导致内存错误，并且需要运行很长时间才能完成。如果有人能给我一些关于这个程序问题的见解，那就太好了！我尝试了很多方法，但现在卡住了，需要帮助。谢谢！

- Benjamin Kovach

---

你尝试过编译运行它吗？ - huon

我刚刚试过了。使用 1..10000 这个数据集时，我没有遇到内存溢出错误，但是运行时间仍然相同。当我使用数据集 1..100000 时，我遇到了内存溢出错误，并且运行速度非常慢。 - Benjamin Kovach

使用列表进行记忆化对于这个问题来说不是一个好的选择。因为涉及到大量的索引，每个索引需要O(n)的时间。 - is7s

你可以尝试使用现有的记忆化库，比如MemoTrie。在Haskell维基的Memoization页面上可以找到许多相关的想法。 - Petr

此外，data-memocombinators 的使用非常简单，你的 collatz 可以变成 collatz = integral collatz' where {- ... -}。我可以在瞬间得到 map collatz [1..10000] 的结果。 - Vitus

Answer 1

备忘录算法在这里运行得非常好。实际上，它运行得非常好，以至于它填满了所有的内存。Collatz序列的中间项变得相当大。在任何以1开头的序列中出现的最大项是数字2974984576。因此，这就是您要在内存中构建的列表的长度。

另一方面，直接实现Collatz函数而不使用备忘录算法也可以很好地解决这个问题。

- kosmikus

---

同时，对于一些限制范围内的数字进行记忆化可能是可行的方法。 - Vitus

那其实很有道理。谢谢你！我想在Groovy中，我使用的是一个Map来做记忆化，而不是一个列表。尽管没有使用记忆化，但我目前使用的实现仍然很慢，所以我还需要找到另一种加速的方式，哈哈。 - Benjamin Kovach

我用 ghc -O2 进行了一些测试，结果发现没有记忆化的版本确实是最快的。记忆化前200000个数耗时6.09秒；完全没有记忆化耗时5.80秒；使用严格累加器的工作器包装器也只需5.41秒（注意，在所有测试中我使用了rem而不是mod）。测试使用了 maximum . map collatz $ [1..1000000]。 - Vitus

@Vitus 你使用的是 Integer 类型吧？如果你使用 Int 或者 Word 类型，只要类型足够大（使用 64 位 GHC 编译器），你可以将速度提高约 10 倍。如果使用 32 位编译器，则需要多次转换为 Integer 类型，这会降低速度。好的记忆化算法可以再次提高约 6 倍的速度。 - Daniel Fischer

@DanielFischer：是的，因为至少在我所知道的范围内，Windows上没有64位的GHC，所以我只是随意地加了Integer，并没有考虑更复杂的东西。看来我应该考虑到这一点，谢谢！ - Vitus

@Vitus 是的，还没有。我听说7.6版也将在Windows上有一个64位版本，但我不知道这是否可靠。无论如何，“Integer”是正确的类型，除非您想要看到它能推动多远，那么尽可能使用“Int”或“Word”。 - Daniel Fischer