Python collections中的雙向隊列deque簡單介紹詳解
前言
在python神書《Python+Cookbook》中有這么一段話：在隊列兩端插入或刪除元素時間復雜度都是 O(1) ，而在列表的開頭插入或刪除元素的時間復雜度為 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']
看到可以append，pop，insert，clear等，還可以像List一樣用中括號 [] 對某個index獲取或設置值。因為是雙向隊列，所以也有左操作函數(shù)：appendleft，popleft。額外的還要反轉函數(shù)reverse，計數(shù)函數(shù)count。
使用ipython驗證
In [1]: from collections import deque …: q = deque(maxlen=4)#有固定長度的雙向隊列 …: qq = deque() #無固定長度 …: print(dir(q))#看看有哪些可用方法或屬性 [‘a(chǎn)dd', ‘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', ‘a(chǎn)ppend', ‘a(chǎn)ppendleft', ‘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
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
是快了一些。
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
快了兩個數(shù)量級。想想也明白，一個是鏈表，插入的時候只需要改變指針指向，而List是連續(xù)空間，需要移動一大堆的元素。
計算移動平均
>>> 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
結語
如果可以，數(shù)據(jù)量大的時候，用deque代替List的能提升一部分性能。 而由于deque是隊列可以設定固定長度，實現(xiàn)先入先出。 那么，如在計算移動平均的時候可以使用，很快捷方便。
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持腳本之家。
相關文章
這篇文章主要為大家詳細介紹了使用Python編寫自己的微型Redis的相關知識,文中的示例代碼講解詳細,具有一定的學習價值,感興趣的小伙伴可以了解一下2024-03-03
這篇文章主要介紹了利用Python讀取CSV文件并計算某一列的均值和方差,這里利用了csv模塊來對文件進行處理，文章通過實例代碼給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2021-12-12
這篇文章主要介紹了python3 cmp實現(xiàn)方式，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-02-02
這篇文章主要為大家詳細介紹了python字典的常用操作方法，主要內容包含Python中列表(List)的詳解操作方法,包含創(chuàng)建、訪問、更新、刪除、其它操作等,需要的朋友可以參考下2016-05-05
在Python中，set是一種集合數(shù)據(jù)類型，表示一個無序且不重復的集合。本文主要為大家詳細介紹了Python中set方法的使用，需要的可以參考一下2023-04-04
今天小編就為大家分享一篇關于Python3.6使用tesseract-ocr的正確方法，小編覺得內容挺不錯的，現(xiàn)在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧2018-10-10
matplotlib 范圍選區(qū)(SpanSelector)的使用
這篇文章主要介紹了matplotlib 范圍選區(qū)(SpanSelector)的使用，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2021-02-02
在本篇文章中我們給大家分享了關于python開發(fā)游戲的前期準備以及用到的工具等內容，需要的朋友們跟著參考下。2019-05-05
這篇文章主要為大家介紹了python開發(fā)微信服務號消息推送示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪2023-10-10
Python中decimal.Decimal類型和float類型的比較
這篇文章主要介紹了Python中decimal.Decimal類型和float類型的比較,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2023-11-11