94

我最近开始研究如何在 Python 中实现各种数据结构,以使我的代码更高效。在调查列表和双端队列的工作方式时,我发现当我想要转移和取消转移时,我可以获得好处,将列表中的 O(n) 时间减少到双端队列中的 O(1)(列表被实现为具有每次在前面插入东西时都要完全复制,等等......)。我似乎找不到的是如何实现双端队列的细节,以及它的缺点与列表的细节。有人可以在这两个问题上启发我吗?

4

4 回答 4

87

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

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

所以是的,deque正如另一个答案所暗示的那样,a 是一个(双重)链表。

详细说明:这意味着 Python 列表对于随机访问和固定长度操作(包括切片)要好得多,而双端队列对于从末端推送和弹出东西更有用,索引(但不是切片,有趣的是)可能但比列表慢。

于 2011-06-06T19:35:52.833 回答
55

退房collections.deque。从文档:

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

尽管列表对象支持类似的操作,但它们针对快速固定长度操作进行了优化,并且会为 pop(0) 和 insert(0, v) 操作带来 O(n) 内存移动成本,这些操作会改变底层数据表示的大小和位置.

正如它所说,使用 pop(0) 或 insert(0, v) 会对列表对象产生很大的惩罚。您不能在 a 上使用切片/索引操作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
于 2011-06-06T19:35:13.943 回答
20

deque我怀疑,对象的文档条目说明了您需要知道的大部分内容。值得注意的报价:

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

但...

索引访问在两端都是 O(1),但在中间慢到 O(n)。对于快速随机访问,请改用列表。

我必须查看源代码以判断实现是链表还是其他东西,但在我看来,adeque的特征与双向链表大致相同。

于 2011-06-06T19:35:56.990 回答
11

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

于 2013-03-17T18:01:05.863 回答