为什么列表的连接需要 O(n)？

Question

根据 ADT（代数数据类型）理论，两个列表的连接必须采用 O(n)，其中 n 是第一个列表的长度。基本上，您必须递归地遍历第一个列表，直到找到结尾。

从不同的角度来看，可以说第二个列表可以简单地链接到第一个列表的最后一个元素。如果知道第一个列表的末尾，这将花费常数时间。

我在这里错过了什么？

Answer 1

为了连接两个列表（称它们为 xs 和 ys），我们需要修改 xs 中的最后一个节点以便 link 到（即指向）ys 的第一个节点。

但是 Haskell 列表是不可变的，因此我们必须先创建 xs 的副本。这个操作是O(n)（其中n是xs的长度）。

示例：

xs
|
v
1 -> 2 -> 3

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7
^              ^
|              |
xs ++ ys       ys

Answer 2

在操作上，Haskell 列表通常由指向单链表第一个单元格的指针（大致）表示。这样， tail 只是 returns 指向下一个单元格的指针（它不必复制任何东西），并且在列表前面使用 x : 分配一个新单元格，使其成为指向旧列表，returns 新指针。旧指针访问的列表没有变化，所以不需要复制。

如果您改为附加一个带有 ++ [x] 的值，则您不能通过更改其最后一个指针来修改原始喜欢的列表，除非您知道原始列表将永远不会被访问。更具体地说，考虑

x = [1..5]
n = length (x ++ [6]) + length x

如果在做x++[6]的时候修改x，n的值会变成12，这是错误的。最后一个x指的是长度为5的不变列表，所以n的结果一定是11。

实际上，您不能指望编译器对此进行优化，即使在不再使用 x 并且理论上可以就地更新的情况下（"linear"采用）。发生的事情是 x++[6] 的评估必须为之后重用 x 的最坏情况做好准备，因此它必须复制整个列表 x.

正如@Ben 所说，说 "the list is copied" 是不准确的。实际发生的是带有指针的单元格被复制（列表中所谓的 "spine"），但元素没有。例如，

x = [[1,2],[2,3]]
y = x ++ [[3,4]]

只需要分配[1,2],[2,3],[3,4]一次。列表的列表 x,y 将共享指向整数列表的指针，不必重复。

Answer 3

这是因为状态不可变。列表是一个对象+一个指针，所以如果我们把一个列表想象成一个元组，它可能看起来像这样：

let tupleList = ("a", ("b", ("c", [])))

现在让我们使用 "head" 函数获取此 "list" 中的第一项。这个 head 函数需要 O(1) 时间，因为我们可以使用 fst:

> fst tupleList

如果我们想用另一个替换列表中的第一项，我们可以这样做：

let tupleList2 = ("x",snd tupleList)

这也可以在 O(1) 中完成。为什么？因为列表中绝对没有其他元素存储对第一个条目的引用。由于状态不变，我们现在有两个列表，tupleList 和 tupleList2。当我们制作 tupleList2 时，我们没有复制整个列表。因为原始指针是不可变的，所以我们可以继续引用它们，但在列表的开头使用其他内容。

现在让我们尝试获取 3 项列表的最后一个元素：

> snd . snd $ fst tupleList

这发生在 O(3) 中，等于我们列表的长度，即 O(n)。

但是我们不能存储指向列表中最后一个元素的指针并在 O(1) 中访问它吗？为此，我们需要一个数组，而不是列表。数组允许任何元素的 O(1) 查找时间，因为它是在寄存器级别实现的原始数据结构。

(旁白：如果您不确定为什么我们要使用链表而不是数组，那么您应该多读一些关于数据结构、数据结构算法和各种操作的 Big-O 时间复杂度的信息，例如获取、轮询、插入、删除、排序等）。

现在我们已经确定了，让我们看看串联。让我们用新列表 ("e", ("f", [])) 连接 tupleList。为此，我们必须像获取最后一个元素一样遍历整个列表：

tupleList3 = (fst tupleList, (snd $ fst tupleList, (snd . snd $ fst tupleList, ("e", ("f", [])))

上面的操作实际上比O(n)时间更糟，因为对于列表中的每个元素我们都必须重新读取列表直到那个索引。但是如果我们暂时忽略它并关注关键方面：为了到达列表中的最后一个元素，我们必须遍历整个结构。

您可能会问，为什么我们不直接在内存中存储最后一个列表项是什么？这样追加到列表的末尾将在 O(1) 中完成。但是没那么快，我们不能在不改变整个列表的情况下改变最后一个列表项。为什么？

让我们来看看它的外观：

data Queue a = Queue { last :: Queue a, head :: a, next :: Queue a} | Empty
appendEnd :: a -> Queue a -> Queue a
appendEnd a2 (Queue l, h, n) = ????

如果我修改 "last"，这是一个不可变变量，我实际上不会修改队列中最后一项的指针。我将创建最后一项的副本。引用原始项目的所有其他内容将继续引用原始项目。

因此，为了更新队列中的最后一项，我必须更新所有引用它的内容。这只能在最佳 O(n) 时间内完成。

所以在我们的传统列表中，我们有最后一项：

List a []

但是如果我们想改变它，我们就复制它。现在倒数第二个项目引用了旧版本。所以我们需要更新那个项目。

List a (List a [])

但是如果我们更新倒数第二个项目，我们会复制它。现在倒数第三个项目有一个旧的参考。所以我们需要更新它。重复直到我们到达列表的头部。我们绕了一圈。没有任何内容保留对列表头部的引用，因此需要 O(1) 的编辑。

这就是 Haskell 没有双向链表的原因。这也是为什么 "Queue"（或者至少是 FIFO 队列）不能以传统方式实现的原因。在 Haskell 中创建队列需要对传统数据结构进行认真的重新思考。

如果您对所有这些工作原理更加好奇，请考虑购买这本书 Purely Funtional Data Structures。

编辑：如果你曾经看过这个：http://visualgo.net/list.html 你可能会注意到在可视化中 "Insert Tail" 发生在 O(1) 中。但是为了做到这一点，我们需要修改列表中的最后一个条目，给它一个新的指针。更新指针会改变状态，这在纯函数式语言中是不允许的。希望我的 post.

的其余部分已经明确了这一点

Answer 4

您要问的与我之前为 TCS Stackexchange 写的一个问题有关：支持功能列表的恒定时间连接的数据结构是 difference list.

不久前，Yasuhiko Minamide in the 90s; I effectively rediscovered it 提出了一种用函数式编程语言处理此类列表的方法。然而，良好的运行时间保证需要 Haskell.

中不可用的语言级支持

为什么列表的连接需要 O(n)？

Why does concatenation of lists take O(n)?

complexity-theory

haskell

functional-programming

algebraic-data-types