为什么差异列表比常规连接更有效？

Question

我目前正在通过在线学习你的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's也是如此......

绘制树的一部分,冒泡起来像这样:

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

成为第一

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

然后

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

一直回到顶端.最终成为顶级子项的(:)树的结构与原始树的结构完全相同,除非最左边的列表为空,当

 (++)
 /  \
[]   b

节点折叠为just 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++))

请注意,它只对那些不需要检查其参数以开始生成输出的函数有效,如果任意函数包含在DiffLists中,则没有这样的效率保证.特别是,附加((++ a),包装或不包装)可以(++)在组合右嵌套时创建左嵌套树,因此O(n²)如果DiffList构造器被公开,您可以使用该树创建连接行为.

Answer 2

查看串联的定义可能会有所帮助:

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

正如您所看到的,为了连接两个列表,您需要查看左侧列表并创建它的"副本",这样您就可以更改它的结尾(这是因为您无法直接更改旧的结尾)列表,由于不变性).

如果以正确的关联方式进行连接,则没有问题.插入后,永远不必再次触摸列表(请注意++的定义如何从不检查右侧的列表),因此每个列表元素仅插入"一次",总时间为O(N).

--This is O(n)
(a ++ (b ++ (c ++ (d ++ (e ++ f)))))

但是,如果以左关联方式进行连接,则每次向末尾添加另一个列表片段时,"当前"列表必须"拆除"并"重建".每个列表元素将在迭代时迭代它被插入,并且每当未来的片段被添加时!如果你连续多次调用strcat,就像你在C中遇到的问题一样.

至于差异列表,诀窍在于它们最后会保留一个明确的"漏洞".当您将DList转换回普通列表时,您可以将它传递给您想要在洞中的内容,并且它已准备就绪.另一方面,正常列表总是插入最后的洞,[]所以如果你想改变它(连接时),那么你需要翻开列表才能到达那一点.

带有函数的差异列表的定义起初可能看起来很吓人,但实际上它非常简单.你可以从面向对象的角度来看它们,将它们视为不透明对象"toList"方法,它接收你应该在最后一个洞中插入的列表,返回DL的内部前缀加上提供的尾部.这是有效率的,因为在完成所有转换后,您只会在最后插入"漏洞".