13

我尝试了一些快速实验，比较原生 Python 列表的性能与链表实现，例如this。

在不应该的情况下（根据理论），本机 Python 列表总是比非本机链表快。

from linkedlist import *
import time
a = LinkedList()
b = []
for i in range(1000000):
    b.append(i)
    a.add_first(i)
t0 = time.clock()
a.remove(10)
t1 = time.clock()
b.remove(10)
t2 = time.clock()
print t1-t0
print t2-t1

我在上面的测试中得到的结果是：

  • 本机链表 = 2.00000000001e-05

  • 蟒蛇列表= 0.005576

  • 非本地链表 = 3.90000000001e-05

所以，我想知道为什么 Python 没有原生的链表数据结构。在 Python 的情况下，在我看来，从算法上讲，使用链接列表而不是标准列表来加速标准库的某些方面可能很有用。

我的理解是，List 数据结构是该语言的关键构建块，它使代码更易于维护和优化，以专注于该数据结构。

还有其他原因吗？

4

2 回答 2

1

事实上，Python 没有本地链表实现，我也很想知道为什么。

您可能要考虑的一种替代方法是collections.deque(= "double-ended queue")，它在两端提供非常快速的恒定时间 O(1) 插入。实际上，对于您的具体示例，双端队列是比链表更好的选择，因为您不需要在中间插入。

但是，一般来说，重要的是要记住，双端队列是与​​链表不同的数据结构。链表还在中间提供恒定时间 O(1) 插入，而双端队列仅在中间提供线性时间 O(n) 插入。换句话说，在双端队列中间插入一个元素所花费的时间与双端队列的当前长度 n 成正比，对于足够大的 n，它会比使用链表慢。

collections.deque 和真正的链表之间的比较

在内部，collections.deque 实际上是使用链表实现的。然而，这是一个实现细节，更重要的是，它被实现为固定大小的元素块的链表，而不是单个元素的链表。

这就是为什么在 collections.deque 中间插入是 O(n) 而不是 O(1)：您仍然需要修改整个双端队列大约一半的内存以容纳新元素 N：

before inserting N: [ABCDE]⇄[FGHIJ]⇄[KLM__]
after inserting N:  [ABCDE]⇄[FGNHI]⇄[JKLM_]
changed memory:                ^^^   ^^^^

相反，对于一个真正的链表（= 单个元素），在中间插入一个新元素 N 只需分配一个新节点并更新四个指针的值，这是一个性能与当前大小无关的操作链表：

before inserting N: [A]⇄[B]⇄[C]⇄[D]⇄[E]⇄[F]⇄[G]⇄    [H]⇄[I]⇄[J]⇄[K]⇄[L]⇄[M]
after inserting N:  [A]⇄[B]⇄[C]⇄[D]⇄[E]⇄[F]⇄[G]⇄[N]⇄[H]⇄[I]⇄[J]⇄[K]⇄[L]⇄[M]
changed memory:                                ^ ^ ^

权衡是双端队列具有更好的内存局部性并且需要更少的独立内存分配。例如，在上面的双端队列中插入新元素 N 根本不需要任何新的内存分配。这就是为什么在实践中，特别是如果你经常在末端而不是中间插入，双端队列实际上是比链表更好的选择。

请注意，虽然在双端队列中间插入元素是 O(n)，但在开头或结尾插入新元素是 O(1)：

before:                [ABCDE]⇄[FGNHI]⇄[JKLM_]

prepending P:  [____P]⇄[ABCDE]⇄[FGNHI]⇄[JKLM_]
                    ^ ^

prepending Q:  [___QP]⇄[ABCDE]⇄[FGNHI]⇄[JKLM_]
                   ^

appending R:   [___QP]⇄[ABCDE]⇄[FGNHI]⇄[JKLMR]
                                            ^

appending S:   [___QP]⇄[ABCDE]⇄[FGNHI]⇄[JKLMR]⇄[S____]
                                              ^ ^

注意事项

当然，对于链表插入实际上是 O(1)，这假设您已经有一个h指向要插入新节点之前或之后的节点的句柄n。在 LinkedList 的假设实现中，这可能如下所示：

n = linkedlist.insertbefore(h, "some value")

在哪里：

type(h)     # => <class 'Node'>
type(n)     # => <class 'Node'>
n.value     # => "some value"
n.next == h # => True

如果你没有这样的句柄，那么类似的函数insert(i, x)仍然是 O(n)，因为找到第 i 个元素是 O(n)，即使插入操作本身是 O(1)。以下是insert(i, x)我们假设的 LinkedList 的一些假设实现：

def insert(self, i, x):
    node = self.node_from_index(i)       # Find the i-th node: O(n)
    return self.insertbefore(node, x)    # Insert and return new node: O(1)

这意味着当您确实保留这些节点句柄时，链表仅在某些问题上才值得。它还使 API 不太方便，尽管如果你小心的话，每个操作都是 O(1)，但常数通常要大得多。所以在实践中，它们并不是那么有用，这可能就是为什么它们不是 Python 中的内置链表。

于 2020-02-01T16:13:45.560 回答
-2

这只是因为构建列表需要大部分时间而不是附加方法。因此，当它不是您展示的线性时间操作时，（例如：n^2 操作）追加方法将比构建更重要，这将导致您想要看到的结果。

于 2017-04-29T04:17:03.050 回答