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

這一篇是《流暢的 python》讀書筆記。主要介紹列表、列表推導有關的話題，最后演示如何用列表實現一個優先級隊列。

Python 標準庫用 C 實現了豐富的序列類型：

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

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

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

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

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

tuple、str和 bytes。

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

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

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

列表推導是構建列表的快捷方式，并且有更好的可讀性。
先看下面兩段代碼：

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

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

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

#2. 把一個字符串變成 unicode 碼位的列表 使用列表推導

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

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

在 Python2 中列表推導有變量泄露的問題

#Python2 的例子

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

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

#Python3 的例子

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

可以看到，這里 x 原有的值被保留了，列表推導也創建了正確的列表。

列表推導還可以生成兩個或以上的可迭代類型的笛卡爾積。

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

# 使用列表推導計算笛卡爾積代碼如下

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

這里得到的結果是先按數字排列，再按圖案排列。如果想先按圖案排列再按數字排列，只需要調整 for 從句的先后順序。

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

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

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

使用列表推導的一個潛在缺陷就是若干輸入非常大的時候會產生一個非常大的結果集，占用大量內存。這個時候，使用生成器表達式迭代產生過濾元素是一個好的選擇。

生成器表達式遵守了迭代器協議，可以逐個產出元素，而不是先建立一個完整的列表，然后再把這個列表傳遞到某個構造函數里。

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

# 使用生成器表達式創建列表

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

如果生成器表達式是一個函數調用過程中唯一的參數，那么不需要額外再用括號把它圍起來。例如：

tuple(n for n in mylist)

如果生成器表達式是一個函數調用過程中其中一個參數，此時括號是必須的。比如：

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

怎么實現一個按優先級排序的隊列？并在這個隊列上每次 pop 操作總是返回優先級最高的那個元素

利用 heapq 模塊

heapq 是 python 的內置模塊，源碼位于 Lib/heapq.py ，該模塊提供了基于堆的優先排序算法。

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

可以通過 list 對 heap 進行初始化，或者通過 api 中的 heapify 將已知的 list 轉化為 heap 對象。

heapq 提供的一些方法如下：

heap = [] #創建了一個空堆

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

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

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

heapq.heapify(x)

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

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

實現如下：

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

通過執行結果我們可以發現，第一個 pop() 操作返回優先級最高的元素。兩個優先級相同的元素（foo 和 grok），pop 操作按照它們被插入到隊列的順序返回。

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

實現上邊排序的關鍵是 元組是支持比較的：

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

當第一個值大小相等時，由于Item 并不支持比較會拋出 TypeError。為了避免上述錯誤，我們引入了index（不可能用兩個元素有相同的 index 值）， 變量組成了(priority, index, item) 三元組。現在再比較就不會出現上述問題了：

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

主要介紹列表、列表推導有關的話題，最后演示如何用heapq和列表實現一個優先級隊列。下一篇介紹元組

Heap queue algorithm

最后，感謝女朋友支持。