如何实现Python中的deques,以及它们何时比列表更糟糕？

Question

我最近开始研究如何在Python中实现各种数据结构,以使我的代码更高效.在调查列表和deques的工作原理时,我发现当我想要移位和卸载时,我可以获得好处,从列表中的O(n)减少到deques中的O(1)的时间(列表被实现为具有固定长度的数组,具有每次在前面插入某些东西时都要完全复制......).我似乎无法找到的是deque如何实现的具体细节,以及它的缺点与列表的细节.有人可以在这两个问题上启发我吗？

Answer 1

https://hg.python.org/cpython/file/3.5/Modules/_collectionsmodule.c

A dequeobject由双重链接的block节点列表组成.

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

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

Answer 2

退房collections.deque.来自文档:

Deques支持线程安全,内存有效的附加和从双端队列的弹出,在任一方向上具有大致相同的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

Answer 3

我怀疑,deque对象的文档条目说明了你需要知道的大部分内容.值得注意的引用:

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

但...

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

我必须看看源代码来判断实现是否是链接列表或其他内容,但它听起来好像有一个deque与双向链表大致相同的特性.

Answer 4

除了所有其他有用的答案,这里是一些更多的信息,比较不同的业务对Python列表,双端,集合和字典的时间复杂度(大哦).这应该有助于为特定问题选择正确的数据结构.