Python 中的双端队列是如何实现的，它们什么时候比列表更糟糕？

Question

我最近开始研究如何在 Python 中实现各种数据结构，以便使我的代码更加高效。在研究列表和双端队列如何工作时，我发现当我想要移动和取消移动时，我可以获得好处，将列表中的 O(n) 时间减少到双端队列中的 O(1) （列表被实现为固定长度数组，这些数组具有每次在前面插入某些内容时都会完全复制，等等...）。我似乎找不到双端队列如何实现的细节，以及它与列表相比的缺点的细节。有人可以帮我解答这两个问题吗？

Answer 1

https://github.com/python/cpython/blob/v3 .8.1/Modules/_collectionsmodule.c

dequeobject 由block 节点的双向链表组成。

所以是的，正如另一个答案所暗示的那样，双端队列是一个（双向）链表。

详细说明：这意味着 Python 列表更适合随机访问和固定长度操作（包括切片），而双端队列对于从末尾推送和弹出内容更有用，索引（有趣的是，但不包括切片）可能，但比列表慢。

Answer 2

查看 collections.deque。来自文档：

双端队列支持线程安全、内存
高效的追加和弹出
双端队列的一侧大约有
相同的 O(1) 性能
方向。

虽然列表对象支持类似
操作，它们针对
快速固定长度操作并产生
pop(0) 的 O(n) 内存移动成本
和 insert(0, v) 操作
改变大小和位置
底层数据表示。

正如它所说，使用 pop(0) 或 insert(0, v) 会对列表对象造成很大的损失。您不能在 deque 上使用切片/索引操作，但可以使用 popleft/appendleft，它们是操作 deque< /code> 已针对以下内容进行了优化。这是一个简单的基准测试来证明这一点：

import time
from collections import deque

num = 100000

def append(c):
    for i in range(num):
        c.append(i)

def appendleft(c):
    if isinstance(c, deque):
        for i in range(num):
            c.appendleft(i)
    else:
        for i in range(num):
            c.insert(0, i)
def pop(c):
    for i in range(num):
        c.pop()

def popleft(c):
    if isinstance(c, deque):
        for i in range(num):
            c.popleft()
    else:
        for i in range(num):
            c.pop(0)

for container in [deque, list]:
    for operation in [append, appendleft, pop, popleft]:
        c = container(range(num))
        start = time.time()
        operation(c)
        elapsed = time.time() - start
        print "Completed %s/%s in %.2f seconds: %.1f ops/sec" % (container.__name__, operation.__name__, elapsed, num / elapsed)

我的机器上的结果：

Completed deque/append in 0.02 seconds: 5582877.2 ops/sec
Completed deque/appendleft in 0.02 seconds: 6406549.7 ops/sec
Completed deque/pop in 0.01 seconds: 7146417.7 ops/sec
Completed deque/popleft in 0.01 seconds: 7271174.0 ops/sec
Completed list/append in 0.01 seconds: 6761407.6 ops/sec
Completed list/appendleft in 16.55 seconds: 6042.7 ops/sec
Completed list/pop in 0.02 seconds: 4394057.9 ops/sec
Completed list/popleft in 3.23 seconds: 30983.3 ops/sec

Answer 3

deque 对象 的文档条目阐明了我怀疑你需要知道的大部分内容。值得注意的引言：

双端队列支持线程安全、内存高效的从双端队列的任意一侧追加和弹出，在任一方向上具有大致相同的 O(1) 性能。

但...

索引访问在两端都是 O(1)，但在中间减慢为 O(n)。为了快速随机访问，请使用列表。

我必须查看源代码才能判断该实现是链表还是其他东西，但在我看来，deque 与双向链接具有大致相同的特征列表。

Answer 4

除了所有其他有用的答案之外，这里还有一些比较时间复杂度的更多信息（Big-哦）Python 列表、双端队列、集合和字典上的各种操作。这应该有助于为特定问题选择正确的数据结构。