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

本篇文章將介紹3種常見的數(shù)據(jù)結(jié)構(gòu)和同數(shù)據(jù)有關(guān)的算法。此外，在collections模塊中也包含了針對(duì)各種數(shù)據(jù)結(jié)構(gòu)的解決方案。

[[262323]]

1. 將序列分解為單獨(dú)的變量

(1) 問題

我們有一個(gè)包含 N 個(gè)元素的元組或序列，現(xiàn)在想將它分解為N個(gè)單獨(dú)的變量。

(2) 解決方案

任何序列(或可迭代的對(duì)象)都可以通過一個(gè)簡(jiǎn)單的賦值操作來分解為單獨(dú)的變量。一個(gè)要求是變量的總數(shù)和結(jié)構(gòu)要與序列相吻合。例如：

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

如果元素的數(shù)量不匹配，將得到一個(gè)錯(cuò)誤提示。例如：

>>> 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) 討論

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

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

當(dāng)做分解操作時(shí)，有時(shí)候可能想丟棄某些特定的值。Python并沒有提供特殊的語法來實(shí)現(xiàn)這一點(diǎn)，但是通?？梢赃x一個(gè)用不到的變量名，以此來作為要丟棄的值的名稱。例如：

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

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

2. 從任意長(zhǎng)度的可迭代對(duì)象中分解元素

(1) 問題

需要從某個(gè)可迭代對(duì)象中分解出N個(gè)元素，但是這個(gè)可迭代對(duì)象的長(zhǎng)度可能超過N，這會(huì)導(dǎo)致出現(xiàn)“分解的值過多(too many values to unpack)”的異常。

(2) 解決方案

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

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

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

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

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

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

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

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

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

(3) 討論

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

*式的語法在迭代一個(gè)變長(zhǎng)的元組序列時(shí)尤其有用。例如，假設(shè)有一個(gè)帶標(biāo)記的元組序列：

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) 

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

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

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

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

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

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

在編寫執(zhí)行這類拆分功能的函數(shù)時(shí)，人們可以假設(shè)這是為了實(shí)現(xiàn)某種精巧的遞歸算法。例如：

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

但是請(qǐng)注意，遞歸真的不算是Python的強(qiáng)項(xiàng)，這是因?yàn)槠鋬?nèi)在的遞歸限制所致。因此，最后一個(gè)例子在實(shí)踐中沒太大的意義，只不過是一點(diǎn)學(xué)術(shù)上的好奇罷了。

3. 保存最后N個(gè)元素

(1) 問題

我們希望在迭代或是其他形式的處理過程中對(duì)最后幾項(xiàng)記錄做一個(gè)有限的歷史記錄統(tǒng)計(jì)。

(2) 解決方案

保存有限的歷史記錄可算是collections.deque的應(yīng)用場(chǎng)景了。例如，下面的代碼對(duì)一系列文本行做簡(jiǎn)單的文本匹配操作，當(dāng)發(fā)現(xiàn)有匹配時(shí)就輸出當(dāng)前的匹配行以及最后檢查過的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) 討論

如同上面的代碼片段中所做的一樣，當(dāng)編寫搜索某項(xiàng)記錄的代碼時(shí)，通常會(huì)用到含有yield關(guān)鍵字的生成器函數(shù)。這將處理搜索過程的代碼和使用搜索結(jié)果的代碼成功解耦開來。如果對(duì)生成器還不熟悉，請(qǐng)參見4.3節(jié)。

deque(maxlen=N)創(chuàng)建了一個(gè)固定長(zhǎng)度的隊(duì)列。當(dāng)有新記錄加入而隊(duì)列已滿時(shí)會(huì)自動(dòng)移除最老的那條記錄。例如：

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

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

更普遍的是，當(dāng)需要一個(gè)簡(jiǎn)單的隊(duì)列結(jié)構(gòu)時(shí)，deque可祝你一臂之力。如果不指定隊(duì)列的大小，也就得到了一個(gè)無界限的隊(duì)列，可以在兩端執(zhí)行添加和彈出操作，例如：

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

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