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功能比它慢200倍newList_good？我知道这不是一个很好的解决方案.但为什么这个无辜的代码工作得如此之慢？

这是什么"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事实并非如此.我们留下了左嵌套的++表达式结构.Daniel Fischer在这个答案中最好地解释了其余部分.它的要点是,要b^2离开,O(n-1)必须执行步骤 - 并且在此访问之后留下的结构仍然是左嵌套的,因此下一次访问将采取O(n-2)步骤,依此类推 - 经典O(n^2)行为.所以真正的原因是++ 没有强制或重新安排其论点足以提高效率.

这实际上是违反直觉的.我们可以期待懒惰的评估在这里为我们神奇地"做".毕竟我们只表达了将来添加[x^2]到列表末尾的意图,我们实际上并没有立即这样做.因此,这里的时间是关闭的,但它可以做出正确的-就像我们访问列表,新元素将被添加到它,并消耗马上,如果时机是正确的:如果将被添加到后面的列表(空间明智),比如说,在消耗之前(时间),遍历/访问将始终如此.c^2b^2 b^2O(1)

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

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

如果你想到这一点,它看起来和你的++[x^2]版本完全一样.它表达了相同的意图,并且也留下了左嵌套结构.

的差,如在由Daniel费相同答案解释的那样,是一个(.)链中,当第一强制,本身重新排列成右嵌套($)结构¹中O(n)的步骤,在此之后的每个接入是O(1)与如上述appendings的定时正是最佳上面的段落,所以我们留下了整体O(n)行为.

¹这是一种神奇的,但确实发生了.:)

Answer 2

经典列表行为.

召回:

(:)  -- O(1) complexity
(++) -- O(n) complexity

所以你创建了一个O(n ^ 2)算法,而不是O(n)算法.

对于递增附加到列表的常见情况,请尝试使用dlist,或者只是在结尾处反向.