Python內置了許多非常有用的數據結構，比如列表(list)、集合(set)以及字典(dictionary)。就絕大部分情況而言，我們可以直接使用這些數據結構。但是，通常我們還需要考慮比如搜索、排序、排列以及篩選等這一類常見的問題。

本篇文章將介紹3種常見的數據結構和同數據有關的算法。此外，在collections模塊中也包含了針對各種數據結構的解決方案。

[[262323]]

1. 將序列分解為單獨的變量

(1) 問題

我們有一個包含 N 個元素的元組或序列，現在想將它分解為N個單獨的變量。

(2) 解決方案

任何序列(或可迭代的對象)都可以通過一個簡單的賦值操作來分解為單獨的變量。一個要求是變量的總數和結構要與序列相吻合。例如：

>>> p = (4, 5) 
>>> x, y = p 
>>> x 
4 
>>> y 
5 
>>> 
>>> data = [ 'ACME', 50, 91.1, (2012, 12, 21) ] 
>>> name, shares, price, date = data 
>>> name 
'ACME' 
>>> date 
(2012, 12, 21) 
>>> name, shares, price, (year, mon, day) = data 
>>> name 
'ACME' 
>>> year 
2012 
>>> mon 
12 
>>> day 
21 
>>> 

如果元素的數量不匹配，將得到一個錯誤提示。例如：

>>> p = (4, 5) 
>>> x, y, z = p 
Traceback (most recent call last): 
 File "<stdin>", line 1, in <module> 
ValueError: need more than 2 values to unpack 
>>> 

(3) 討論

實際上不僅僅只是元組或列表，只要對象恰好是可迭代的，那么就可以執行分解操作。這包括字符串、文件、迭代器以及生成器。比如：

>>> s = 'Hello' 
>>> a, b, c, d, e = s 
>>> a 
'H' 
>>> b 
'e' 
>>> e 
'o' 
>>> 

當做分解操作時，有時候可能想丟棄某些特定的值。Python并沒有提供特殊的語法來實現這一點，但是通常可以選一個用不到的變量名，以此來作為要丟棄的值的名稱。例如：

>>> data = [ 'ACME', 50, 91.1, (2012, 12, 21) ] 
>>> _, shares, price, _ = data 
>>> shares 
50 
>>> price 
91.1 
>>> 

但是請確保選擇的變量名沒有在其他地方用到過。

2. 從任意長度的可迭代對象中分解元素

(1) 問題

需要從某個可迭代對象中分解出N個元素，但是這個可迭代對象的長度可能超過N，這會導致出現“分解的值過多(too many values to unpack)”的異常。

(2) 解決方案

Python的“*表達式”可以用來解決這個問題。例如，假設開設了一門課程，并決定在期末的作業成績中去掉第一個和最后一個，只對中間剩下的成績做平均分統計。如果只有4個成績，也許可以簡單地將4個都分解出來，但是如果有24個呢?*表達式使這一切都變得簡單：

def drop_first_last(grades): 
 first, *middle, last = grades 
 return avg(middle) 

另一個用例是假設有一些用戶記錄，記錄由姓名和電子郵件地址組成，后面跟著任意數量的電話號碼。則可以像這樣分解記錄：

>>> record = ('Dave', 'dave@example.com', '773-555-1212', '847-555-1212') 
>>> name, email, *phone_numbers = user_record 
>>> name 
'Dave' 
>>> email 
'dave@example.com' 
>>> phone_numbers 
['773-555-1212', '847-555-1212'] 
>>> 

不管需要分解出多少個電話號碼(甚至沒有電話號碼)，變量phone_numbers都一直是列表，而這是毫無意義的。如此一來，對于任何用到了變量phone_numbers的代碼都不必對它可能不是一個列表的情況負責，或者額外做任何形式的類型檢查。

由*修飾的變量也可以位于列表的第一個位置。例如，比方說用一系列的值來代表公司過去8個季度的銷售額。如果想對最近一個季度的銷售額同前7個季度的平均值做比較，可以這么做：

*trailing_qtrs, current_qtr = sales_record 
trailing_avg = sum(trailing_qtrs) / len(trailing_qtrs) 
return avg_comparison(trailing_avg, current_qtr) 

從Python解釋器的角度來看，這個操作是這樣的：

>>> *trailing, current = [10, 8, 7, 1, 9, 5, 10, 3] 
>>> trailing 
[10, 8, 7, 1, 9, 5, 10] 
>>> current 
3 

(3) 討論

對于分解未知或任意長度的可迭代對象，這種擴展的分解操作可謂是量身定做的工具。通常，這類可迭代對象中會有一些已知的組件或模式(例如，元素1之后的所有內容都是電話號碼)，利用*表達式分解可迭代對象使得開發者能夠輕松利用這些模式，而不必在可迭代對象中做復雜花哨的操作才能得到相關的元素。

*式的語法在迭代一個變長的元組序列時尤其有用。例如，假設有一個帶標記的元組序列：

records = [ 
 ('foo', 1, 2), 
 ('bar', 'hello'), 
 ('foo', 3, 4), 
] 
def do_foo(x, y): 
 print('foo', x, y) 
def do_bar(s): 
 print('bar', s) 
for tag, *args in records: 
 if tag == 'foo': 
 do_foo(*args) 
elif tag == 'bar': 
 do_bar(*args) 

當和某些特定的字符串處理操作相結合，比如做拆分(splitting)操作時，這種*式的語法所支持的分解操作也非常有用。例如：

>>> line = 'nobody:*:-2:-2:Unprivileged User:/var/empty:/usr/bin/false' 
>>> uname, *fields, homedir, sh = line.split(':') 
>>> uname 
'nobody' 
>>> homedir 
'/var/empty' 
>>> sh 
'/usr/bin/false' 
>>> 

有時候可能想分解出某些值然后丟棄它們。在分解的時候，不能只是指定一個單獨的*，但是可以使用幾個常用來表示待丟棄值的變量名，比如_或者ign(ignored)。例如：

>>> record = ('ACME', 50, 123.45, (12, 18, 2012)) 
>>> name, *_, (*_, year) = record 
>>> name 
'ACME' 
>>> year 
2012 
>>> 

*分解操作和各種函數式語言中的列表處理功能有著一定的相似性。例如，如果有一個列表，可以像下面這樣輕松將其分解為頭部和尾部：

>>> items = [1, 10, 7, 4, 5, 9] 
>>> head, *tail = items 
>>> head 
1 
>>> tail 
[10, 7, 4, 5, 9] 
>>> 

在編寫執行這類拆分功能的函數時，人們可以假設這是為了實現某種精巧的遞歸算法。例如：

>>> def sum(items): 
... head, *tail = items 
... return head + sum(tail) if tail else head 
... 
>>> sum(items) 
36 
>>> 

但是請注意，遞歸真的不算是Python的強項，這是因為其內在的遞歸限制所致。因此，最后一個例子在實踐中沒太大的意義，只不過是一點學術上的好奇罷了。

3. 保存最后N個元素

(1) 問題

我們希望在迭代或是其他形式的處理過程中對最后幾項記錄做一個有限的歷史記錄統計。

(2) 解決方案

保存有限的歷史記錄可算是collections.deque的應用場景了。例如，下面的代碼對一系列文本行做簡單的文本匹配操作，當發現有匹配時就輸出當前的匹配行以及最后檢查過的N行文本。

from collections import deque 
def search(lines, pattern, history=5): 
 previous_lines = deque(maxlen=history) 
 for line in lines: 
 if pattern in line: 
 yield line, previous_lines 
 previous_lines.append(line) 
# Example use on a file 
if __name__ == '__main__': 
 with open('somefile.txt') as f: 
 for line, prevlines in search(f, 'python', 5): 
 for pline in prevlines: 
 print(pline, end='') 
 print(line, end='') 
 print('-'*20) 

(3) 討論

如同上面的代碼片段中所做的一樣，當編寫搜索某項記錄的代碼時，通常會用到含有yield關鍵字的生成器函數。這將處理搜索過程的代碼和使用搜索結果的代碼成功解耦開來。如果對生成器還不熟悉，請參見4.3節。

deque(maxlen=N)創建了一個固定長度的隊列。當有新記錄加入而隊列已滿時會自動移除最老的那條記錄。例如：

>>> q = deque(maxlen=3) 
>>> q.append(1) 
>>> q.append(2) 
>>> q.append(3) 
>>> q 
deque([1, 2, 3], maxlen=3) 
>>> q.append(4) 
>>> q 
deque([2, 3, 4], maxlen=3) 
>>> q.append(5) 
>>> q 
deque([3, 4, 5], maxlen=3) 

盡管可以在列表上手動完成這樣的操作(append、del)，但隊列這種解決方案要優雅得多，運行速度也快得多。

更普遍的是，當需要一個簡單的隊列結構時，deque可祝你一臂之力。如果不指定隊列的大小，也就得到了一個無界限的隊列，可以在兩端執行添加和彈出操作，例如：

>>> q = deque() 
>>> q.append(1) 
>>> q.append(2) 
>>> q.append(3) 
>>> q 
deque([1, 2, 3]) 
>>> q.appendleft(4) 
>>> q 
deque([4, 1, 2, 3]) 
>>> q.pop() 
3 
>>> q 
deque([4, 1, 2]) 
>>> q.popleft() 
4 

從隊列兩端添加或彈出元素的復雜度都是O(1)。這和列表不同，當從列表的頭部插入或移除元素時，列表的復雜度為O(N)。