algorithm - 表现不佳的非尾递归函数的实例

Question

下面定义了两个函数来查找数字列表的最大值。

mx :: (Ord a) => [a] -> a
mx [] = error "Empty list"
mx [x] = x
mx (x:xs) 
    | x > (mx xs) = x
    | otherwise = (mx xs)

mx' (x:xs) = findMax x xs
  where
    findMax cmx [] = cmx
    findMax cmx (x:xs) | x > cmx = findMax x xs
               | otherwise = findMax cmx xs

main = do 
    print $ mx [1..30]

为上面的代码计时，首先是 mx'(尾递归)，然后是 mx(非尾递归)，我们有以下计时。

Lenovo-IdeaPad-Y510P:/tmp$ time ./t 
30

real    0m0.002s
user    0m0.000s
sys 0m0.001s
Lenovo-IdeaPad-Y510P:/tmp$ ghc -O2 t.hs
[1 of 1] Compiling Main             ( t.hs, t.o )
Linking t ...
Lenovo-IdeaPad-Y510P:/tmp$ time ./t 
30

real    0m6.272s
user    0m6.274s
sys 0m0.000s

有人可以解释为什么只有 30 个元素的列表在性能上有如此巨大的差异吗？

Answer 1

正如其他人指出的那样，GHC 不执行公共(public)子表达式消除 (CSE)，导致您的第一个代码段以指数时间运行。

要了解原因，请考虑例如

test1 = length [1..1000] + sum [1..1000]
test2 = let l = [1..1000] in length l + sum l

这两个示例在语义上是等价的，但是 test1 在 constant space 中运行，而test2 线性空间(分配了整个 1000 个单元格)。基本上，在这种情况下 CSE否定了懒惰的优势。

由于 CSE 会导致更差的性能，因此 GHC 在应用它时相当保守。

GHC 常见问题解答中的更多解释:

https://www.haskell.org/haskellwiki/GHC/FAQ#Does_GHC_do_common_subexpression_elimination.3F