这个Haskell表达式为什么如此缓慢？

Question

我正在解决欧拉计划第14题，这是我的解决方案。

import Data.List

collatzLength :: Int->Int
collatzLength 1 = 1
collatzLength n | odd n = 1 + collatzLength (3 * n + 1)
                | even n = 1 + collatzLength (n `quot` 2)

maxTuple :: (Int, Int)->(Int, Int)->Ordering
maxTuple (x1, x2) (y1, y2)  | x1 > y1 = GT
                | x1 < y1 = LT
                | otherwise = EQ

我正在GHCi中运行以下内容

maximumBy maxTuple [(collatzLength x, x) | x <- [1..1000000]]

我知道如果Haskell采用严格求值，这个程序的时间复杂度应该是O(n³)。但是由于Haskell采用惰性求值，这个程序的时间复杂度似乎应该是n的某个常数倍数。然而，这个程序已经运行了将近一个小时了，这看起来非常不合理。有没有人知道为什么会这样呢？

- afkbowflexin

---

我不明白为什么 Haskell 的惰性计算会对这个算法的复杂度产生任何影响。 - sepp2k

你的函数 collatzLength 不是尾递归的。这会减慢函数的速度并导致不必要的分配。而你的 maxTuple 与 comparing fst 相同。 - fuz

@Josh 这确实可能是一个原因。如果我没记错，其他程序中也有这个问题，尽管我无法回忆起发生在哪里。 - fuz

是的，我没有认真考虑评估。我将collatzLength重写为尾递归，但仍然很慢。此外，我没有编译这个程序，似乎也没必要这么做。 - afkbowflexin

@Josh：将您的更新发布为一个新问题。这是一个与此主题无关的链接问题。 - hammar

Answer 1

你假设collatzLength函数将被记忆化，但Haskell不会自动记忆化。你需要自己实现这个功能。以下是使用data-memocombinators包的示例。

import Data.List
import Data.Ord
import qualified Data.MemoCombinators as Memo

collatzLength :: Integer -> Integer
collatzLength = Memo.arrayRange (1,1000000) collatzLength'
  where
    collatzLength' 1 = 1
    collatzLength' n | odd n  = 1 + collatzLength (3 * n + 1)
                     | even n = 1 + collatzLength (n `quot` 2)

main = print $ foldl1' max $ [(collatzLength n, n) | n <- [1..1000000]]

当使用-O2编译时，运行时间约为1秒。

- hammar

Answer 2

为了能够找到列表的最大值，整个列表都需要被评估。

因此，它将从1到1000000计算collatzLength，并且collatzLength是递归的。最糟糕的是，你对collatzLength的定义甚至不是尾递归的。

- Johannes Weiss

---

这个答案没有抓住重点。整个列表确实需要被评估，但通过记录（记忆化）collatzLength的结果，它可以被大大加速，正是因为它是递归定义的。我认为这是这个欧拉问题所要传达的智慧精华。 - Dan Burton

好的，但他问到了惰性求值。我告诉他，在这里使用惰性求值不会使它更快，因为所有东西都需要被评估（至少一次）。但你是对的！问题不在于一次性评估所有内容，而在于评估某些内容超过一次。 - Johannes Weiss

啊，现在我明白你的想法了。你也是正确的：整个列表需要被评估，因此懒惰并不能真正帮助；发帖者的困惑显然来自于没有清楚地理解惰性求值，假设其中包含了备忘录魔法，但实际上并没有。 - Dan Burton

是的，就是这样，我想是吧 :-). 他或许混淆了纯度和惰性？纯函数可能具有自动记忆化... - Johannes Weiss

Answer 3

cL 是 collatzLength 的缩写

cL!!n 表示 collatzLength n

cL :: [Int]
cL = 1 : 1 : [ 1 + (if odd n then cL!!(3*n+1) else cL!!(n `div` 2)) | n <- [2..]]

简单测试：

ghci> cL !! 13
10

- wenlong

---

基本上，这个程序使用了一个列表来记忆化collatzLength，同时在构建自身。但是当你尝试追踪执行顺序时，对于cL !! 3的执行依赖于列表中稍后会被计算的元素cL !! 10，这可能会让人感到非常困惑！ - Dan Burton

@Dan Burton，最糟糕的是它运行缓慢，可能是由于（！！）引起的。 - wenlong

是的，!! 将 O(n) 的时间复杂度加入算法的核心（相比之下，记忆化函数在调用时应该是 O(1) 或者在最坏情况下为 *O(log n)*），因此对于大的 n 值你一定会看到很明显的减速。 - Dan Burton