python - 如何最有效地使用 collections.deque(popleft 与 appendleft)

Question

我在学习 Python 中的数据结构时一直在学习队列，并想询问有关其使用的问题。

我想有两种方法从队列中追加/弹出。第一种方法是使用 deque.append()和 deque.popleft() .另一种方法是使用 deque.appendleft()和 deque.pop() .两者之间有性能差异吗？如果不是，根据您的经验，哪个更常用？您是否出于其他原因推荐一个？

在我看来，它们本质上做同样的事情，因为它们都实现了先进先出。您的意见将不胜感激!

Answer 1

根据 the docs :

Deques support thread-safe, memory efficient appends and pops from either side of the deque with approximately the same O(1) performance in either direction.

所以两个选项之间没有渐近差异；无论哪种方式，您的“入队”和“轮询”操作都是在恒定时间内完成的。这是意料之中的，因为双端队列(双端队列)的全部意义在于在双方都有高效的添加和删除操作。

使用 timeit 的实证结果确认基本没有区别:

from collections import deque

def append_popleft():
    d = deque()
    for i in range(10000):
        d.append(i)
    for j in range(10000):
        d.popleft()

def appendleft_pop():
    d = deque()
    for i in range(10000):
        d.appendleft(i)
    for j in range(10000):
        d.pop()

import timeit
t = timeit.timeit(append_popleft, number=10000)
print('append / popleft:', t)
t = timeit.timeit(appendleft_pop, number=10000)
print('appendleft / pop:', t)

输出:

append / popleft: 12.000681700999849
appendleft / pop: 11.937629571999423