Python：deque与list性能比较

Question

在Python文档中，我可以看到deque是一种专门优化左右两侧弹出/添加元素的特殊集合。例如，文档中说：

Deques是stacks和queues的泛化（名称发音为“deck”，是“double-ended queue”的简称）。 Deques支持线程安全，内存高效的从deque的任一侧进行附加和弹出操作，在任一方向上大约具有相同的O(1)性能。

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

我决定使用ipython进行一些比较。是否有人能解释一下我在这里做错了什么：

In [31]: %timeit range(1, 10000).pop(0)
 10000 loops, best of 3: 114 us per loop

In [32]: %timeit deque(xrange(1, 10000)).pop() 
10000 loops, best of 3: 181 us per loop

In [33]: %timeit deque(range(1, 10000)).pop()
1000 loops, best of 3: 243 us per loop

- Oleg Tarasenko

---

从列表（如range或xrange）创建一个deque对象需要O(n)的时间。 - Jayanth Koushik

同意@JayanthKoushik的看法，需要在同时创建列表和双端队列后使用time.pop。 - vaultah

deque具有内部锁以实现线程安全，而list则没有。 - Xing Fei

不，collections.deque没有内部锁。如果需要锁，你应该使用Queue.Queue。但是deque的append()、appendleft()、pop()、popleft()和len()方法可以被认为是原子操作，这不是通过合同保证，而是因为它们在CPython中的实现方式。参见https://bugs.python.org/issue15329#msg199368。例如，迭代deque不是线程安全的。 - Jostikas

@Michael Ruth - 问题使用了Python2的一个特性，并不意味着答案和一般的[python]问题无关。我重新添加了该标签，以便人们可以找到它。虽然我不是Python专家，但我认为大多数答案对于一般的Python问题来说都是相关的。 - Peter Cordes

Answer 1

有人能解释一下我在这里做错了什么吗？

是的，你的时间是由创建列表或双向队列的时间主导的。与之相比，执行pop所需的时间微不足道。

相反，你应该将你要测试的东西（弹出速度）与设置时间隔离开来：

In [1]: from collections import deque

In [2]: s = list(range(1000))

In [3]: d = deque(s)

In [4]: s_append, s_pop = s.append, s.pop

In [5]: d_append, d_pop = d.append, d.pop

In [6]: %timeit s_pop(); s_append(None)
10000000 loops, best of 3: 115 ns per loop

In [7]: %timeit d_pop(); d_append(None)
10000000 loops, best of 3: 70.5 ns per loop

话虽如此，就性能而言，双端队列和列表之间的真正区别在于：

• 对于 appendleft（） 和 popleft（） 操作，双端队列的速度为 O（1），而对于 insert（0，value） 和 pop（0） 操作，列表的性能为 O（n）。

• 由于底层使用了 realloc（），因此列表的追加效率有时快有时慢。简单代码情况下会过度优化计时（因为realloc不需要移动数据），但实际代码中会非常缓慢（因为内存碎片强制realloc移动所有数据）。相比之下，双端队列的追加性能稳定，因为它从不进行realloc操作，也不移动数据。

- Raymond Hettinger

---

是的，它使用链表逻辑。更具体地说，它使用一个固定长度块的双向链表。 - Raymond Hettinger

使用realloc()来处理列表只是一种优化。每次调整大小时，列表都会过度分配以保证O(1)的平摊附加性能，即使需要在每次调整大小时复制数据。 - augurar

使用realloc()函数不是为了优化，而是作为列表增长的核心。过度分配策略是优化的关键——该策略减少了对realloc()的调用次数，但并没有消除它们。realloc()函数仍然定期调用。这使得计时变得不太可重复和难以解释，因为realloc()性能会根据数据是否需要被复制而产生极大的变化。 - Raymond Hettinger

你完全没有抓住重点。是的，它具有摊销O(1)性能。 然而，由于底层操作有时便宜有时昂贵，所以常数因子变化很大。 - Raymond Hettinger

我会更新答案。在Python 2中，range() 返回一个列表，因此答案是正确的。 - Raymond Hettinger

Answer 2

值得一提的是:

Python 3

deque.pop与list.pop的区别

> python3 -mtimeit -s 'import collections' -s 'items = range(10000000); base = [*items]' -s 'c = collections.deque(base)' 'c.pop()'
5000000 loops, best of 5: 46.5 nsec per loop 
    
> python3 -mtimeit -s 'import collections' -s 'items = range(10000000); base = [*items]' 'base.pop()'
5000000 loops, best of 5: 55.1 nsec per loop

deque.appendleft与list.insert的区别

> python3 -mtimeit -s 'import collections' -s 'c = collections.deque()' 'c.appendleft(1)'
5000000 loops, best of 5: 52.1 nsec per loop

> python3 -mtimeit -s 'c = []' 'c.insert(0, 1)'
50000 loops, best of 5: 12.1 usec per loop

Python 2

