我很难想象为什么被认为是O(n)而 differential lists被认为是“O(1)”. 如果我们假设它被定义为： (++) :: [a] - [a] - [a](a:as) ++ b = a:(as ++ b)[] ++ b = b 现在,如果我们需要获取ab中的访问第一个元素
如果我们假设它被定义为：
(++) :: [a] -> [a] -> [a] (a:as) ++ b = a:(as ++ b) [] ++ b = b
现在,如果我们需要获取ab中的访问第一个元素,我们可以在O(1)中进行(假设a可以在1步中成为HNF),类似于第二个等.它随着附加多个列表设置为Ω而变化(1) )/ O(m),其中m是未评估附加物的数量.访问最后一个元素可以用Θ(n m)完成,其中n是列表的长度,除非我遗漏了一些东西.如果我们有差分列表,我们也可以访问Θ(m)中的第一个元素,而最后一个元素是Θ(n m).
我错过了什么？
理论上的表现O(1)指的是DLists的附加只是(.),其中一个减少,wheras()是O(n).
最糟糕的情况
当您使用它重复添加到现有字符串的末尾时具有二次性能,因为每次添加另一个列表时,您都会迭代现有列表,因此
"Existing long ...... answer" ++ "newbit"
每次追加一个新位时,遍历“现有长…….回答”.
另一方面,
("Existing long ..... answer" ++ ) . ("newbit"++)
当函数链应用于[]转换为列表时,只会实际遍历“现有长……回答”一次.
经验说
多年前,当我还是一个年轻的Haskeller时,我写了一个程序,正在寻找一个猜测的反例,所以一直在向磁盘输出数据,直到我停止它,除了一旦我取下测试制动器,它输出的确没有任何东西,因为我的左关联尾部递归构建一个字符串,我意识到我的程序不够懒惰 – 它不能输出任何东西,直到它附加了最后的字符串,但没有最后的字符串！我推出了自己的DList(这是在编写DList库的那个之前的千禧年),并且我的程序运行得非常漂亮,愉快地在服务器上制作了大量的非反例,直到我们放弃了该项目.
如果你有足够大的例子,你可以看到性能差异,但对于小的有限输出并不重要.它确实教会了我懒惰的好处.
玩具示例
愚蠢的例子来证明我的观点：
plenty f = f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f.f
alot f = plenty f.plenty f.plenty f
让我们做两种追加,首先是DList方式
compose f = f . ("..and some more.."++)
append xs = xs ++ "..and some more.."
insufficiently_lazy = alot append []
sufficiently_lazy = alot compose id []
得到：
ghci> head $sufficiently_lazy '.' (0.02 secs, 0 bytes) ghci> head $insufficiently_lazy '.' (0.02 secs, 518652 bytes)
和
ghci> insufficiently_lazy
-- (much output skipped)
..and some more....and some more....and some more.."
(0.73 secs, 61171508 bytes)
ghci> sufficiently_lazy
-- (much output skipped)
..and some more....and some more....and some more.."
(0.31 secs, 4673640 bytes).
-- less than a tenth the space and half the time
所以它在实践和理论上都更快.