performance - 带有惰性求值的差分列表的好处

Question

我很难理解为什么++被认为是 O(n) 而 differential lists被认为是“O(1)”。

如果是 ++让我们假设它被定义为:

(++) :: [a] -> [a] -> [a]
(a:as) ++ b = a:(as ++ b)
[]     ++ b = b

现在，如果我们需要在 a ++ b 中获取访问第一个元素我们可以在 O(1) 中做到这一点(假设 a 可以在 1 步中成为 HNF)，类似的第二步等等。它随着将多个列表设置附加到 Ω(1)/O(m) 而改变，其中 m 是未评估的附加物的数量。访问最后一个元素可以用 Θ(n + m) 完成，其中 n 是列表的长度，除非我遗漏了什么。如果我们有差分列表，我们也可以访问 Θ(m) 中的第一个元素，而最后一个元素在 Θ(n + m) 中。

我想念什么？

Answer 1

理论上的表现

O(1) 指的是 DLists 的 append 只是 (.)这需要一个减少，而 (++)是 O(n)。

最差的情况
++当您使用它重复添加到现有字符串的末尾时具有二次性能，因为每次添加另一个列表时都会遍历现有列表，因此

"Existing long ...... answer" ++ "newbit"

遍历 "Existing long ....... answer"每次添加一个新位时。

另一方面，

("Existing long ..... answer" ++ ) . ("newbit"++)

只会真正遍历 "Existing long ...... answer"一次，当函数链应用于 []转换为列表。

经验说

多年前，当我还是一个年轻的 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

所以它在实践和理论上都更快。