Python中的双端队列是如何实现的？它们何时不如列表？

Question

我最近开始研究在Python中各种数据结构是怎么实现的，目的是让我的代码更高效。在研究列表和双端队列（deque）的时候，我发现当我想要在前面添加或删除元素时，使用双端队列可以把时间从O(n)减少到O(1)。这是因为列表是用固定长度的数组实现的，每次在前面插入东西时都需要把整个数组复制一遍等等。不过，我找不到双端队列具体是怎么实现的，也不清楚它相对于列表的缺点是什么。有没有人能帮我解答这两个问题？

Answer 1

关于deque对象的文档里，应该有你需要知道的大部分内容。这里有几个重要的点：

双端队列（deques）支持线程安全，并且在内存使用上很高效，可以从两端快速添加和删除元素，性能大约都是O(1)，也就是无论从哪一边操作，速度都差不多。

但是……

如果你想随机访问某个元素，双端队列的两端访问是O(1)，但在中间访问就变成O(n)，也就是速度会慢很多。如果你需要快速随机访问，建议使用列表。

我得看看具体的实现才能判断它是用链表还是其他方式，但听起来deque的特点和双向链表差不多。

Answer 2

可以看看collections.deque。根据文档的介绍：

双端队列（deque）支持线程安全，并且在内存使用上非常高效，可以从两端快速添加和删除元素，性能大约都是O(1)，也就是无论从哪一边操作，速度都差不多。

虽然列表（list）也能进行类似的操作，但它们是为了快速处理固定长度的操作而优化的。当你使用pop(0)或insert(0, v)时，会导致O(n)的内存移动成本，这意味着在操作时需要移动很多数据，影响性能。

正如文中所说，使用pop(0)或insert(0, v)在列表上会有很大的性能损失。虽然你不能在deque上使用切片或索引操作，但可以使用popleft和appendleft，这些操作是deque特别优化过的。下面是一个简单的基准测试来演示这个问题：

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

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

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

所以没错，deque 确实是一种（双向）链表，就像其他回答提到的那样。

进一步解释一下：这意味着 Python 的列表在随机访问和固定长度操作（比如切片）方面表现得更好，而 deque 则更适合在两端添加或删除元素。虽然 deque 也可以进行索引（查找某个位置的元素），但在这方面的速度比列表要慢，特别是切片操作是不可用的，这点很有意思。