performance - Haskell Foldl' 性能不佳 (++)

Question

我有这个代码:

import Data.List

newList_bad  lst = foldl' (\acc x -> acc ++ [x*2]) [] lst
newList_good lst = foldl' (\acc x -> x*2 : acc) [] lst

这些函数返回每个元素乘以 2 的列表:

*Main> newList_bad [1..10]
[2,4,6,8,10,12,14,16,18,20]
*Main> newList_good [1..10]
[20,18,16,14,12,10,8,6,4,2]

在 ghci 中:

*Main> sum $ newList_bad [1..15000]
225015000
(5.24 secs, 4767099960 bytes)
*Main> sum $ newList_good [1..15000]
225015000
(0.03 secs, 3190716 bytes)

为什么newList_bad函数的运行速度比newList_good慢200倍？我知道这对于该任务来说不是一个好的解决方案。但为什么这个无辜的代码运行得这么慢？

这个“4767099960字节”是什么？？对于这个简单的操作，Haskell 使用了 4 GiB？

编译后:

C:\1>ghc -O --make test.hs
C:\1>test.exe
225015000
Time for sum (newList_bad [1..15000]) is 4.445889s
225015000
Time for sum (newList_good [1..15000]) is 0.0025005s

Answer 1

关于这个问题有很多困惑。通常给出的原因是“在列表末尾重复附加需要重复遍历列表，因此是O(n^2)”。但在严格评估下，事情才会这么简单。在惰性求值下，一切都应该被延迟，因此这就引出了一个问题:是否真的存在这些重复的遍历和附加。末尾的添加是由前面的消费触发的，并且由于我们在前面消费，列表变得越来越短，因此这些操作的确切时间还不清楚。因此，真正的答案更加微妙，并处理惰性求值下的具体缩减步骤。

直接的罪魁祸首是 foldl' 仅强制其累加器参数为弱头范式 - 即直到公开非严格构造函数为止。这里涉及到的函数有

(a:b)++c = a:(b++c)    -- does nothing with 'b', only pulls 'a' up
[]++c = c              -- so '++' only forces 1st elt from its left arg

foldl' f z [] = z
foldl' f z (x:xs) = let w=f z x in w `seq` foldl' f w xs

sum xs = sum_ xs 0     -- forces elts fom its arg one by one
sum_ [] a = a
sum_ (x:xs) a = sum_ xs (a+x)

因此实际的归约序列是(使用g = Foldl' f)

sum $ foldl' (\acc x-> acc++[x^2]) []          [a,b,c,d,e]
sum $ g  []                                    [a,b,c,d,e]
      g  [a^2]                                   [b,c,d,e]
      g  (a^2:([]++[b^2]))                         [c,d,e]
      g  (a^2:(([]++[b^2])++[c^2]))                  [d,e]
      g  (a^2:((([]++[b^2])++[c^2])++[d^2]))           [e]
      g  (a^2:(((([]++[b^2])++[c^2])++[d^2])++[e^2]))   []
sum $ (a^2:(((([]++[b^2])++[c^2])++[d^2])++[e^2]))

请注意，到目前为止我们只执行了 O(n) 步骤。 a^2 可立即用于 sum 的消耗，但 b^2 则不然。 我们只剩下 ++ 表达式的左嵌套结构。其余部分在 this answer by Daniel Fischer 中得到了最好的解释。 。其要点是，要获取 b^2 ，必须执行 O(n-1) 步骤 - 并且在该访问之后留下结构仍将是左嵌套的，因此下一次访问将采取 O(n-2) 步骤，依此类推 - 经典的 O(n^2) 行为。所以真正的原因是 ++ 没有强制或重新排列其参数以提高效率。

这实际上是违反直觉的。我们可以期望惰性求值能够神奇地为我们“做这件事”。毕竟，我们只是表达了将来将 [x^2] 添加到列表末尾的意图，我们实际上并没有立即执行此操作。所以这里的时机不对，但它可以是正确的 - 当我们访问列表时，如果时机正确，新元素将被添加到列表中并立即消耗: if c ^2 将被添加到列表中 b^2 之后(空间方面)，例如，就在(时间上)之前 b^2 将被消耗，遍历/访问将始终是 O(1)。

这是通过所谓的“差异列表”技术实现的:

newlist_dl lst = foldl' (\z x-> (z . (x^2 :)) ) id lst

如果您想一下，它看起来与您的 ++[x^2] 版本完全相同。它表达了相同的意图，并且也留下了左嵌套结构。

正如 Daniel Fischer 在同一答案中所解释的那样，区别在于(.) 链在第一次强制时，会重新排列自身 以 O(n) 步骤进入右嵌套 ($) 结构¹，之后每次访问是 O(1) 并且附加的时间是最佳的，正如上一段所述，因此我们剩下总体 O(n) 行为。

<小时/>

¹ 这有点神奇，但它确实发生了。 :)