performance - 为什么差异列表比 Haskell 中的常规串联更有效？

Question

我目前正在通过 Learn you a Haskell 工作在线预订，并且已经来到了作者解释某些列表连接可能效率低下的章节:例如

((((a ++ b) ++ c) ++ d) ++ e) ++ f

据说效率低下。作者提出的解决方案是使用定义为的“差异列表”

newtype DiffList a = DiffList {getDiffList :: [a] -> [a] }

instance Monoid (DiffList a) where
    mempty = DiffList (\xs -> [] ++ xs)
    (DiffList f) `mappend` (DiffList g) = DiffList (\xs -> f (g xs))

我很难理解为什么 DiffList在某些情况下，比简单的串联在计算上更有效。有人可以简单地向我解释一下为什么上面的例子效率如此低下，以及 DiffList 的方式如何？解决这个问题？

Answer 1

问题在

((((a ++ b) ++ c) ++ d) ++ e) ++ f

是嵌套。 (++)的应用是左嵌套的，这很糟糕；右嵌套

a ++ (b ++ (c ++ (d ++ (e ++f))))

不会有问题。那是因为(++)被定义为

[] ++ ys = ys
(x:xs) ++ ys = x : (xs ++ ys)

所以要找到要使用的方程，实现必须深入到表达式树中

             (++)
             /  \
          (++)   f
          /  \
       (++)   e
       /  \
    (++)   d
    /  \
 (++)   c
 /  \
a    b

直到它发现左操作数是否为空。如果它不是空的，它的头部被取出并冒泡到顶部，但左操作数的尾部保持不变，因此当需要连接的下一个元素时，相同的过程再次开始。

当串联右嵌套时，(++) 的左操作数总是在顶部，检查头部是否空虚/冒泡是 O(1)。

但是当串联是左嵌套时，n层深，到达第一个元素，n对于结果的每个元素(来自第一个列表，n-1 来自第二个等等)，必须遍历树的节点。

让我们考虑一下 a = "hello"在

hi = ((((a ++ b) ++ c) ++ d) ++ e) ++ f

我们要评估 take 5 hi .所以首先必须检查是否

(((a ++ b) ++ c) ++ d) ++ e

是空的。为此，必须检查是否

((a ++ b) ++ c) ++ d

是空的。为此，必须检查是否

(a ++ b) ++ c

是空的。为此，必须检查是否

a ++ b

是空的。为此，必须检查是否

a

是空的。呼。不是，所以我们可以再次冒泡，组装

a ++ b                             = 'h':("ello" ++ b)
(a ++ b) ++ c                      = 'h':(("ello" ++ b) ++ c)
((a ++ b) ++ c) ++ d               = 'h':((("ello" ++ b) ++ c) ++ d)
(((a ++ b) ++ c) ++ d) ++ e        = 'h':(((("ello" ++ b) ++ c) ++ d) ++ e)
((((a ++ b) ++ c) ++ d) ++ e) ++ f = 'h':((((("ello" ++ b) ++ c) ++ d) ++ e) ++ f)

和 'e' ，我们必须重复，对于 'l'也是...

绘制树的一部分，冒泡是这样的:

            (++)
            /  \
         (++)   c
         /  \
'h':"ello"   b

成为第一

     (++)
     /  \
   (:)   c
  /   \
'h'   (++)
      /  \
 "ello"   b

进而

      (:)
      / \
    'h' (++)
        /  \
     (++)   c
     /  \
"ello"   b

一路回到顶端。成为顶层右子树的结构(:)最后，与原始树的结构完全相同，除非最左边的列表为空，当

 (++)
 /  \
[]   b

节点折叠为仅 b .

因此，如果您有短列表的左嵌套串联，则串联变为二次的，因为获得串联的头部是一个 O(嵌套深度)操作。一般来说，左嵌套的串联

(...((a_d ++ a_{d-1}) ++ a_{d-2}) ...) ++ a_2) ++ a_1

是 O(sum [i * length a_i | i <- [1 .. d]])来全面评估。

使用差异列表(为了简化说明而没有新型包装器)，组合是否左嵌套并不重要

((((a ++) . (b ++)) . (c ++)) . (d ++)) . (e ++)

或右嵌套。一旦您穿过嵌套到达 (a ++) ，那 (++)被提升到表达式树的顶部，因此获取 a 的每个元素又是 O(1)。

事实上，只要你需要第一个元素，整个组合就会与差异列表重新关联，

((((a ++) . (b ++)) . (c ++)) . (d ++)) . (e ++) $ f

变成

((((a ++) . (b ++)) . (c ++)) . (d ++)) $ (e ++) f
(((a ++) . (b ++)) . (c ++)) $ (d ++) ((e ++) f)
((a ++) . (b ++)) $ (c ++) ((d ++) ((e ++) f))
(a ++) $ (b ++) ((c ++) ((d ++) ((e ++) f)))
a ++ (b ++ (c ++ (d ++ (e ++ f))))

之后，每个列表都是顶级 (++) 的直接左操作数在前面的列表被消费之后。

重要的是，前置函数 (a ++)可以在不检查其参数的情况下开始产生其结果，以便从

             ($)
             / \
           (.)  f
           / \
         (.) (e ++)
         / \
       (.) (d ++)
       / \
     (.) (c ++)
     / \
(a ++) (b ++)

通过

           ($)---------
           /           \
         (.)           ($)
         / \           / \
       (.) (d ++) (e ++)  f
       / \
     (.) (c ++)
     / \
(a ++) (b ++)

到

     ($)
     / \
(a ++) ($)
       / \
  (b ++) ($)
         / \
    (c ++) ($)
           / \
      (d ++) ($)
             / \
        (e ++)  f

不需要知道关于最终列表的组合函数的任何信息 f ，所以它只是一个 O(depth)重写。然后是顶级

     ($)
     / \
(a ++)  stuff

变成

 (++)
 /  \
a    stuff

以及 a 的所有元素可以一步获得。在这个例子中，我们有纯左嵌套，只需要重写一次。如果而不是(例如)(d ++)那个地方的函数是一个左嵌套的组合，(((g ++) . (h ++)) . (i ++)) . (j ++) ，顶级重新关联将保持不变，当它成为顶级 ($) 的左操作数时，它将重新关联。在之前的所有列表都被消耗掉之后。

所有重新关联所需的总工作为 O(number of lists) ，因此串联的总成本为 O(number of lists + sum (map length lists)) . (这意味着您也可以通过插入大量左嵌套 ([] ++) 来为此带来糟糕的性能。)

这

newtype DiffList a = DiffList {getDiffList :: [a] -> [a] }

instance Monoid (DiffList a) where
    mempty = DiffList (\xs -> [] ++ xs)
    (DiffList f) `mappend` (DiffList g) = DiffList (\xs -> f (g xs))

只是将其包装起来，以便抽象处理更方便。

DiffList (a ++) `mappend` DiffList (b ++) ~> DiffList ((a ++) . (b++))

请注意，如果任意函数包装在 DiffList 中，则它仅对不需要检查其参数即可开始生成输出的函数有效。 s，你没有这样的效率保证。特别是，追加( (++ a) ，无论是否包裹)可以创建 (++) 的左嵌套树当组合成右嵌套时，您可以创建 O(n²)如果 DiffList 的连接行为构造函数被暴露。