> python -mtimeit -s 'import collections' -s 'c = collections.deque(xrange(1, 100000000))' 'c.pop()'
10000000 loops, best of 3: 0.11 usec per loop
    
> python -mtimeit -s 'c = range(1, 100000000)' 'c.pop()'
10000000 loops, best of 3: 0.174 usec per loop
   
> python -mtimeit -s 'import collections' -s 'c = collections.deque()' 'c.appendleft(1)'
10000000 loops, best of 3: 0.116 usec per loop
    
> python -mtimeit -s 'c = []' 'c.insert(0, 1)'
100000 loops, best of 3: 36.4 usec per loop

正如您所看到的，deque最擅长的是在appendleft和insert之间进行选择。

- sberry

Answer 3

我建议您参考https://wiki.python.org/moin/TimeComplexity。Python 的列表和 deque 在大多数操作（如 push、pop 等）的复杂度方面相似。

- Krishan Chopra

---

但是需要特别注意的是，这并不适用于 popleft / .pop(0) / 弹出中间元素，而这正是该问题试图衡量的内容。 - Peter Cordes

Answer 4

我找到了这个问题并想提供一个带有一些背景的例子。
使用Deque的经典用例可能是在集合中旋转/移动元素，因为（正如其他人提到的那样），对于两端的push/pop操作，您可以获得非常好的（O（1））复杂度，因为这些操作只是在移动引用，而不是像列表一样必须在内存中物理移动对象。

所以这里有两个非常相似的左旋实现：（rotate-left function）

def rotate_with_list(items, n):
    l = list(items)
    for _ in range(n):
        l.append(l.pop(0))
    return l

from collections import deque
def rotate_with_deque(items, n):
    d = deque(items)
    for _ in range(n):
        d.append(d.popleft())
    return d

注意：这是deque的一个常见用法，deque有内置的rotate方法，但为了视觉比较而在这里手动执行。

现在让我们使用%timeit。

In [1]: def rotate_with_list(items, n):
   ...:     l = list(items)
   ...:     for _ in range(n):
   ...:         l.append(l.pop(0))
   ...:     return l
   ...: 
   ...: from collections import deque
   ...: def rotate_with_deque(items, n):
   ...:     d = deque(items)
   ...:     for _ in range(n):
   ...:         d.append(d.popleft())
   ...:     return d
   ...: 

In [2]: items = range(100000)

In [3]: %timeit rotate_with_list(items, 800)
100 loops, best of 3: 17.8 ms per loop

In [4]: %timeit rotate_with_deque(items, 800)
The slowest run took 5.89 times longer than the fastest. This could mean that an intermediate result is being cached.
1000 loops, best of 3: 527 µs per loop

In [5]: %timeit rotate_with_list(items, 8000)
10 loops, best of 3: 174 ms per loop

In [6]: %timeit rotate_with_deque(items, 8000)
The slowest run took 8.99 times longer than the fastest. This could mean that an intermediate result is being cached.
1000 loops, best of 3: 1.1 ms per loop

In [7]: more_items = range(10000000)

In [8]: %timeit rotate_with_list(more_items, 800)
1 loop, best of 3: 4.59 s per loop

In [9]: %timeit rotate_with_deque(more_items, 800)
10 loops, best of 3: 109 ms per loop

很有趣的是，这两种数据结构展示了一个惊人地相似的界面，但却有着截然不同的性能表现 :)

- ccchoy

Answer 5

出于好奇，我尝试在列表的开头插入元素，与使用deque的appendleft()方法相比较。
显然deque更胜一筹。

- abhay patil

---

最好将代码和文本作为文本复制/粘贴（使用代码块进行格式化），而不是像sberry在他们的答案中展示结果的文本图片。一些用户是盲人并使用文本到语音，而其他用户则被公司防火墙阻止了imgur。 - Peter Cordes

@PeterCordes 这只有七行。 - abhay patil

那么复制粘贴并进行格式化就不会花费太多时间。 - Peter Cordes

无论如何，这段代码都不能在纯Python上运行，@PeterCordes。我认为这种批评有点太苛刻了。如果想要可以复制/粘贴的东西，请使用其他答案；因为在任何情况下复制/粘贴这个代码都没有意义。 - Can H. Tartanoglu

@CanH.Tartanoglu：我从未说过我想复制/粘贴这段代码到任何地方，我说的是这个答案的作者应该这样做，将他们的代码从那里放到SO上。这是关于搜索索引文本而不是图像。我在第一条评论中提到的原因是：盲用户和阻止imgur的防火墙。 - Peter Cordes

所讨论的响应具有我喜欢看到的风格，但可悲的是复制/粘贴代码并没有意义。是的，这不是一种包容性格式，这是一个问题。有一个直接等价物可以在其他答案中复制/粘贴。我们应该倡导将jupyter笔记本集成到StackExchange框架中，因为这会给使用本地功能的响应者带来太大的压力。 - Can H. Tartanoglu