下面定义了两个函数来查找数字列表的最大值。
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 个元素的列表在性能上有如此巨大的差异吗?
最佳答案
正如其他人指出的那样,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
关于algorithm - 表现不佳的非尾递归函数的实例,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/26927372/