来自 collections 模块的 deque 真的比 Python 中的 list 快 100 倍吗？

Question

我的代码有问题吗？使用 collections 模块中的 deque 而非常规列表对简单函数进行计时时，我的速度提高了 100 倍。

>>> from collections import deque as dl
>>> import cProfile
>>> 
>>> def l(i):
...     l = ['0','1','2','3','4','5','6']
...     while i:
...         l.insert(0,'9')
...         i -= 1
... 
>>> def d(i):
...     l = dl('0123456')
...     while i:
...         l.appendleft('9')
...         i -= 1
... 
>>> cProfile.run('l(100000)')
         100004 function calls in 4.480 seconds

[...]

>>> cProfile.run('d(100000)')
         100004 function calls in 0.031 seconds

如果我的代码没问题，那么使用列表有什么意义呢？为什么不完全切换到 deque？

Answer 1

来自 Python 文档：

双端队列是栈和队列的泛化（名字发音为“deck”，是“double-ended queue”的缩写）。双端队列支持线程安全、内存高效的追加和从双端队列的任一侧弹出，在任一方向上的 O(1) 性能大致相同。

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

双端队列支持迭代、pickling、len(d)、reversed(d)、copy.copy(d)、copy.deepcopy(d)、使用 in 运算符的成员资格测试以及下标引用等作为 d[-1]。索引访问在两端是 O(1)，但在中间减慢到 O(n)。对于快速随机访问，请改用列表。

...

现在不同的是list是用固定大小的内存块（数组）实现的，而deque是用双链表实现的。

这意味着列表必须根据您插入新项目的位置重新分配内存并制作数据副本，追加时除外。

但是随机访问（索引）对他们来说非常快。

双端队列没有这样的问题，因为在插入时，只需要修正指针，在给定位置插入一个新节点。

但是查找数据（插入或随机访问的位置 - 索引）需要对双端队列进行迭代。

双端队列也是线程安全的，但除非你必须处理端点，即使用属性队列列表仍然是你最好的朋友。

双端队列对每个项目使用更多的内存，因为它们为每个项目存储至少两个整数（指针）。

还有切片双端队列的问题。它可以通过使用 rotate 方法切换双端队列的端点来手动完成。获取N项然后旋转回来

参见 Python 文档如何仅对一项执行删除：

rotate()方法提供了一种实现双端队列切片和删除的方法。例如，del d[n] 的纯 Python 实现依赖于 rotate() 方法来定位要弹出的元素：

def delete_nth(d, n):
    d.rotate(-n)
    d.popleft()
    d.rotate(n)

我想这对你来说已经足够了。顺便说一句，您的 Q 几乎是以下内容的重复：

How are deques in Python implemented, and when are they worse than lists?

来自 collections 模块的 deque 真的比 Python 中的 list 快 100 倍吗？

Is deque from the collections module really 100 times faster at prepending than list in Python?

python

performance

list

deque

cprofile