快捷導(dǎo)航

Python collections中的雙向隊(duì)列deque簡(jiǎn)單介紹詳解

更新時(shí)間：2019年11月04日 14:29:06 作者：洛的城

這篇文章主要介紹了Python collections中的雙向隊(duì)列deque簡(jiǎn)單介紹詳解，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧

前言

在python神書(shū)《Python+Cookbook》中有這么一段話：在隊(duì)列兩端插入或刪除元素時(shí)間復(fù)雜度都是 O(1) ，而在列表的開(kāi)頭插入或刪除元素的時(shí)間復(fù)雜度為 O(N)。
于是就想驗(yàn)證下。

簡(jiǎn)單使用

基本代碼

from collections import deque
q = deque(maxlen=4)#有固定長(zhǎng)度的雙向隊(duì)列
qq = deque() #無(wú)固定長(zhǎng)度
print(dir(q))#看看有哪些可用方法或?qū)傩?

結(jié)果：

['__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一樣用中括號(hào) [] 對(duì)某個(gè)index獲取或設(shè)置值。因?yàn)槭请p向隊(duì)列，所以也有左操作函數(shù)：appendleft，popleft。額外的還要反轉(zhuǎn)函數(shù)reverse，計(jì)數(shù)函數(shù)count。

使用ipython驗(yàn)證

In [1]: from collections import deque
…: q = deque(maxlen=4)#有固定長(zhǎng)度的雙向隊(duì)列
…: qq = deque() #無(wú)固定長(zhǎng)度
…: print(dir(q))#看看有哪些可用方法或?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([])

性能測(cè)試

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()

運(yùn)行結(jié)果：

<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()

運(yùn)行結(jié)果：

<function didDeque at 0x0000021367F06D08> cost time: 32 ms
------------
<function didList at 0x0000021367F34048> cost time: 3499 ms

快了兩個(gè)數(shù)量級(jí)。想想也明白，一個(gè)是鏈表，插入的時(shí)候只需要改變指針指向，而List是連續(xù)空間，需要移動(dòng)一大堆的元素。

計(jì)算移動(dòng)平均

>>> 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

結(jié)語(yǔ)

如果可以，數(shù)據(jù)量大的時(shí)候，用deque代替List的能提升一部分性能。而由于deque是隊(duì)列可以設(shè)定固定長(zhǎng)度，實(shí)現(xiàn)先入先出。那么，如在計(jì)算移動(dòng)平均的時(shí)候可以使用，很快捷方便。

以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: