我已经编写了六个版本的length
函数。其中一些性能差异是有道理的,但有些似乎完全不符合我阅读过的文章(例如这篇和这篇)。
-- len1 and lenFold1 should have equivalent performance, right?
len1 :: [a] -> Integer
len1 [] = 0
len1 (x:xs) = len1 xs + 1
lenFold1 :: [a] -> Integer
lenFold1 = foldr (\_ a -> a + 1) 0
-- len2 and lenFold2 should have equivalent performance, right?
len2 :: [a] -> Integer
len2 xs = go xs 0 where
go [] acc = acc
go (x:xs) acc = go xs (1 + acc)
lenFold2 :: [a] -> Integer
lenFold2 = foldl (\a _ -> a + 1) 0
-- len3 and lenFold3 should have equivalent performance, right?
-- And len3 should outperform len1 and len2, right?
len3 :: [a] -> Integer
len3 xs = go xs 0 where
go [] acc = acc
go (x:xs) acc = go xs $! (1 + acc)
lenFold3 :: [a] -> Integer
lenFold3 = foldl' (\a _ -> a + 1) 0
我的机器实际性能令人困惑。
*Main Lib> :set +m +s
*Main Lib> xs = [1..10000000]
(0.01 secs, 351,256 bytes)
*Main Lib> len1 xs
10000000
(5.47 secs, 2,345,244,016 bytes)
*Main Lib> lenFold1 xs
10000000
(2.74 secs, 1,696,750,840 bytes)
*Main Lib> len2 xs
10000000
(6.02 secs, 2,980,997,432 bytes)
*Main Lib> lenFold2 xs
10000000
(3.97 secs, 1,776,750,816 bytes)
*Main Lib> len3 xs
10000000
(5.24 secs, 3,520,354,616 bytes)
*Main Lib> lenFold3 xs
10000000
(1.24 secs, 1,040,354,528 bytes)
*Main Lib> length xs
10000000
(0.21 secs, 720,354,480 bytes)
我的问题:
- 为什么每个函数的
fold
版本始终比使用显式递归的版本表现更出色? - 尽管这篇文章发出警告,但在我的计算机上,这些实现从未导致堆栈溢出。为什么?
- 为什么
len3
的性能不如len1
或len2
好? - 为什么Prelude中的
length
执行效果比这些实现都要好得多?
编辑:
感谢Carl的建议,我的第一个和第二个问题得到了解答,原因是GHCI默认解释代码。使用-fobject-code
再次运行程序可解释显式递归和fold之间的不同性能。新的测量结果如下:
Prelude Lib Main> xs = [1..10000000]
(0.00 secs, 354,136 bytes)
Prelude Lib Main> len1 xs
10000000
(1.62 secs, 1,612,661,544 bytes)
Prelude Lib Main> lenFold1 xs
10000000
(1.62 secs, 1,692,661,552 bytes)
Prelude Lib Main> len2 xs
10000000
(2.46 secs, 1,855,662,888 bytes)
Prelude Lib Main> lenFold2 xs
10000000
(2.53 secs, 1,772,661,528 bytes)
Prelude Lib Main> len3 xs
10000000
(0.48 secs, 1,680,361,272 bytes)
Prelude Lib Main> lenFold3 xs
10000000
(0.31 secs, 1,040,361,240 bytes)
Prelude Lib Main> length xs
10000000
(0.18 secs, 720,361,272 bytes)
我还有几个关于这个问题的疑问。
- 为什么
lenFold3
的性能优于len3
?我已经运行了几次。 length
如何仍然优于所有这些实现?
-fobject-code
再次运行它。”但还是感谢您的建议!更新测量数据。 - dan p-O2
进行编译,并使用类似 criterion 的工具进行测试。 - Thomas M. DuBuisson