摘要：主要介紹列表列表推導(dǎo)有關(guān)的話題，最后演示如何用列表實(shí)現(xiàn)一個(gè)優(yōu)先級隊(duì)列。笛卡爾積列表推導(dǎo)還可以生成兩個(gè)或以上的可迭代類型的笛卡爾積。兩個(gè)優(yōu)先級相同的元素和，操作按照它們被插入到隊(duì)列的順序返回。變量的作用是保證同等優(yōu)先級元素的正確排序。

這一篇是《流暢的 python》讀書筆記。主要介紹列表、列表推導(dǎo)有關(guān)的話題，最后演示如何用列表實(shí)現(xiàn)一個(gè)優(yōu)先級隊(duì)列。

Python 標(biāo)準(zhǔn)庫用 C 實(shí)現(xiàn)了豐富的序列類型：

list、tuple和 collections.deque 這些序列能存放不同類型的數(shù)據(jù)。

str、bytes、bytearray、memoryview 和 array.array，這類序列只能容納一種類型。

容器序列存放的是它們所包含的任意類型的對象的引用，而扁平序列里存放的是值而不是引用（也可以說扁平序列其實(shí)存放的是一段連續(xù)的內(nèi)存空間）。

如果按序列是否可被修改來分類，序列分為可變序列 和 不可變序列:

list、bytearray、array.array、collections.deque 和 memoryview。

tuple、str和 bytes。

下圖顯示了可變序列（MutableSequence）和不可變序列（sequence）的差異：

從這個(gè)圖可以看出，可變序列從不可變序列那里繼承了一些方法。

列表（list）是 Python 中最基礎(chǔ)的序列類型。list 是一個(gè)可變序列，并且能同時(shí)存放不同類型的元素。
列表的基礎(chǔ)用法這里就不再介紹了，這里主要介紹一下列表推導(dǎo)。

列表推導(dǎo)是構(gòu)建列表的快捷方式，并且有更好的可讀性。
先看下面兩段代碼：

#1. 把一個(gè)字符串變成 unicode 碼位的列表

>>> symbols = "$&@#%^&*"
>>> codes = []
>>> for symbol in symbols:
        codes.append(ord(symbol))

>>> codes
[36, 38, 64, 35, 37, 94, 38, 42]

#2. 把一個(gè)字符串變成 unicode 碼位的列表 使用列表推導(dǎo)

>>> symbols = "$&@#%^&*"
>>> codes = [ord(s) for s in symbols]
>>> codes
[36, 38, 64, 35, 37, 94, 38, 42]

對比發(fā)現(xiàn)，如果理解列表推導(dǎo)的話，第二段代碼比第一段更簡潔可讀性也更好。
當(dāng)然，列表推導(dǎo)也不應(yīng)該被濫用，通常的原則是只用列表推導(dǎo)來創(chuàng)建新的列表，并且盡量保持簡短。
如果列表推導(dǎo)超過兩行，就應(yīng)該考慮要不要使用 for 循環(huán)重寫了。

在 Python2 中列表推導(dǎo)有變量泄露的問題

#Python2 的例子

>>> x = "my precious"
>>> dummy = [x for x in "ABC"]
>>> x
"C"

這里 x 原來的值被取代了，變成了列表推導(dǎo)中的最后一個(gè)值，需要避免這個(gè)問題。好消息是 Python3解決了這個(gè)問題。

#Python3 的例子

>>> x = "ABC"
>>> dummy = [ord(x) for x in x]
>>> x 
"ABC"
>>> dummy
[65, 66, 67]

可以看到，這里 x 原有的值被保留了，列表推導(dǎo)也創(chuàng)建了正確的列表。

列表推導(dǎo)還可以生成兩個(gè)或以上的可迭代類型的笛卡爾積。

笛卡爾積是一個(gè)列表，列表里的元素是由輸入的可迭代類型的元素對構(gòu)成的元組，因此笛卡爾積列表的長度等于輸入變量的長度的成績，如圖所示：

# 使用列表推導(dǎo)計(jì)算笛卡爾積代碼如下

>>> suits = ["spades", "diamonds", "clubs", "hearts"]
>>> nums = ["A", "K", "Q"]
>>> cards = [(num, suit) for num in nums for suit in suits]
>>> cards
[("A", "spades"),
 ("A", "diamonds"),
 ("A", "clubs"),
 ("A", "hearts"),
 ("K", "spades"),
 ("K", "diamonds"),
 ("K", "clubs"),
 ("K", "hearts"),
 ("Q", "spades"),
 ("Q", "diamonds"),
 ("Q", "clubs"),
 ("Q", "hearts")]

這里得到的結(jié)果是先按數(shù)字排列，再按圖案排列。如果想先按圖案排列再按數(shù)字排列，只需要調(diào)整 for 從句的先后順序。

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

最簡單的過濾序列元素的方法是使用列表推導(dǎo)。比如：

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

