數據結構和算法

Python 提供了大量的內置數據結構，包括列表，集合以及字典。大多數情況下使用這些數據結構是很簡單的。但是，我們也會經常碰到到諸如查詢，排序和過濾等等這些普遍存在的問題。因此，這一章的目的就是討論這些比較常見的問題和算法。另外，我們也會給出在集合模塊 collections 當中操作這些數據結構的方法。

解壓序列賦值給多個變量

問題

現(xiàn)在有一個包含 N 個元素的元組或者是序列，怎樣將它里面的值解壓后同時賦值給 N 個變量？

解決方案

任何的序列(或者是可迭代對象)可以通過一個簡單的賦值語句解壓并賦值給多個變量。唯一的前提就是變量的數量必須跟序列元素的數量是一樣的。

代碼示例：

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

討論

實際上，這種解壓賦值可以用在任何可迭代對象上面，而不僅僅是列表或者元組。包括字符串，文件對象，迭代器和生成器。

代碼示例：

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

你必須保證你選用的那些占位變量名在其他地方沒被使用到。

解壓可迭代對象賦值給多個變量

問題

如果一個可迭代對象的元素個數超過變量個數時，會拋出一個 ValueError。那么怎樣才能從這個可迭代對象中解壓出 N 個元素出來？

解決方案

Python 的星號表達式可以用來解決這個問題。比如，你在學習一門課程，在學期末的時候，你想統(tǒng)計下家庭作業(yè)的平均成績，但是排除掉第一個和最后一個分數。如果只有四個分數，你可能就直接去簡單的手動賦值，但如果有24個呢？這時候星號表達式就派上用場了：

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

另外一種情況，假設你現(xiàn)在有一些用戶的記錄列表，每條記錄包含一個名字、郵件，接著就是不確定數量的電話號碼。你可以像下面這樣分解這些記錄：

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

值得注意的是上面解壓出的 phone_numbers 變量永遠都是列表類型，不管解壓的電話號碼數量是多少(包括0個)。所以，任何使用到 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 解釋器中執(zhí)行的結果：

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

討論

擴展的迭代解壓語法是專門為解壓不確定個數或任意個數元素的可迭代對象而設計的。通常，這些可迭代對象的元素結構有確定的規(guī)則（比如第1個元素后面都是電話號碼），星號表達式讓開發(fā)人員可以很容易的利用這些規(guī)則來解壓出元素來。而不是通過一些比較復雜的手段去獲取這些關聯(lián)的的元素值。

值得注意的是，星號表達式在迭代元素為可變長元組的序列時是很有用的。比如，下面是一個帶有標簽的元組序列：

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)

星號解壓語法在字符串操作的時候也會很有用，比如字符串的分割。

代碼示例：

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

代碼示例：

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

如果你夠聰明的話，還能用這種分割語法去巧妙的實現(xiàn)遞歸算法。比如：

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

然后，由于語言層面的限制，遞歸并不是 Python 擅長的。因此，最后那個遞歸演示僅僅是個好奇的探索罷了，對這個不要太認真了。

保留最后 N 個元素

問題

在迭代操作或者其他操作的時候，怎樣只保留最后有限幾個元素的歷史記錄？

解決方案

保留有限歷史記錄正是 collections.deque 大顯身手的時候。比如，下面的代碼在多行上面做簡單的文本匹配，并只返回在前N 行中匹配成功的行：

from collections import deque

def search(lines, pattern, history=5):
    previous_lines = deque(maxlen=history)
    for li in lines:
        if pattern in li:
            yield li, previous_lines
        previous_lines.append(li)

# Example use on a file
if __name__ == '__main__':
    with open(r'../../cookbook/somefile.txt') as f:
        for line, prevlines in search(f, 'python', 5):
            for pline in prevlines:
                print(pline, end='')
            print(line, end='')
            print('-' * 20)

討論

我們在寫查詢元素的代碼時，通常會使用包含 yield 表達式的生成器函數，也就是我們上面示例代碼中的那樣。這樣可以將搜索過程代碼和使用搜索結果代碼解耦。如果你還不清楚什么是生成器，請參看4.3節(jié)。

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

盡管你也可以手動在一個列表上實現(xiàn)這一的操作(比如增加、刪除等等)。但是這里的隊列方案會更加優(yōu)雅并且運行得更快些。

