Python collections中的双向队列deque简单介绍详解
前言
在python神书《Python+Cookbook》中有这么一段话：在队列两端插入或删除元素时间复杂度都是O(1)，而在列表的开头插入或删除元素的时间复杂度为O(N)。
于是就想验证下。
简单使用
基本代码
fromcollectionsimportdeque 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']
看到可以append，pop，insert，clear等，还可以像List一样用中括号[]对某个index获取或设置值。因为是双向队列，所以也有左操作函数：appendleft，popleft。额外的还要反转函数reverse，计数函数count。
使用ipython验证
In[1]:fromcollectionsimportdeque …: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
#coding:utf8
importdatetime,time
fromcollectionsimportdeque
D=deque()
L=[]
defcalcTime(func):
defdoCalcTime():
sst=int(time.time()*1000)
func()
eed=int(time.time()*1000)
print(func,'costtime:',eed-sst,'ms')
returndoCalcTime
@calcTime
defdidDeque():
foriinrange(0,10000000):
D.append(i)
whileD:
D.pop()
@calcTime
defdidList():
foriinrange(0,10000000):
L.append(i)
whileL:
L.pop()
if__name__=='__main__':
didDeque()
print("------------")
didList()
运行结果：
costtime:1924ms
------------
costtime:2420ms
是快了一些。
insert
#coding:utf8
importdatetime,time
fromcollectionsimportdeque
D=deque()
L=[]
defcalcTime(func):
defdoCalcTime():
sst=int(time.time()*1000)
func()
eed=int(time.time()*1000)
print(func,'costtime:',eed-sst,'ms')
returndoCalcTime
@calcTime
defdidDeque():
foriinrange(0,100000):
D.insert(5,i)
@calcTime
defdidList():
foriinrange(0,100000):
L.insert(5,i)
if__name__=='__main__':
didDeque()
print("------------")
didList()
运行结果：
costtime:32ms
------------
costtime:3499ms
快了两个数量级。想想也明白，一个是链表，插入的时候只需要改变指针指向，而List是连续空间，需要移动一大堆的元素。
计算移动平均
>>>importnumpyasnp >>>fromcollectionsimportdeque >>>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是队列可以设定固定长度，实现先入先出。那么，如在计算移动平均的时候可以使用，很快捷方便。
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。