python collection雜談之三

4. deque

一般來說作為串列容器，list就可以應付很多狀況，但還是有一些狀況list效能是不理想的，比如說如果要在list的head端做push和pop的動作，其所消耗的時間複雜度是O(n)，也就是他在時間上並不有效支援雙端的push和pop操作，而當我們有這個需求的時候，deque(double-end queue)就是一個不錯的選擇：

In python3 shell:
>>> from collections import deque
>>> d = deque('123456789')
>>> d
deque(['1', '2', '3', '4', '5', '6', '7', '8', '9'])
>>> d.pop() # 提取左邊元素
'9'
>>> d
deque(['1', '2', '3', '4', '5', '6', '7', '8'])
>>> d.popleft() # 提取右邊元素
'1'
>>> d
deque(['2', '3', '4', '5', '6', '7', '8'])
>>> d.extend(['a','b']) # 從tail端新增元素
>>> d
deque(['2', '3', '4', '5', '6', '7', '8', 'a', 'b'])
>>> d.extendleft(['x','y']) # 從head端新增元素
>>> d
deque(['y', 'x', '2', '3', '4', '5', '6', '7', '8', 'a', 'b'])
>>> d.rotate(1) # 看起來稍微巧妙一點的一個方法，其功能和d.appendleft(d.pop())一樣，像轉動輪盤一樣把所有元素的位置像右移了一位，參數可接受負值向左移位
>>> d
deque(['b', 'y', 'x', '2', '3', '4', '5', '6', '7', '8', 'a'])
>>> d.reverse()
>>> d
deque(['a', '8', '7', '6', '5', '4', '3', '2', 'x', 'y', 'b'])

除了上述的操作，deque還支援一般的list方法，比如說len(),reversed()還有用index值獲取元素(當然也接受負值，比如說d[-1])，但其最主要的應用不只體現在其能在雙端快速的操作，而是其初始化時，能夠指定一個maxlen參數，限制deque的大小，但並不是只要deque滿了就不行再接收新的元素，而是從哪一端獲取新元素就從另一端把舊元素丟棄：

In python3 shell:
>>> from collections import deque
>>> d = deque('123456',maxlen=6)
>>> d
deque(['1', '2', '3', '4', '5', '6'], maxlen=6)
>>> d.extend('789') # 元素1,2,3會被丟棄
>>> d
deque(['4', '5', '6', '7', '8', '9'], maxlen=6)
>>> d.extendleft('xyz') # 元素7,8,9會被丟棄
>>> d
deque(['z', 'y', 'x', '4', '5', '6'], maxlen=6)

而這個功能到底好用再哪呢，來試著把我們生活中的一些東西與這個功能的特性來做連結，首先這個特性包括：
(1) 喜新厭舊，接收了新的就會把最舊的淘汰掉
(2) 若在時間序列上看，其就只接收某一段時間連續給予的元素，不會在中間出現斷裂

來試想這是不是與我們瀏覽器常看到的歷史紀錄很像呢，撇除看了什麼不該看的東西(？)才會把歷程紀錄刪掉之外，不就是接收最新的瀏覽紀錄並丟棄最舊的嗎？而deque也能用在音訊分析或其他時間序列分析上所用的一個被稱為'幀'(time frame)的概念，也就是從比較長的時間間隔中取一段小的時間間隔，並在之後對其做一些數值分析。

若對於文字資料處理，我們也可以把他用於查看某pattern在一個檔案中出現時，其附近的文字段為何，以下以此作為範例：

data.txt(先試著寫出這樣一個檔案):
我是不重要文字
我是不重要文字
我是不重要文字
...
重要內容前三行
重要內容前兩行
重要內容前一行
我有重要內容:lalalalala
重要內容後一行
重要內容後兩行
重要內容後三行
...
我是不重要文字
我是不重要文字
我是不重要文字

sample.py(要找到pattern:"lalalalala",與其前後三行的文字):

from collections import deque
import itertools # 這也是個很好用的工具，或許以後有機會介紹

near_line_distance = 3
d = deque(maxlen=2*near_line_distance+1)

with open('data.txt','rt') as data_file:
    print('File start!')
    for line in data_file:
        d.extend([line.rstrip()]) # rstrip可以把結尾'\n'去掉
        if line.find("lalalalala") > 0: # 是否找到重要內容
            for _ in itertools.repeat(None, near_line_distance): # 重複三次同樣行為，用於把重要內容後三行加進deque，這個比for i in range(near_line_distance): 還來的有效率喔
                    d.extend([next(data_file).rstrip()])
           
            for d_line in d: # 印出重要內容的附近內容
                print(d_line)
        
    print('File end!')


In bash:
$ python3 sample.py
File start!
重要內容前三行
重要內容前兩行
重要內容前一行
我有重要內容:lalalalala
重要內容後一行
重要內容後兩行
重要內容後三行
File end!

呵呵，雖然這個code有很多隱性的缺點(也是有很多人覺得缺點很明顯拉orz)，但總之就是這樣，用了deque作為儲存附近內容的容器(也可以說是查閱字串的歷史紀錄)，因為deque可以幫我們自動濾除較舊的紀錄，所以我們可以很安心的直接用extend來增添新的字串進去，而不需要很花費腦筋的去實現濾除舊紀錄的功能，有興趣的人可以試著只用list來實現，但這樣既要多加幾行code，速度又會比deque慢，這實在是個浪費時間的行為XD。

另外還有其他例子，可以在官方文檔https://docs.python.org/3.5/library/collections.html#deque-recipes 中參考，保證會更深入了解deque的應用情境，其中有一個計算moving_average就是一個用deque取time frame的例子。