Python collections中的双向队列deque简单介绍详解
本文详解Python中collections模块的双向队列deque。通过对比list在头部插入删除的时间复杂度，展示deque在O(1)操作下的性能优势。文章包含pop/append及insert操作的实测数据，并演示如何利用deque固定长度特性高效计算移动平均值，为大数据量场景下的数据结构选择提供参考。
前言
deque与list的性能差异分析
参考《Python Cookbook》中的描述，在队列两端进行元素的插入或删除操作，其时间复杂度均为 O(1)；相比之下，在列表（list）开头执行相同的插入或删除操作，时间复杂度则高达 O(N)。基于这一理论差异，本文旨在通过实际代码验证这一结论。
简单使用
基本代码
from collections import deque
q = deque(maxlen=4)#有固定长度的双向队列
qq = deque() #无固定长度
print(dir(q))#看看有哪些可用方法或属性
运行结果如下所示：
['__add__', '__bool__', '__class__', '__contains__', '__copy__', '__delattr__', '__delitem__', '__dir__', '__doc__', '__eq__', '__format__', '__ge__', '__getattribute__', '__getitem__', '__gt__', '__hash__', '__iadd__', '__imul__', '__init__', '__init_subclass__', '__iter__', '__le__', '__len__', '__lt__', '__mul__', '__ne__', '__new__', '__reduce__', '__reduce_ex__', '__repr__', '__reversed__', '__rmul__', '__setattr__', '__setitem__', '__sizeof__', '__str__', '__subclasshook__', 'append', 'appendleft', 'clear', 'copy', 'count', 'extend', 'extendleft', 'index', 'insert', 'maxlen', 'pop', 'popleft', 'remove', 'reverse', 'rotate']
从上述输出可以看出，deque 支持 append、pop、insert、clear 等常见列表操作，同时也支持使用中括号 [] 对指定索引位置的元素进行读取或赋值。作为双向队列，它额外提供了针对左侧的操作方法：appendleft 和 popleft。此外，还包含 reverse（反转）和 count（计数）等实用功能。
deque基本用法与验证
使用ipython验证
In [1]: from collections import deque
…: q = deque(maxlen=4)#有固定长度的双向队列
…: qq = deque() #无固定长度
…: print(dir(q))#看看有哪些可用方法或属性
[‘add', ‘bool', ‘class', ‘contains', ‘copy', ‘delattr', ‘delitem', ‘dir', ‘doc', ‘eq', ‘format', ‘ge', ‘getattribute', ‘getitem', ‘gt', ‘hash', ‘iadd', ‘imul', ‘init', ‘init_subclass', ‘iter', ‘le', ‘len', ‘lt', ‘mul', ‘ne', ‘new', ‘reduce', ‘reduce_ex', ‘repr', ‘reversed', ‘rmul', ‘setattr', ‘setitem', ‘sizeof', ‘str', ‘subclasshook', ‘append', ‘appendleft', ‘clear', ‘copy', ‘count', ‘extend', ‘extendleft', ‘index', ‘insert', ‘maxlen', ‘pop', ‘popleft', ‘remove', ‘reverse', ‘rotate']
In [2]: q
Out[2]: deque([])
In [3]: q.append(1)
In [4]: q.insert(0,33)
In [6]: q
Out[6]: deque([33, 1])
In [8]: q.appendleft(44)
In [9]: q
Out[9]: deque([44, 33, 1])
In [10]: q.pop()
Out[10]: 1
In [12]: q[1]
Out[12]: 33
In [13]: q
Out[13]: deque([44, 33])
In [14]: q.reverse()
In [15]: q
Out[15]: deque([33, 44])
In [17]: q.clear()
In [18]: q
Out[18]: deque([])pop/append与insert性能实测
性能测试
pop和append操作对比
#coding:utf8
import datetime,time
from collections import deque
D = deque()
L=[]
def calcTime(func):
def doCalcTime():
sst = int(time.time()*1000)
func()
eed = int(time.time()*1000)
print(func,'cost time:',eed-sst,'ms')
return doCalcTime
@calcTime
def didDeque():
for i in range(0,10000000):
D.append(i)
while D:
D.pop()
@calcTime
def didList():
for i in range(0,10000000):
L.append(i)
while L:
L.pop()
if __name__=='__main__':
didDeque()
print("------------")
didList()运行结果：
<function didDeque at 0x000002D6912A4D08> cost time: 1924 ms ------------ <function didList at 0x000002D6912D4048> cost time: 2420 ms
结果显示 deque 的速度略快于 list。
insert操作对比
#coding:utf8
import datetime,time
from collections import deque
D = deque()
L=[]
def calcTime(func):
def doCalcTime():
sst = int(time.time()*1000)
func()
eed = int(time.time()*1000)
print(func,'cost time:',eed-sst,'ms')
return doCalcTime
@calcTime
def didDeque():
for i in range(0,100000):
D.insert(5,i)
@calcTime
def didList():
for i in range(0,100000):
L.insert(5,i)
if __name__=='__main__':
didDeque()
print("------------")
didList()运行结果：
<function didDeque at 0x0000021367F06D08> cost time: 32 ms ------------ <function didList at 0x0000021367F34048> cost time: 3499 ms
在 insert 操作中，deque 的速度提升了两个数量级。这符合预期：deque 基于链表实现，插入元素仅需调整指针指向；而 list 基于连续内存空间，插入元素需要移动大量后续元素，导致性能显著下降。
利用deque计算移动平均
计算移动平均
>>> import numpy as np
>>> from collections import deque
>>> q=deque(maxlen=5)
>>> q.append(1)
>>> q.append(2)
>>> q.append(3)
>>> q.append(4)
>>> q.append(5)
>>> q.append(6)
>>> q
deque([2, 3, 4, 5, 6], maxlen=5)
>>> np.array(q).mean()
4.0
结语
在数据量较大的场景下，使用 deque 替代 list 能够有效提升部分操作的性能。由于 deque 支持设定固定长度（maxlen），它天然具备先入先出（FIFO）的特性。因此，在需要计算移动平均值的场景中，使用 deque 可以非常便捷且高效地实现。
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持本站。
免责声明：本文内容仅供参考，不代表本站观点。转载或引用请注明出处。