使用列表推導(dǎo)的一個(gè)潛在缺陷就是若干輸入非常大的時(shí)候會(huì)產(chǎn)生一個(gè)非常大的結(jié)果集，占用大量內(nèi)存。這個(gè)時(shí)候，使用生成器表達(dá)式迭代產(chǎn)生過濾元素是一個(gè)好的選擇。

生成器表達(dá)式遵守了迭代器協(xié)議，可以逐個(gè)產(chǎn)出元素，而不是先建立一個(gè)完整的列表，然后再把這個(gè)列表傳遞到某個(gè)構(gòu)造函數(shù)里。

生成器表達(dá)式的語法跟列表推導(dǎo)差不多，只需要把方括號換成圓括號。

# 使用生成器表達(dá)式創(chuàng)建列表

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

如果生成器表達(dá)式是一個(gè)函數(shù)調(diào)用過程中唯一的參數(shù)，那么不需要額外再用括號把它圍起來。例如：

tuple(n for n in mylist)

如果生成器表達(dá)式是一個(gè)函數(shù)調(diào)用過程中其中一個(gè)參數(shù)，此時(shí)括號是必須的。比如：

>>> import array
>>> array.array("list", (n for n in mylist))
array("list", [1, 4, 10, 2, 3])

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

利用 heapq 模塊

heapq 是 python 的內(nèi)置模塊，源碼位于 Lib/heapq.py ，該模塊提供了基于堆的優(yōu)先排序算法。

堆的邏輯結(jié)構(gòu)就是完全二叉樹，并且二叉樹中父節(jié)點(diǎn)的值小于等于該節(jié)點(diǎn)的所有子節(jié)點(diǎn)的值。這種實(shí)現(xiàn)可以使用 heap[k] <= heap[2k+1] 并且 heap[k] <= heap[2k+2] （其中 k 為索引，從 0 開始計(jì)數(shù)）的形式體現(xiàn)，對于堆來說，最小元素即為根元素 heap[0]。

可以通過 list 對 heap 進(jìn)行初始化，或者通過 api 中的 heapify 將已知的 list 轉(zhuǎn)化為 heap 對象。

heapq 提供的一些方法如下：

heap = [] #創(chuàng)建了一個(gè)空堆

heapq.heappush(heap, item)：向 heap 中插入一個(gè)元素

heapq.heappop(heap)：返回 root 節(jié)點(diǎn)，即 heap 中最小的元素

heapq.heappushpop(heap, item)：向 heap 中加入 item 元素，并返回 heap 中最小元素

heapq.heapify(x)

heapq.nlargest(n, iterable, key=None)：返回可枚舉對象中的 n 個(gè)最大值，并返回一個(gè)結(jié)果集 list，key 為對該結(jié)果集的操作

heapq.nsmallest(n, iterable, key=None)：同上相反

實(shí)現(xiàn)如下：

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

通過執(zhí)行結(jié)果我們可以發(fā)現(xiàn)，第一個(gè) pop() 操作返回優(yōu)先級最高的元素。兩個(gè)優(yōu)先級相同的元素（foo 和 grok），pop 操作按照它們被插入到隊(duì)列的順序返回。

函數(shù) heapq.heappush() 和 heapq.heappop() 分別在隊(duì)列 queue 上插入和刪除第一個(gè)元素，并且隊(duì)列 queue 保證 第一個(gè)元素?fù)碛凶钚?yōu)先級。 heappop() 函數(shù)總是返回 最小的 的元素，這就是保證隊(duì)列 pop 操作返回正確元素的關(guān)鍵。另外，由于 push 和 pop 操作時(shí)間復(fù)雜度為 O(log N)，其中 N 是堆的大小，因此就算是 N 很大的時(shí)候它們 運(yùn)行速度也依舊很快。
在上面代碼中，隊(duì)列包含了一個(gè) (-priority, index, item) 的元組。優(yōu)先級為負(fù) 數(shù)的目的是使得元素按照優(yōu)先級從高到低排序。這個(gè)跟普通的按優(yōu)先級從低到高排序的堆排序恰巧相反。
index 變量的作用是保證同等優(yōu)先級元素的正確排序。通過保存一個(gè)不斷增加的 index 下標(biāo)變量，可以確保元素按照它們插入的順序排序。而且， index 變量也在相 同優(yōu)先級元素比較的時(shí)候起到重要作用。

實(shí)現(xiàn)上邊排序的關(guān)鍵是 元組是支持比較的：

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

當(dāng)?shù)谝粋€(gè)值大小相等時(shí)，由于Item 并不支持比較會(huì)拋出 TypeError。為了避免上述錯(cuò)誤，我們引入了index（不可能用兩個(gè)元素有相同的 index 值）， 變量組成了(priority, index, item) 三元組?，F(xiàn)在再比較就不會(huì)出現(xiàn)上述問題了：

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

主要介紹列表、列表推導(dǎo)有關(guān)的話題，最后演示如何用heapq和列表實(shí)現(xiàn)一個(gè)優(yōu)先級隊(duì)列。下一篇介紹元組

Heap queue algorithm

最后，感謝女朋友支持。