我在这个页面上工作
http://www.haskell.org/haskellwiki/99_questions/Solutions/4
我理解每个函数的含义,看到一个函数可以像这样以多种方式定义,这很有趣。但是,我刚开始想知道哪个更快。我认为它会是 length
中的 Prelude
。
length [] = 0
length (x:xs) = 1 + length xs
但是,这比
length
中的 Prelude
慢得多。在我的计算机上,
length
中的 Prelude
在 0.37 秒内返回 [1..10^7]
的长度。然而,上面定义的函数需要 15.26 秒。我定义了自己的长度函数,它使用了累加器。只用了 8.99 秒。
我想知道为什么会出现这些巨大的差异?
最佳答案
当您说“length
中的 Prelude
返回 ... 在 0.37 秒内”时,您指的是哪个编译器?如果您正在使用 GHC,您可以看到,例如 here 实际实现与简单的不同
length [] = 0
length (x:xs) = 1 + length xs
即,它是:
length l = len l 0#
where
len :: [a] -> Int# -> Int
len [] a# = I# a#
len (_:xs) a# = len xs (a# +# 1#)
此代码使用累加器,并通过使用未装箱的整数避免了巨大的未评估 thunk 的问题,即此版本是高度优化的。
为了说明“简单”版本的问题,请考虑如何评估
length [1, 2, 3]
:length [1, 2, 3]
=> 1 + length [2, 3]
=> 1 + (1 + length [3])
=> 1 + (1 + (1 + length []))
=> 1 + (1 + (1 + 0))
直到真正需要它的结果时才会评估总和,因此您看到当输入是一个巨大的列表时,您将首先在内存中创建一个巨大的总和,然后仅在真正需要其结果时才对其进行评估。
相比之下,优化版本的评估如下:
length [1, 2, 3]
=> len [1, 2, 3] 0#
=> len [2, 3] (1#)
=> len [3] (2#)
=> len [] (3#)
=> 3
即“+1”立即完成。
关于Haskell 编写 myLength,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16205086/