更一般的， deque 類可以被用在任何你只需要一個簡單隊列數據結構的場合。 如果你不設置最大隊列大小，那么就會得到一個無限大小隊列，你可以在隊列的兩端執(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

在隊列兩端插入或刪除元素時間復雜度都是 O(1) ，而在列表的開頭插入或刪除元素的時間復雜度為 O(N) 。

查找最大或最小的 N 個元素

問題

怎樣從一個集合中獲得最大或者最小的 N 個元素列表？

解決方案

heapq 模塊有兩個函數：nlargest() 和 nsmallest() 可以完美解決這個問題。

import heapq
nums = [1, 8, 2, 23, 7, -4, 18, 23, 42, 37, 2]
print(heapq.nlargest(3, nums)) # Prints [42, 37, 23]
print(heapq.nsmallest(3, nums)) # Prints [-4, 1, 2]

兩個函數都能接受一個關鍵字參數，用于更復雜的數據結構中：

portfolio = [
    {'name': 'IBM', 'shares': 100, 'price': 91.1},
    {'name': 'AAPL', 'shares': 50, 'price': 543.22},
    {'name': 'FB', 'shares': 200, 'price': 21.09},
    {'name': 'HPQ', 'shares': 35, 'price': 31.75},
    {'name': 'YHOO', 'shares': 45, 'price': 16.35},
    {'name': 'ACME', 'shares': 75, 'price': 115.65}
]
cheap = heapq.nsmallest(3, portfolio, key=lambda s: s['price'])
expensive = heapq.nlargest(3, portfolio, key=lambda s: s['price'])

譯者注：上面代碼在對每個元素進行對比的時候，會以 price 的值進行比較。

討論

如果你想在一個集合中查找最小或最大的 N 個元素，并且 N 小于集合元素數量，那么這些函數提供了很好的性能。 因為在底層實現(xiàn)里面，首先會先將集合數據進行堆排序后放入一個列表中：

>>> nums = [1, 8, 2, 23, 7, -4, 18, 23, 42, 37, 2]
>>> import heapq
>>> heapq.heapify(nums)
>>> nums
[-4, 2, 1, 23, 7, 2, 18, 23, 42, 37, 8]
>>>

堆數據結構最重要的特征是 heap[0] 永遠是最小的元素。并且剩余的元素可以很容易的通過調用 heapq.heappop() 方法得到， 該方法會先將第一個元素彈出來，然后用下一個最小的元素來取代被彈出元素(這種操作時間復雜度僅僅是O(logN)，N 是堆大小)。 比如，如果想要查找最小的3個元素，你可以這樣做：

>>> heapq.heappop(nums)
-4
>>> heapq.heappop(nums)
1
>>> heapq.heappop(nums)
2

當要查找的元素個數相對比較小的時候，函數 nlargest() 和 nsmallest() 是很合適的。如果你僅僅想查找唯一的最小或最大(N=1)的元素的話，那么使用 min()和 max()函數會更快些。類似的，如果 N 的大小和集合大小接近的時候，通常先排序這個集合然后再使用切片操作會更快點 ( sorted(items)[:N] 或者是 sorted(items)[-N:] )。需要在正確場合使用函數nlargest() 和 nsmallest()才能發(fā)揮它們的優(yōu)勢 (如果N 快接近集合大小了，那么使用排序操作會更好些)。

盡管你沒有必要一定使用這里的方法，但是堆數據結構的實現(xiàn)是一個很有趣并且值得你深入學習的東西?；旧现灰菙祿Y構和算法書籍里面都會有提及到。heapq 模塊的官方文檔里面也詳細的介紹了堆數據結構底層的實現(xiàn)細節(jié)。

實現(xiàn)一個優(yōu)先級隊列

問題

怎樣實現(xiàn)一個按優(yōu)先級排序的隊列？ 并且在這個隊列上面每次 pop 操作總是返回優(yōu)先級最高的那個元素

解決方案

下面的類利用 heapq 模塊實現(xiàn)了一個簡單的優(yōu)先級隊列：

import heapq

class PriorityQueue:
    def __init__(self):
        self._queue = []
        self._index = 0

    def push(self, item, priority):
        heapq.heappush(self._queue, (-priority, self._index, item))
        self._index += 1

    def pop(self):
        return heapq.heappop(self._queue)[-1]

下面是它的使用方式：

>>> class Item:
...     def __init__(self, name):
...         self.name = name
...     def __repr__(self):
...         return 'Item({!r})'.format(self.name)
...
>>> q = PriorityQueue()
>>> q.push(Item('foo'), 1)
>>> q.push(Item('bar'), 5)
>>> q.push(Item('spam'), 4)
>>> q.push(Item('grok'), 1)
>>> q.pop()
Item('bar')
>>> q.pop()
Item('spam')
>>> q.pop()
Item('foo')
>>> q.pop()
Item('grok')
>>>

仔細觀察可以發(fā)現(xiàn)，第一個 pop() 操作返回優(yōu)先級最高的元素。另外注意到如果兩個有著相同優(yōu)先級的元素( foo 和 grok )，pop 操作按照它們被插入到隊列的順序返回的。

討論

這一小節(jié)我們主要關注 heapq 模塊的使用。 函數 heapq.heappush() 和 heapq.heappop() 分別在隊列 _queue 上插入和刪除第一個元素， 并且隊列_queue 保證第一個元素擁有最小優(yōu)先級(1.4節(jié)已經討論過這個問題)。 heappop() 函數總是返回”最小的”的元素，這就是保證隊列 pop 操作返回正確元素的關鍵。另外，由于 push 和 pop 操作時間復雜度為O(logN)，其中 N 是堆的大小，因此就算是 N 很大的時候它們運行速度也依舊很快。

在上面代碼中，隊列包含了一個 (-priority, index, item) 的元組。優(yōu)先級為負數的目的是使得元素按照優(yōu)先級從高到低排序。 這個跟普通的按優(yōu)先級從低到高排序的堆排序恰巧相反。

index 變量的作用是保證同等優(yōu)先級元素的正確排序。通過保存一個不斷增加的 index 下標變量，可以確保元素按照它們插入的順序排序。而且，index 變量也在相同優(yōu)先級元素比較的時候起到重要作用。

為了闡明這些，先假定 Item 實例是不支持排序的：

>>> a = Item('foo')
>>> b = Item('bar')
>>> a < b
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: unorderable types: Item() < Item()
>>>

如果你使用元組 (priority, item) ，只要兩個元素的優(yōu)先級不同就能比較。 但是如果兩個元素優(yōu)先級一樣的話，那么比較操作就會跟之前一樣出錯：

>>> a = (1, Item('foo'))
>>> b = (5, Item('bar'))
>>> a < b
True
>>> c = (1, Item('grok'))
>>> a < c
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: unorderable types: Item() < Item()
>>>

通過引入另外的 index 變量組成三元組 (priority, index, item) ，就能很好的避免上面的錯誤， 因為不可能有兩個元素有相同的 index 值。Python 在做元組比較時候，如果前面的比較以及可以確定結果了， 后面的比較操作就不會發(fā)生了：

>>> a = (1, 0, Item('foo'))
>>> b = (5, 1, Item('bar'))
>>> c = (1, 2, Item('grok'))
>>> a < b
True
>>> a < c
True
>>>

如果你想在多個線程中使用同一個隊列，那么你需要增加適當的鎖和信號量機制。 可以查看12.3 小節(jié)的例子演示是怎樣做的。

heapq 模塊的官方文檔有更詳細的例子程序以及對于堆理論及其實現(xiàn)的詳細說明。

字典中的鍵映射多個值

問題

怎樣實現(xiàn)一個鍵對應多個值的字典(也叫 multidict )？

解決方案

一個字典就是一個鍵對應一個單值的映射。如果你想要一個鍵映射多個值，那么你就需要將這多個值放到另外的容器中， 比如列表或者集合里面。比如，你可以像下面這樣構造這樣的字典：

d = {
    'a' : [1, 2, 3],
    'b' : [4, 5]
}
e = {
    'a' : {1, 2, 3},
    'b' : {4, 5}
}

選擇使用列表還是集合取決于你的實際需求。如果你想保持元素的插入順序就應該使用列表， 如果想去掉重復元素就使用集合（并且不關心元素的順序問題）。

你可以很方便的使用 collections 模塊中的 defaultdict 來構造這樣的字典。 defaultdict 的一個特征是它會自動初始化每個 key 剛開始對應的值，所以你只需要關注添加元素操作了。比如：

from collections import defaultdict

d = defaultdict(list)
d['a'].append(1)
d['a'].append(2)
d['b'].append(4)

d = defaultdict(set)
d['a'].add(1)
d['a'].add(2)
d['b'].add(4)

需要注意的是， defaultdict 會自動為將要訪問的鍵(就算目前字典中并不存在這樣的鍵)創(chuàng)建映射實體。 如果你并不需要這樣的特性，你可以在一個普通的字典上使用 setdefault() 方法來代替。比如：

d = {} # A regular dictionary
d.setdefault('a', []).append(1)
d.setdefault('a', []).append(2)
d.setdefault('b', []).append(4)

但是很多程序員覺得 setdefault() 用起來有點別扭。因為每次調用都得創(chuàng)建一個新的初始值的實例(例子程序中的空列表[])。

討論

一般來講，創(chuàng)建一個多值映射字典是很簡單的。但是，如果你選擇自己實現(xiàn)的話，那么對于值的初始化可能會有點麻煩， 你可能會像下面這樣來實現(xiàn)：

d = {}
for key, value in pairs:
    if key not in d:
        d[key] = []
    d[key].append(value)

如果使用 defaultdict 的話代碼就更加簡潔了：

d = defaultdict(list)
for key, value in pairs:
    d[key].append(value)

這一小節(jié)所討論的問題跟數據處理中的記錄歸類問題有大的關聯(lián)?？梢詤⒖?.15小節(jié)的例子。

字典排序

問題

你想創(chuàng)建一個字典，并且在迭代或序列化這個字典的時候能夠控制元素的順序。

解決方案

為了能控制一個字典中元素的順序，你可以使用 collections 模塊中的 OrderedDict 類。 在迭代操作的時候它會保持元素被插入時的順序，示例如下：

from collections import OrderedDict
def ordered_dict():
    d = OrderedDict()
    d['foo'] = 1
    d['bar'] = 2
    d['spam'] = 3
    d['grok'] = 4
    # Outputs "foo 1", "bar 2", "spam 3", "grok 4"
    for key in d:
        print(key, d[key])

當你想要構建一個將來需要序列化或編碼成其他格式的映射的時候， OrderedDict 是非常有用的。 比如，你想精確控制以 JSON 編碼后字段的順序，你可以先使用 OrderedDict 來構建這樣的數據：

>>> import json
>>> json.dumps(d)
'{"foo": 1, "bar": 2, "spam": 3, "grok": 4}'
>>>

討論

OrderedDict 內部維護著一個根據鍵插入順序排序的雙向鏈表。每次當一個新的元素插入進來的時候， 它會被放到鏈表的尾部。對于一個已經存在的鍵的重復賦值不會改變鍵的順序。

需要注意的是，一個 OrderedDict 的大小是一個普通字典的兩倍，因為它內部維護著另外一個鏈表。 所以如果你要構建一個需要大量 OrderedDict 實例的數據結構的時候(比如讀取100,000行CSV 數據到一個 OrderedDict 列表中去)， 那么你就得仔細權衡一下是否使用 OrderedDict 帶來的好處要大過額外內存消耗的影響。

字典的運算

問題

怎樣在數據字典中執(zhí)行一些計算操作(比如求最小值、最大值、排序等等)？

解決方案

考慮下面的股票名和價格映射字典：

prices = {
    'ACME': 45.23,
    'AAPL': 612.78,
    'IBM': 205.55,
    'HPQ': 37.20,
    'FB': 10.75
}

為了對字典值執(zhí)行計算操作，通常需要使用 zip() 函數先將鍵和值反轉過來。比如，下面是查找最小和最大股票價格和股票值的代碼：

min_price = min(zip(prices.values(), prices.keys()))
# min_price is (10.75, 'FB')
max_price = max(zip(prices.values(), prices.keys()))
# max_price is (612.78, 'AAPL')

類似的，可以使用 zip() 和 sorted() 函數來排列字典數據：

prices_sorted = sorted(zip(prices.values(), prices.keys()))
# prices_sorted is [(10.75, 'FB'), (37.2, 'HPQ'),
#                   (45.23, 'ACME'), (205.55, 'IBM'),
#                   (612.78, 'AAPL')]

執(zhí)行這些計算的時候，需要注意的是 zip() 函數創(chuàng)建的是一個只能訪問一次的迭代器。 比如，下面的代碼就會產生錯誤：

prices_and_names = zip(prices.values(), prices.keys())
print(min(prices_and_names)) # OK
print(max(prices_and_names)) # ValueError: max() arg is an empty sequence

討論

如果你在一個字典上執(zhí)行普通的數學運算，你會發(fā)現(xiàn)它們僅僅作用于鍵，而不是值。比如：

min(prices) # Returns 'AAPL'
max(prices) # Returns 'IBM'

這個結果并不是你想要的，因為你想要在字典的值集合上執(zhí)行這些計算?；蛟S你會嘗試著使用字典的 values() 方法來解決這個問題：

min(prices.values()) # Returns 10.75
max(prices.values()) # Returns 612.78

不幸的是，通常這個結果同樣也不是你想要的。你可能還想要知道對應的鍵的信息(比如那種股票價格是最低的？)。

你可以在 min() 和 max() 函數中提供 key 函數參數來獲取最小值或最大值對應的鍵的信息。比如：

min(prices, key=lambda k: prices[k]) # Returns 'FB'
max(prices, key=lambda k: prices[k]) # Returns 'AAPL'

但是，如果還想要得到最小值，你又得執(zhí)行一次查找操作。比如：

min_value = prices[min(prices, key=lambda k: prices[k])]

前面的 zip() 函數方案通過將字典”反轉”為(值，鍵)元組序列來解決了上述問題。當比較兩個元組的時候，值會先進行比較，然后才是鍵。這樣的話你就能通過一條簡單的語句就能很輕松的實現(xiàn)在字典上的求最值和排序操作了。

需要注意的是在計算操作中使用到了(值，鍵)對。當多個實體擁有相同的值的時候，鍵會決定返回結果。比如，在執(zhí)行 min() 和 max() 操作的時候，如果恰巧最小或最大值有重復的，那么擁有最小或最大鍵的實體會返回：

>>> prices = { 'AAA' : 45.23, 'ZZZ': 45.23 }
>>> min(zip(prices.values(), prices.keys()))
(45.23, 'AAA')
>>> max(zip(prices.values(), prices.keys()))
(45.23, 'ZZZ')
>>>

查找兩字典的相同點

問題

怎樣在兩個字典中尋尋找相同點(比如相同的鍵、相同的值等等)？

解決方案

考慮下面兩個字典：

a = {
    'x' : 1,
    'y' : 2,
    'z' : 3
}

b = {
    'w' : 10,
    'x' : 11,
    'y' : 2
}

為了尋找兩個字典的相同點，可以簡單的在兩字典的 keys() 或者 items() 方法返回結果上執(zhí)行集合操作。比如：

# Find keys in common
a.keys() & b.keys() # { 'x', 'y' }
# Find keys in a that are not in b
a.keys() - b.keys() # { 'z' }
# Find (key,value) pairs in common
a.items() & b.items() # { ('y', 2) }

這些操作也可以用于修改或者過濾字典元素。比如，假如你想以現(xiàn)有字典構造一個排除幾個指定鍵的新字典。下面利用字典推導來實現(xiàn)這樣的需求：

# Make a new dictionary with certain keys removed
c = {key:a[key] for key in a.keys() - {'z', 'w'}}
# c is {'x': 1, 'y': 2}

討論

一個字典就是一個鍵集合與值集合的映射關系。字典的 keys() 方法返回一個展現(xiàn)鍵集合的鍵視圖對象。鍵視圖的一個很少被了解的特性就是它們也支持集合操作，比如集合并、交、差運算。 所以，如果你想對集合的鍵執(zhí)行一些普通的集合操作，可以直接使用鍵視圖對象而不用先將它們轉換成一個 set。

字典的 items() 方法返回一個包含(鍵，值)對的元素視圖對象。這個對象同樣也支持集合操作，并且可以被用來查找兩個字典有哪些相同的鍵值對。

盡管字典的 values() 方法也是類似，但是它并不支持這里介紹的集合操作。某種程度上是因為值視圖不能保證所有的值互不相同，這樣會導致某些集合操作會出現(xiàn)問題。不過，如果你硬要在值上面執(zhí)行這些集合操作的話，你可以先將值集合轉換成 set，然后再執(zhí)行集合運算就行了。

刪除序列相同元素并保持順序

問題

怎樣在一個序列上面保持元素順序的同時消除重復的值？

解決方案

如果序列上的值都是 hashable 類型，那么可以很簡單的利用集合或者生成器來解決這個問題。比如：

def dedupe(items):
    seen = set()
    for item in items:
        if item not in seen:
            yield item
            seen.add(item)

下面是使用上述函數的例子：

>>> a = [1, 5, 2, 1, 9, 1, 5, 10]
>>> list(dedupe(a))
[1, 5, 2, 9, 10]
>>>

這個方法僅僅在序列中元素為 hashable 的時候才管用。如果你想消除元素不可哈希(比如 dict 類型)的序列中重復元素的話，你需要將上述代碼稍微改變一下，就像這樣：

def dedupe(items, key=None):
    seen = set()
    for item in items:
        val = item if key is None else key(item)
        if val not in seen:
            yield item
            seen.add(val)

這里的 key 參數指定了一個函數，將序列元素轉換成 hashable 類型。下面是它的用法示例：

>>> a = [ {'x':1, 'y':2}, {'x':1, 'y':3}, {'x':1, 'y':2}, {'x':2, 'y':4}]
>>> list(dedupe(a, key=lambda d: (d['x'],d['y'])))
[{'x': 1, 'y': 2}, {'x': 1, 'y': 3}, {'x': 2, 'y': 4}]
>>> list(dedupe(a, key=lambda d: d['x']))
[{'x': 1, 'y': 2}, {'x': 2, 'y': 4}]
>>>

如果你想基于單個字段、屬性或者某個更大的數據結構來消除重復元素，第二種方案同樣可以勝任。

討論

如果你僅僅就是想消除重復元素，通?？梢院唵蔚臉嬙煲粋€集合。比如：

>>> a
[1, 5, 2, 1, 9, 1, 5, 10]
>>> set(a)
{1, 2, 10, 5, 9}
>>>

然而，這種方法不能維護元素的順序，生成的結果中的元素位置被打亂。而上面的方法可以避免這種情況。

在本節(jié)中我們使用了生成器函數讓我們的函數更加通用，不僅僅是局限于列表處理。比如，如果如果你想讀取一個文件，消除重復行，你可以很容易像這樣做：

with open(somefile,'r') as f:
for line in dedupe(f):
    ...

上述 key 函數參數模仿了 sorted() , min() 和 max() 等內置函數的相似功能?？梢詤⒖?.8和1.13小節(jié)了解更多。

命名切片

問題

你的程序已經出現(xiàn)一大堆已無法直視的硬編碼切片下標，然后你想清理下代碼。

解決方案

假定你有一段代碼要從一個記錄字符串中幾個固定位置提取出特定的數據字段(比如文件或類似格式)：

###### 0123456789012345678901234567890123456789012345678901234567890'
record = '....................100 .......513.25 ..........'
cost = int(record[20:23]) * float(record[31:37])

與其那樣寫，為什么不想這樣命名切片呢：

SHARES = slice(20, 23)
PRICE = slice(31, 37)
cost = int(record[SHARES]) * float(record[PRICE])

第二種版本中，你避免了大量無法理解的硬編碼下標，使得你的代碼更加清晰可讀了。

討論

一般來講，代碼中如果出現(xiàn)大量的硬編碼下標值會使得可讀性和可維護性大大降低。比如，如果你回過來看看一年前你寫的代碼，你會摸著腦袋想那時候自己到底想干嘛啊。這里的解決方案是一個很簡單的方法讓你更加清晰的表達代碼到底要做什么。

內置的 slice() 函數創(chuàng)建了一個切片對象，可以被用在任何切片允許使用的地方。比如：

>>> items = [0, 1, 2, 3, 4, 5, 6]
>>> a = slice(2, 4)
>>> items[2:4]
[2, 3]
>>> items[a]
[2, 3]
>>> items[a] = [10,11]
>>> items
[0, 1, 10, 11, 4, 5, 6]
>>> del items[a]
>>> items
[0, 1, 4, 5, 6]

如果你有一個切片對象 s，你可以分別調用它的 s.start , s.stop, s.step屬性來獲取更多的信息。比如：

>>> s = slice(5, 50, 2)
>>> s.start
5
>>> s.stop
50
>>> s.step
2
>>>

另外，你還能通過調用切片的 indices(size) 方法將它映射到一個確定大小的序列上，這個方法返回一個三元組 (start, stop, step)，所有值都會被合適的縮小以滿足邊界限制，從而使用的時候避免出現(xiàn) IndexError 異常。比如：

>>> s = 'HelloWorld'
>>> a.indices(len(s))
(5, 10, 2)
>>> for i in range(*a.indices(len(s))):
... print(s[i])
...
W
r
d
>>>

序列中出現(xiàn)次數最多的元素

問題

怎樣找出一個序列中出現(xiàn)次數最多的元素呢？

解決方案

collections.Counter 類就是專門為這類問題而設計的，它甚至有一個有用的 most_common() 方法直接給了你答案。

為了演示，先假設你有一個單詞列表并且想找出哪個單詞出現(xiàn)頻率最高。你可以這樣做：

words = [
    'look', 'into', 'my', 'eyes', 'look', 'into', 'my', 'eyes',
    'the', 'eyes', 'the', 'eyes', 'the', 'eyes', 'not', 'around', 'the',
    'eyes', "don't", 'look', 'around', 'the', 'eyes', 'look', 'into',
    'my', 'eyes', "you're", 'under'
]
from collections import Counter
word_counts = Counter(words)
# 出現(xiàn)頻率最高的3個單詞
top_three = word_counts.most_common(3)
print(top_three)
# Outputs [('eyes', 8), ('the', 5), ('look', 4)]

討論

作為輸入， Counter 對象可以接受任意的 hashable 序列對象。 在底層實現(xiàn)上，一個 Counter 對象就是一個字典，將元素映射到它出現(xiàn)的次數上。比如：

>>> word_counts['not']
1
>>> word_counts['eyes']
8
>>>

如果你想手動增加計數，可以簡單的用加法：

>>> morewords = ['why','are','you','not','looking','in','my','eyes']
>>> for word in morewords:
... word_counts[word] += 1
...
>>> word_counts['eyes']
9
>>>

或者你可以使用 update() 方法：

>>> word_counts.update(morewords)
>>>

Counter 實例一個鮮為人知的特性是它們可以很容易的跟數學運算操作相結合。比如：

>>> a = Counter(words)
>>> b = Counter(morewords)
>>> a
Counter({'eyes': 8, 'the': 5, 'look': 4, 'into': 3, 'my': 3, 'around': 2,
"you're": 1, "don't": 1, 'under': 1, 'not': 1})
>>> b
Counter({'eyes': 1, 'looking': 1, 'are': 1, 'in': 1, 'not': 1, 'you': 1,
'my': 1, 'why': 1})
>>> # Combine counts
>>> c = a + b
>>> c
Counter({'eyes': 9, 'the': 5, 'look': 4, 'my': 4, 'into': 3, 'not': 2,
'around': 2, "you're": 1, "don't": 1, 'in': 1, 'why': 1,
'looking': 1, 'are': 1, 'under': 1, 'you': 1})
>>> # Subtract counts
>>> d = a - b
>>> d
Counter({'eyes': 7, 'the': 5, 'look': 4, 'into': 3, 'my': 2, 'around': 2,
"you're": 1, "don't": 1, 'under': 1})
>>>

毫無疑問， Counter 對象在幾乎所有需要制表或者計數數據的場合是非常有用的工具。 在解決這類問題的時候你應該優(yōu)先選擇它，而不是手動的利用字典去實現(xiàn)。

通過某個關鍵字排序一個字典列表

問題

你有一個字典列表，你想根據某個或某幾個字典字段來排序這個列表。

解決方案

通過使用 operator 模塊的 itemgetter 函數，可以非常容易的排序這樣的數據結構。 假設你從數據庫中檢索出來網站會員信息列表，并且以下列的數據結構返回：

rows = [
    {'fname': 'Brian', 'lname': 'Jones', 'uid': 1003},
    {'fname': 'David', 'lname': 'Beazley', 'uid': 1002},
    {'fname': 'John', 'lname': 'Cleese', 'uid': 1001},
    {'fname': 'Big', 'lname': 'Jones', 'uid': 1004}
]

根據任意的字典字段來排序輸入結果行是很容易實現(xiàn)的，代碼示例：

from operator import itemgetter
rows_by_fname = sorted(rows, key=itemgetter('fname'))
rows_by_uid = sorted(rows, key=itemgetter('uid'))
print(rows_by_fname)
print(rows_by_uid)

代碼的輸出如下：

[{'fname': 'Big', 'uid': 1004, 'lname': 'Jones'},
{'fname': 'Brian', 'uid': 1003, 'lname': 'Jones'},
{'fname': 'David', 'uid': 1002, 'lname': 'Beazley'},
{'fname': 'John', 'uid': 1001, 'lname': 'Cleese'}]
[{'fname': 'John', 'uid': 1001, 'lname': 'Cleese'},
{'fname': 'David', 'uid': 1002, 'lname': 'Beazley'},
{'fname': 'Brian', 'uid': 1003, 'lname': 'Jones'},
{'fname': 'Big', 'uid': 1004, 'lname': 'Jones'}]

itemgetter() 函數也支持多個 keys，比如下面的代碼

rows_by_lfname = sorted(rows, key=itemgetter('lname','fname'))
print(rows_by_lfname)

會產生如下的輸出：

[{'fname': 'David', 'uid': 1002, 'lname': 'Beazley'},
{'fname': 'John', 'uid': 1001, 'lname': 'Cleese'},
{'fname': 'Big', 'uid': 1004, 'lname': 'Jones'},
{'fname': 'Brian', 'uid': 1003, 'lname': 'Jones'}]

討論

在上面例子中， rows 被傳遞給接受一個關鍵字參數的 sorted() 內置函數。 這個參數是 callable 類型，并且從 rows 中接受一個單一元素，然后返回被用來排序的值。 itemgetter() 函數就是負責創(chuàng)建這個 callable 對象的。

operator.itemgetter() 函數有一個被 rows 中的記錄用來查找值的索引參數?？梢允且粋€字典鍵名稱， 一個整形值或者任何能夠傳入一個對象的 __getitem__() 方法的值。 如果你傳入多個索引參數給 itemgetter() ，它生成的 callable 對象會返回一個包含所有元素值的元組， 并且 sorted() 函數會根據這個元組中元素順序去排序。 但你想要同時在幾個字段上面進行排序(比如通過姓和名來排序，也就是例子中的那樣)的時候這種方法是很有用的。

itemgetter() 有時候也可以用 lambda 表達式代替，比如：

rows_by_fname = sorted(rows, key=lambda r: r['fname'])
rows_by_lfname = sorted(rows, key=lambda r: (r['lname'],r['fname']))

這種方案也不錯。但是，使用 itemgetter() 方式會運行的稍微快點。因此，如果你對性能要求比較高的話就使用 itemgetter() 方式。

最后，不要忘了這節(jié)中展示的技術也同樣適用于 min() 和 max() 等函數。比如：

>>> min(rows, key=itemgetter('uid'))
{'fname': 'John', 'lname': 'Cleese', 'uid': 1001}
>>> max(rows, key=itemgetter('uid'))
{'fname': 'Big', 'lname': 'Jones', 'uid': 1004}
>>>

排序不支持原生比較的對象

問題

你想排序類型相同的對象，但是他們不支持原生的比較操作。

解決方案

內置的 sorted() 函數有一個關鍵字參數 key ，可以傳入一個 callable 對象給它， 這個 callable 對象對每個傳入的對象返回一個值，這個值會被 sorted 用來排序這些對象。 比如，如果你在應用程序里面有一個 User 實例序列，并且你希望通過他們的 user_id 屬性進行排序， 你可以提供一個以 User 實例作為輸入并輸出對應 user_id 值的 callable 對象。比如：

class User:
    def __init__(self, user_id):
        self.user_id = user_id

    def __repr__(self):
        return 'User({})'.format(self.user_id)

def sort_notcompare():
    users = [User(23), User(3), User(99)]
    print(users)
    print(sorted(users, key=lambda u: u.user_id))

另外一種方式是使用 operator.attrgetter() 來代替 lambda 函數：

>>> from operator import attrgetter
>>> sorted(users, key=attrgetter('user_id'))
[User(3), User(23), User(99)]
>>>

討論

選擇使用 lambda 函數或者是 attrgetter() 可能取決于個人喜好。但是，attrgetter() 函數通常會運行的快點，并且還能同時允許多個字段進行比較。 這個跟 operator.itemgetter() 函數作用于字典類型很類似(參考1.13小節(jié))。 例如，如果 User 實例還有一個 first_name 和 last_name 屬性，那么可以向下面這樣排序：

by_name = sorted(users, key=attrgetter('last_name', 'first_name'))

同樣需要注意的是，這一小節(jié)用到的技術同樣適用于像 min() 和 max() 之類的函數。比如：

>>> min(users, key=attrgetter('user_id')
User(3)
>>> max(users, key=attrgetter('user_id')
User(99)
>>>

通過某個字段將記錄分組

問題

你有一個字典或者實例的序列，然后你想根據某個特定的字段比如 date 來分組迭代訪問。

解決方案

itertools.groupby() 函數對于這樣的數據分組操作非常實用。為了演示，假設你已經有了下列的字典列表：

rows = [
    {'address': '5412 N CLARK', 'date': '07/01/2012'},
    {'address': '5148 N CLARK', 'date': '07/04/2012'},
    {'address': '5800 E 58TH', 'date': '07/02/2012'},
    {'address': '2122 N CLARK', 'date': '07/03/2012'},
    {'address': '5645 N RAVENSWOOD', 'date': '07/02/2012'},
    {'address': '1060 W ADDISON', 'date': '07/02/2012'},
    {'address': '4801 N BROADWAY', 'date': '07/01/2012'},
    {'address': '1039 W GRANVILLE', 'date': '07/04/2012'},
]

現(xiàn)在假設你想在按 date 分組后的數據塊上進行迭代。為了這樣做，你首先需要按照指定的字段(這里就是 date )排序， 然后調用 itertools.groupby() 函數：

from operator import itemgetter
from itertools import groupby

# Sort by the desired field first
rows.sort(key=itemgetter('date'))
# Iterate in groups
for date, items in groupby(rows, key=itemgetter('date')):
    print(date)
    for i in items:
        print(' ', i)

運行結果：

07/01/2012
  {'date': '07/01/2012', 'address': '5412 N CLARK'}
  {'date': '07/01/2012', 'address': '4801 N BROADWAY'}
07/02/2012
  {'date': '07/02/2012', 'address': '5800 E 58TH'}
  {'date': '07/02/2012', 'address': '5645 N RAVENSWOOD'}
  {'date': '07/02/2012', 'address': '1060 W ADDISON'}
07/03/2012
  {'date': '07/03/2012', 'address': '2122 N CLARK'}
07/04/2012
  {'date': '07/04/2012', 'address': '5148 N CLARK'}
  {'date': '07/04/2012', 'address': '1039 W GRANVILLE'}

討論

groupby() 函數掃描整個序列并且查找連續(xù)相同值(或者根據指定 key 函數返回值相同)的元素序列。 在每次迭代的時候，它會返回一個值和一個迭代器對象， 這個迭代器對象可以生成元素值全部等于上面那個值的組中所有對象。

一個非常重要的準備步驟是要根據指定的字段將數據排序。 因為 groupby() 僅僅檢查連續(xù)的元素，如果事先并沒有排序完成的話，分組函數將得不到想要的結果。

如果你僅僅只是想根據 date 字段將數據分組到一個大的數據結構中去，并且允許隨機訪問， 那么你最好使用 defaultdict() 來構建一個多值字典，關于多值字典已經在1.6小節(jié)有過詳細的介紹。比如：

from collections import defaultdict
rows_by_date = defaultdict(list)
for row in rows:
    rows_by_date[row['date']].append(row)

這樣的話你可以很輕松的就能對每個指定日期訪問對應的記錄：

>>> for r in rows_by_date['07/01/2012']:
... print(r)
...
{'date': '07/01/2012', 'address': '5412 N CLARK'}
{'date': '07/01/2012', 'address': '4801 N BROADWAY'}
>>>

在上面這個例子中，我們沒有必要先將記錄排序。因此，如果對內存占用不是很關心， 這種方式會比先排序然后再通過 groupby() 函數迭代的方式運行得快一些。

過濾序列元素

問題

你有一個數據序列，想利用一些規(guī)則從中提取出需要的值或者是縮短序列

解決方案

最簡單的過濾序列元素的方法就是使用列表推導。比如：

>>> mylist = [1, 4, -5, 10, -7, 2, 3, -1]
>>> [n for n in mylist if n > 0]
[1, 4, 10, 2, 3]
>>> [n for n in mylist if n < 0]
[-5, -7, -1]
>>>

使用列表推導的一個潛在缺陷就是如果輸入非常大的時候會產生一個非常大的結果集，占用大量內存。 如果你對內存比較敏感，那么你可以使用生成器表達式迭代產生過濾的元素。比如：

>>> pos = (n for n in mylist if n > 0)
>>> pos
<generator object <genexpr> at 0x1006a0eb0>
>>> for x in pos:
... print(x)
...
1
4
10
2
3
>>>

有時候，過濾規(guī)則比較復雜，不能簡單的在列表推導或者生成器表達式中表達出來。比如，假設過濾的時候需要處理一些異?；蛘咂渌麖碗s情況。這時候你可以將過濾代碼放到一個函數中，然后使用內建的 filter() 函數。示例如下：

values = ['1', '2', '-3', '-', '4', 'N/A', '5']
def is_int(val):
    try:
        x = int(val)
        return True
    except ValueError:
        return False
ivals = list(filter(is_int, values))
print(ivals)
# Outputs ['1', '2', '-3', '4', '5']

filter() 函數創(chuàng)建了一個迭代器，因此如果你想得到一個列表的話，就得像示例那樣使用 list() 去轉換。

討論

列表推導和生成器表達式通常情況下是過濾數據最簡單的方式。其實它們還能在過濾的時候轉換數據。比如：

>>> mylist = [1, 4, -5, 10, -7, 2, 3, -1]
>>> import math
>>> [math.sqrt(n) for n in mylist if n > 0]
[1.0, 2.0, 3.1622776601683795, 1.4142135623730951, 1.7320508075688772]
>>>

過濾操作的一個變種就是將不符合條件的值用新的值代替，而不是丟棄它們。比如，在一列數據中你可能不僅想找到正數，而且還想將不是正數的數替換成指定的數。通過將過濾條件放到條件表達式中去，可以很容易的解決這個問題，就像這樣：

>>> clip_neg = [n if n > 0 else 0 for n in mylist]
>>> clip_neg
[1, 4, 0, 10, 0, 2, 3, 0]
>>> clip_pos = [n if n < 0 else 0 for n in mylist]
>>> clip_pos
[0, 0, -5, 0, -7, 0, 0, -1]
>>>

另外一個值得關注的過濾工具就是 itertools.compress()，它以一個 iterable 對象和一個相對應的 Boolean 選擇器序列作為輸入參數。然后輸出 iterable 對象中對應選擇器為 True 的元素。當你需要用另外一個相關聯(lián)的序列來過濾某個序列的時候，這個函數是非常有用的。比如，假如現(xiàn)在你有下面兩列數據：

addresses = [
    '5412 N CLARK',
    '5148 N CLARK',
    '5800 E 58TH',
    '2122 N CLARK'
    '5645 N RAVENSWOOD',
    '1060 W ADDISON',
    '4801 N BROADWAY',
    '1039 W GRANVILLE',
]
counts = [ 0, 3, 10, 4, 1,