第六章 Python數據結構 · python 3 面向對象編程筆記

[TOC] 到目前為止，在我們的例子中，我們已經看到了許多內置的Python數據結構。你可能已經在介紹性文章或教程中了解了一些數據結構。在本章中，我們將討論這些數據結構中的面向對象的特性，何時應該使用它們來代替常規類，以及何時不應該使用它們。特別的，我們將了解： * 元組和命名元組 * 詞典 * 列表和集合 * 如何以及為什么擴展內置對象 * 三種類型的隊列 ## 空對象讓我們從最基本的Python內置類型開始，我們已經見過很多次了，我們創建的每個類都繼承自它：對象`object`。技術上，我們可以實例化一個對象，而不需要編寫它的子類： ``` >>> o = object() >>> o.x = 5 Traceback (most recent call last): File "<stdin>", line 1, in <module> AttributeError: 'object' object has no attribute 'x' ``` 不幸的是，如你所見，我們不能在直接實例化的對象上設置任何屬性。這不是因為Python開發人員想要強制我們寫我們自己的類，或者其他任何如此險惡的事情。他們這樣做是為了節省內存；很多很多內存。當Python允許對象具有任意屬性時，需要一定量的系統內存存儲屬性名及屬性值，用于跟蹤每個對象的屬性。即使沒有存儲屬性，仍然需要分配內存給*潛在的*新屬性。鑒于典型的Python程序存在數十、數百或數千個的對象（每個類都擴展自`object`）；每一筆小的內存開銷很快匯成大量的內存消耗。所以，默認情況下，Python會禁用`object`和其他幾個內置類型添加任意屬性。 > 可以使用`slots`來限制對我們自己類添加任意屬性。`slots`超出了本書的范圍，你可以使用搜索詞查找更多的信息。在正常使用中，使用`slots`沒什么好處，但是如果你在寫一個將在整個系統中復制數千次的對象，它可以幫助節省內存，就像它對`object`那樣。然而，創建一個我們自己的空對象類是微不足道的；我們在我們的最早的例子中看過這樣的空對象類： ``` class MyObject: pass ``` 正如我們已經看到的，我們可以在這樣的類上設置屬性： ``` >>> m = MyObject() >>> m.x = "hello" >>> m.x 'hello' ``` 如果我們想將屬性組合在一起，我們可以像這樣將它們存儲在一個空對象中。但是通常我們最好使用其他為存儲數據而設計的內置類型。我們在整本書都強調類和對象只應該在我們希望*同時*指定數據和行為的情況下使用。寫空類的主要原因就是快速封鎖一些東西，我們稍后會回來增加行為。空類很容易修改行為，這比用對象替換數據結構并更改對它的所有引用，要容易得多。因此，從一開始就要判斷數據僅僅是數據，還是它是偽裝的對象。一旦設計決策完成后，剩下的設計就水到渠成了。 ## 元組和命名元組元組是可以按順序存儲特定數量的其他對象的對象。它們是不可變的，所以我們不能在元組之上添加、刪除或替換對象。這似乎就像一個巨大的限制，但事實是，如果你需要修改元組，你多半正在使用錯誤的數據類型（通常列表更合適）。元組不變性的主要好處是，我們可以把它們作為字典的鍵，或者對象需要哈希值的其他地方。 元組用于存儲數據；行為不能存儲在元組中。如果我們需要操縱元組，我們必須將元組傳遞給函數（或者其他對象方法）來執行操作。 元組通常應該存儲彼此不同的值。例如，我們不會將三個股票符號放在一個元組中，但是我們可以創建一個包含股票符號、當前價格、當天的高低價格的元組。使用元組的主要目的是將不同的數據片段集合到一個容器中。因此，元組可以是替換“無數據對象”的最簡單的工具。 我們可以通過用逗號分隔值來創建元組。通常，元組是用圓括號括起來，以便于閱讀和區分表達式的其他部分，但這并不總是強制性的。以下兩種賦值寫法是相同的（它們記錄一家盈利公司的股票符號、當前價格、高點和低點價格）： ``` >>> stock = "FB", 75.00, 75.03, 74.90 >>> stock2 = ("FB", 75.00, 75.03, 74.90) ``` 如果我們在某個其他對象（如函數調用、列表或生成器）內部使用元組，括號是必需的。否則，解釋器將無從判斷它是元組還是下一個函數參數。例如，以下函數接受元組和日期，并返回一個包含日期和股票高低價平均值的元組： ``` import datetime def middle(stock, date): symbol, current, high, low = stock return (((high + low) / 2), date) mid_value, date = middle(("FB", 75.00, 75.03, 74.90), datetime.date(2014, 10, 31)) ``` 元組是通過將值用逗號分隔開，并將整個元組括在括號中。作為函數參數的元組，用逗號將它與函數的第二個參數分開。 這個例子還說明了元組解包。函數內部的第一行將`stock`參數拆分為四個不同的變量。元組長度必須與變量的數量完全相同，否則會引發異常。我們還可以在最后一行看到元組解包的示例，函數內部返回了一個元組，該元組被解包成兩個值，中間值`mid_value `和日期`date`。當然，有點奇怪的是，我們首先為函數提供了日期，但是這給了我們一個查看解包是如何工作的機會。 解包是Python中非常有用的特性。我們可以將變量組成元組，讓存儲和傳遞它們變得更簡單，但是當我們需要訪問它們時，我們可以把它們分解成單獨的變量。當然，有時候我們只需要訪問元組中的一個變量。我們可以使用與其他序列類型(例如列表和字符串)相同的語法來訪問單個值： ``` >>> stock = "FB", 75.00, 75.03, 74.90 >>> high = stock[2] >>> high 75.03 ``` 我們甚至可以使用切片獲取元組的一個片段： ``` >>> stock[1:3] (75.00, 75.03) ``` 這些例子雖然說明了元組是多么靈活，但也展示了一個主要缺點：可讀性。一個人閱讀這些代碼，怎么會知道特定元組的第二個位置代表的是什么呢？從我們賦予它的變量名稱，人們可以猜測，它在某種程度上是`high`，但是如果我們在沒有分配元組值的情況下訪問計算中的元組值，就不會有這樣的暗示。人們將不得不在探索元組之前是什么，在代碼中尋找聲明元組的位置。 在某些情況下，直接訪問元組成員是可以的，但不要成為一種習慣。這種所謂的“神奇數字”（似乎來自代碼中沒有明顯含義的稀薄空氣）是許多編碼的錯誤來源并導致幾個小時的失敗調試。只有當你知道所有的元組值都會立刻有用才使用元組，而且通常在訪問時才解包。如果你必須直接訪問成員或使用切片并且該值的目的不是顯而易見的，至少加一些注釋解釋它來自哪里。 ### 命名元組那么，當我們想把某些值組合在一起，又知道我們經常需要單獨訪問它們時，我們該怎么做？我們可以使用一個空對象，就像上一節已經討論過了的（但是除非我們預期會添加行為），或者我們可以使用字典（如果我們不知道具體有多少特定數據將被存儲，這將非常有用），這將在下一節中介紹。 然而，如果我們不需要向對象添加行為，并且事先知道我們需要存儲什么屬性，我們可以使用命名元組。命名元組是帶有屬性的元組。它們是將只讀數據進行分組的一個好方法。 構建一個命名元組比構建一個普通元組多一些工作。首先，我們必須導入`namedtuple`，因為默認情況下它不在命名空間中。然后，我們通過給命名元組命名并概述其屬性來描述命名元組。這會返回一個類似類的對象，我們可以隨時用我們所需要的值來實例化它們： ``` from collections import namedtuple Stock = namedtuple("Stock", "symbol current high low") stock = Stock("FB", 75.00, high=75.03, low=74.90) ``` `namedtuple`構造函數接受兩個參數。第一個是命名元組的標識。第二個參數是一串以空格分隔、元組的屬性字符串。第一個屬性被列出，后跟一個空格（或逗號，看你喜歡），然后是第二個屬性，然后是另一個空格，依此類推。結果是一個對象，可以像普通類一樣調用來實例化其他對象。這個構造函數必須傳入正確數量的參數，作為參數或鍵參數。和普通對象一樣，我們可以創造盡可能多的這個“類”的實例，每個實例都有不同的值。 然后，可以將生成的`namedtuple`的文件打包、解包，像普通元組那樣操作，但是我們也可以像訪問對象一樣訪問它的單個屬性： ``` >>> stock.high 75.03 >>> symbol, current, high, low = stock >>> current 75.00 ``` > 請記住，創建命名元組是一個兩步過程。首先，使用`collections.namedtuple`創建一個類，然后構造該類的實例。命名元組對于許多“僅數據”表示來說是完美的，但是它們并不適用于所有情況。像元組和字符串一樣，命名元組是不可變的，所以我們不能設置屬性后修改它。例如，自從我們開始討論以來，我公司的股票當前值已經下跌，但是我們不能設置新值: ``` >>> stock.current = 74.98 Traceback (most recent call last): File "<stdin>", line 1, in <module> AttributeError: can't set attribute ``` 如果我們需要能夠改變已經存儲的數據，字典可能是我們需要的。 ## 字典字典是非常有用的容器，允許我們直接將對象映射到其他對象上。具有屬性的空對象是一種字典；名字屬性映射到屬性值。這實際上比聽起來更接近事實。在內部，對象通常將屬性表示為字典，其中值是對象的屬性或方法（如果你不相信我，請參見`__dict__`屬性）。甚至模塊上的屬性也存儲在內部字典中。 給定一個特定的鍵，這個鍵是映射到某個值的對象，通過字典很容易找到這個值。當你想基于一個對象找到另一個對象的時候，應該一直使用字典。正在被存儲的對象稱為**值**；用作索引的對象稱為**鍵**。我們已經在前面一些例子中看到了字典語法。 字典可以使用`dict()`構造函數或`{}`快捷方式創建。實際上，后一種格式幾乎總是被使用。我們可以預先填充一個字典，通過使用冒號將鍵與值分開，然后使用逗號將鍵值對分開。 例如，在股票應用程序中，我們通常希望通過股票符號查詢價格。我們可以創建一個以股票符號作為鍵、以當前價格、高價和低價構成的元組作為鍵值的字典： ``` stocks = {"GOOG": (613.30, 625.86, 610.50), "MSFT": (30.25, 30.70, 30.19)} ``` 正如我們在前面的例子中看到的，我們可以在字典中通過請求方括號內的鍵來查找值。如果鍵不在字典里，它會的引發異常： ``` >>> stocks["GOOG"] (613.3, 625.86, 610.5) >>> stocks["RIM"] Traceback (most recent call last): File "<stdin>", line 1, in <module> KeyError: 'RIM' ``` 當然，我們可以捕捉`KeyError`并處理它。但是我們還有其他選擇。記住，字典是對象，即使它們的主要目的是容納其他的對象。因此，它們有幾種相關的行為。其中這些方法中最有用的是`get`方法；它接受一個鍵作為第一個參數，和一個如果鍵不存在時可選的默認值： ``` >>> print(stocks.get("RIM")) None >>> stocks.get("RIM", "NOT FOUND") 'NOT FOUND' ``` 為了獲得更多的控制，我們可以使用`setdefault`方法。如果鍵在字典里，這個方法的行為就像`get`一樣返回該鍵的值。否則，如果鍵不在字典中，它不僅會返回我們在方法中提供的默認值（就像`get`做的那樣），它也將給這個鍵設置同樣的默認值。另一種思考方式是`setdefault`只在字典中不存在一個鍵的值時，才會設置該鍵的值。它返回的值，要么是已經存在的，要么是一個新提供的默認值。 ``` >>> stocks.setdefault("GOOG", "INVALID") (613.3, 625.86, 610.5) >>> stocks.setdefault("BBRY", (10.50, 10.62, 10.39)) (10.50, 10.62, 10.39) >>> stocks["BBRY"] (10.50, 10.62, 10.39) ``` ` GOOG`股票已經在字典里了，所以當我們試圖使用`setdefault`方法為它設置無效值時，它只會返回字典中已經存在的值。`BBRY`不在字典中，所以`setdefault`返回默認值，并在給我們的字典添加了新的鍵值對。隨后我們可以查看字典里的新股票。 另外三種非常有用的字典方法是`keys()`、`values()`和`items()`。前兩個返回字典中所有鍵的迭代器和所有值的迭代器。我們可以像使用列表那樣使用它們，如果我們想處理所有的鍵或值，可以在for循環中使用它們。`items()`方法可能是最有用的；它為字典中每個項目配對返回一個元組迭代器`(key，value)`。使用元組解包對for循環中歷遍相關的鍵和值非常有用。下面這個例子打印了字典中每種股票的當前價格： ``` >>> for stock, values in stocks.items(): ... print("{} last value is {}".format(stock, values[0])) ... GOOG last value is 613.3 BBRY last value is 10.50 MSFT last value is 30.25 ``` 每個鍵/值元組被解包成兩個名為`stock`和`values`的變量（我們可以使用任何我們想要的變量名，但是這兩個名字似乎都是合適的），然后打印格式化字符串。 請注意，股票的顯示順序不同于它們的插入順序。由于高效的算法（哈希算法）被用來鍵查找，用以提高查詢效率，所以，字典本質上是無序的。 因此，一旦字典被實例化，就有很多數據被檢索的方法；我們可以使用方括號作為索引查詢，以及`get`方法、`setdefault`方法，或者`items`方法上的迭代器，等等。 最后，你可能已經知道，我們可以使用與檢索值時使用的索引語法相同的語法給鍵設置值： ``` >>> stocks["GOOG"] = (597.63, 610.00, 596.28) >>> stocks['GOOG'] (597.63, 610.0, 596.28) ``` 谷歌今天的價格更低，所以我更新了字典中的元組值。我們可以使用此索引語法為任何鍵設置值，而不用管鍵是否在字典里。如果鍵在字典中，舊值將被新值替換；否則，將創建一個新的鍵/值對。 到目前為止，我們一直使用字符串作為字典鍵，但并不局限于字符串鍵。通常使用字符串作為鍵，尤其是當我們用字典來存儲收集來的數據（而不是使用具有命名屬性的對象）。但是我們也可以使用元組、數字，甚至我們自己定義的對象作為字典鍵。我們甚至可以在一個字典中使用不同類型的鍵： ``` random_keys = {} random_keys["astring"] = "somestring" random_keys[5] = "aninteger" random_keys[25.2] = "floats work too" random_keys[("abc", 123)] = "so do tuples" class AnObject: def __init__(self, avalue): self.avalue = avalue my_object = AnObject(14) random_keys[my_object] = "We can even store objects" my_object.avalue = 12 try: random_keys[[1,2,3]] = "we can't store lists though" except: print("unable to store list\n") for key, value in random_keys.items(): print("{} has value {}".format(key, value)) ``` 這段代碼顯示了我們可以提供給字典的幾種不同類型的鍵。它也顯示一種無法使用的對象類型。我們已經廣泛使用了列表，我們將在下一節看到更多的細節。因為列表可以隨時更改（例如，通過添加或刪除項目），所以它們不能哈希為特定的值。 可**哈希**的對象有一個預定義算法，可以將對象轉換為唯一的整數值以便快速查找。這個哈希值實際上在字典中被用來查找值。例如，字符串基于字符串中的字符被映射為整數，而元組是元組中項目的哈希值的組合。任何兩個在某種程度上被認為相等的對象（就像具有相同字符的字符串或具有相同值的元組）應該具有相同的哈希值，對象的哈希值永遠不應該改變。然而，列表可以更改它們的內容，這將改變它們的哈希值（兩個列表的哈希值當且僅當它們的內容相同時才會相等）。正因為如此，它們不能用作字典的鍵。出于同樣的原因，字典也不能用作其他字典的鍵。 相比之下，可以用作字典鍵值的對象類型沒有這樣的限制。例如，我們可以把字符串鍵映射到列表值上，或者我們可以將嵌套字典作為另一個字典中的值。 ### 用戶字典字典的用途非常廣泛。有兩個主要的使用方法。第一種方法是所有的字典鍵代表相似對象的不同實例；例如，我們的股票字典。這是一個索引系統。我們使用股票符號作為值的索引。這些值甚至可能是復雜的自定義的對象，用于購買和出售決策，或設定止損，而不是簡單的元組。 第二種設計是字典的每個鍵代表一個結構的某個方面；在這種情況下，我們最好為每個對象使用單獨的字典，他們都有相似（雖然通常不完全相同）的鍵。這種情況也可以用命名元組來解決。如果使用命名元組，我們得確切地知道數據必須存儲哪些屬性，并且我們知道我們可以立即提供這些屬性數據（當項目被構建時）。但是如果我們需要隨著時間的推移創建或更改字典鍵，或者我們不知道具體會出現什么鍵，字典可能更合適。 ### 使用默認字典我們已經看到了如果一個鍵不存在，如何使用`setdefault`來設置默認值，但是如果我們每次查詢時都需要設置默認值，這可能會變得有點乏味。例如，如果我們正在計算字母出現在給定的句子中的數量，我們可以這樣做： ``` def letter_frequency(sentence): frequencies = {} for letter in sentence: frequency = frequencies.setdefault(letter, 0) frequencies[letter] = frequency + 1 return frequencies ``` 每次我們訪問字典，我們都需要檢查它是否已經有一個鍵值，如果沒有，將其設置為零。如果每次都需要查詢空鍵的話，我們可以使用另外一種不同版本的字典，稱為`defaultdict`： ``` from collections import defaultdict def letter_frequency(sentence): frequencies = defaultdict(int) for letter in sentence: frequencies[letter] += 1 return frequencies ``` 這段代碼看起來不可能工作。`defaultdict`在它的構造函數接受一個函數。當訪問字典中還沒有定義的鍵時，它調用沒有參數的函數為這個鍵創建默認值。 在這種情況下，它調用的函數是`int`，它是整數對象的構造函數。通常，只需在代碼中輸入一個整數就可以創建整數，并且如果我們確實使用`int`構造函數創建了一個整數，我們會將我們想要創建的項傳遞給它（例如，將數字串轉換成整數）。但是如果我們調用不帶參數的`int`構造函數（即`int()`），它會返回數字零。在這段代碼中，如果字母不存在于`defaultdict`中，當我們訪問它時會返回零。然后我們給這個數字加一，表示我們找到了這個字母的一個實例，下一次我們找到一個，這個數字將被返回，我們可以再次增加這個值。 `defaultdict`對于創建容器字典很有用。如果我們想創建一個過去30天的股票價格字典，我們可以使用股票符號作為鍵，將價格存儲在列表`list`中；我們第一次接觸股票價格時，我們希望創建一個空列表。只需將列表`list`傳遞給`defaultdict`，然后每次訪問空鍵時都會調用它。我們可以用集合或者一個空字典做類似的事情，如果我們想與一個鍵相關聯的話。 當然，我們也可以編寫自己的函數，并將它們傳遞給`defaultdict`。假設我們想要創建一個`defaultdict`，其中每個新元素包含一個元組，元組內有一個表示當前插入字典的條目數和空列表。沒人知道我們為什么要創造這樣一個對象，但是讓我們看看這個對象長什么樣子的： ``` from collections import defaultdict num_items = 0 def tuple_counter(): global num_items num_items += 1 return (num_items, []) d = defaultdict(tuple_counter) ``` 當我們運行這段代碼時，我們可以在一行代碼同時訪問空鍵并插入一個列表： ``` >>> d = defaultdict(tuple_counter) >>> d['a'][1].append("hello") >>> d['b'][1].append('world') >>> d defaultdict(<function tuple_counter at 0x82f2c6c>, {'a': (1, ['hello']), 'b': (2, ['world'])}) ``` 當我們在最后打印`dict`時，我們看到計數器真的在工作。 > 這個例子，雖然簡潔地展示了如何為`defaultdict`創建我們自己的函數，實際上不是很好的代碼；使用全局變量意味著如果我們創建了四個（譯注：為什么是四個？）不同的`defaultdict`代碼段，每個代碼段都使用`tuple_counter`，它會計數所有字典中的條目數，而不是為每個字典計算不同的條目數。最好創建一個類并將這個類的一個方法傳遞給`defaultdict`。 #### 計數器你可能會認為你不能比`defaultdict(int)`做得更簡單了，但是“我想以可迭代的方式統計特定實例的數量”是一個已經足夠常見的用例，所以Python開發人員為它創建了一個特定的類。之前用于統計字符串字符數量的代碼，可以很容易地在一行代碼中計算出來： ``` from collections import Counter def letter_frequency(sentence): return Counter(sentence) ``` 計數器對象的行為就像一個增強的字典，其中鍵是被計數的項目，值是這些項目的數量。其中最有用的一個函數是`most_common()`方法。它返回一個按照計數排序的`(key，value)`元組列表。你可以選擇將整數參數傳遞到`most_common()`中，以便只查看最常見的元素。例如，你可以寫一個簡單的投票應用程序，如下所示： ``` from collections import Counter responses = [ "vanilla", "chocolate", "vanilla", "vanilla", "caramel", "strawberry", "vanilla" ] print( "The children voted for {} ice cream".format( Counter(responses).most_common(1)[0][0] ) ) ``` 大概，你會從數據庫得到統計數量，或使用復雜的視覺算法計算舉手孩子的數量。在這里，我們把它硬編碼成這樣，以便于我們可以測試`most_common`方法。它返回只有一個元素的列表（因為我們只請求返回一個元素）。此元素存儲位置是0、排名第一的名稱，因此被調用的函數以雙`[0][0]`結束。我覺得它們看起來像一張驚訝的臉，不是嗎？你的電腦可能很驚訝它可以如此輕松地計算數據。它的祖先，1890年美國人口普查的霍爾瑞斯制表機，知道后一定很嫉妒！ ## 列表列表是Python數據結構中最不面向對象的。雖然列表本身是對象，Python中有很多語法可以盡可能地輕松使用它們。與許多其他面向對象語言不同，Python中的列表簡單易用。我們不需要導入它們，也很少需要在它們身上調用方法。我們可以在列表中歷遍，而無需顯式請求迭代器對象，我們可以用自定義語法構建一個列表（就像字典一樣）。此外，列表解析和生成器表達式使它們成為計算中名副其實的瑞士軍刀。 我們不會深入到語法的太多細節；你可以通過網絡的入門教程和本書前面的例子中看到列表。如果你不學習如何使用列表，你不可能編寫很好的python代碼！我們將學習何時使用列表，以及它們作為對象的性質。如果你不知道如何創建或向列表添加元素，如何從列表中檢索項目，或者什么是“切片符號”，你最好盡快查看官方Python教程。你可以在[https://docs.python.org/3/tutorial/](https://docs.python.org/3/tutorial/)找到它們。 在Python中，當我們想要存儲幾個具有“相同”類型對象實例時，最常用的就是列表；例如字符串列表或數字列表；最常見的是，我們自定義的對象列表。當我們想要以某種秩序存儲項目時，應該始終使用列表。通常，這是它們被插入的順序，但是它們也可以按照一些標準來排序。 正如我們在前幾章案例研究中看到的，當我們需要修改內容時，列表是非常有用的：插入對象到任意位置或從任意位置刪除對象，或者更新列表中的值。 像字典一樣，Python列表使用一個非常有效且經過良好調教的內部數據結構，這樣我們就可以只關心我們儲存的是什么，而不是考慮如何儲存它。許多面向對象語言為隊列、堆棧、鏈表和基于數組的列表提供不同的數據結構（譯注：這點特別要留意一下）。Python確實提供了其中一些類的特殊實例，用來優化對大量數據集的訪問。然而，通常情況下，列表數據結構可以同時服務于所有這些目的，程序員可以完全控制如何訪問它。 不要使用列表來收集具有單個項目的不同屬性。例如，一個特定形式的屬性列表，這并不是我們所希望的列表，元組、命名元組、字典和對象都更適合這個目的。在一些語言里，它們可能會創建一個列表，其中每個替換項都有不同的類型；例如，它們可能將字母頻率列表寫成['a '，1，' b '，3]。它們必須使用一個奇怪的循環，一次訪問列表中的兩個元素或使用一個模數操作符決定訪問哪個位置。 不要在Python中做這個。我們可以使用字典將相關的項目組合在一起，如我們在上一節中所做的（如果順序無關緊要），或者使用元組列表。這里有一個相當復雜的例子，展示了我們如何使用列表計算頻率的示例。它比字典中的例子復雜得多，而且說明選擇正確（或錯誤）的數據結構將影響我們代碼的可讀性： ``` import string CHARACTERS = list(string.ascii_letters) + [" "] def letter_frequency(sentence): frequencies = [(c, 0) for c in CHARACTERS] for letter in sentence: index = CHARACTERS.index(letter) frequencies[index] = (letter,frequencies[index][1]+1) return frequencies ``` 這段代碼以可能的字符列表開始。`string.ascii_letters`屬性按順序提供所有小寫和大寫字母的字符串。我們將它轉換為列表，然后使用列表串聯（加號運算符將兩個列表合并成一個）添加一個字符，即空格。這些是我們頻率列表中的可用字符（如果我們試圖添加不在列表中的字母，會引起程序崩潰，但是異常處理程序可以解決這個問題）。 函數的第一行使用列表解析將字符列表轉換成元組列表。列表解析是Python中一個重要的、非面向對象的的工具；我們將在下一章詳細介紹它們。 然后我們循環遍歷句子中的每個字符。我們首先查找字符列表中的字符索引，我們知道我們的頻率列表也具有同樣的索引，因為我們剛剛從第一個列表創建了第二個列表。然后我們創建一個新元組來更新頻率列表的索引，同時丟棄原來的元組。除了垃圾收集和內存浪費之外，它還很難閱讀！ 像字典一樣，列表也是對象，它們有幾種可以調用的方法。以下是一些常見的例子： * `append(element)`方法在列表末尾添加一個元素 * `insert(index, element)`方法在特定位置插入項目 * `count(element)`方法告訴我們一個元素在列表中出現了多少次 * `index()`方法告訴我們列表中某項的索引，如果找不到，則引發異常 * `find()`方法做同樣的事情，但是返回-1而不是引發遺失項目的異常 * `reverse()`方法完全按照它所說的做——反轉列表 * `sort()`方法有一些相當復雜的面向對象行為，我們現在將討論這個問題 ### 排序列表沒有任何參數，`sort`通常會做預期的事情。如果它是一個列表字符串，它會按字母順序排列。這個操作區分大小寫，所以所有大寫字母將在小寫字母之前排序，也就是說，Z在a之前。如果是數字列表，它們將按數字順序排序。如果提供的是元組列表，列表按每個元組中的第一個元素排序。如果列表含混合的不可排序的項，排序將引發`TypeError`異常。 如果我們想把我們定義的對象放入到一個列表中，并希望這些對象可排序，我們必須做更多的工作。特殊方法`__lt__`，代表“小于”，以使該類的實例具有可比性。列表中的`sort`方法將在每個對象上訪問該方法，以確定該對象在列表中的位置。如果我們的類在某種程度上小于傳入參數，`__lt__`方法返回True，否則返回False。這里有一個相當愚蠢的類，可以基于字符串或數字對其排序： ``` class WeirdSortee: def __init__(self, string, number, sort_num): self.string = string self.number = number self.sort_num = sort_num. def __lt__(self, object): if self.sort_num: return self.number < object.number return self.string < object.string def __repr__(self): return"{}:{}".format(self.string, self.number) ``` `__repr__`方法使我們打印列表時很容易看到這兩個值。`__lt__`方法的實現將對象與的另一個同類實例進行比較（或者任何具有`string`, `number`和`sort_num`屬性的鴨子類型的對象；如果這些屬性缺失，它將失敗)。以下輸出說明了這個類是如何排序的： ``` >>> a = WeirdSortee('a', 4, True) >>> b = WeirdSortee('b', 3, True) >>> c = WeirdSortee('c', 2, True) >>> d = WeirdSortee('d', 1, True) >>> l = [a,b,c,d] >>> print(l) [a:4, b:3, c:2, d:1] >>> l.sort() >>> print(l) [d:1, c:2, b:3, a:4] >>> for i in l: ... i.sort_num = False ... >>> l.sort() >>> l [a:4, b:3, c:2, d:1] ``` 我們第一次調用`sort`，它是按數字排序的，因為所有正在比較的對象的`sort_num`是TRUE。第二次，它按字母排序。`__lt__`方法是我們實現排序所需要的唯一方法。然而，從技術上講，如果`__lt__`方法可以實現，那么類通常也能實現類似的`__gt__`，`__eq__`、`__ne__`、`__ge__`、和`__le__`方法，以便所有<、>、==、！=、> =、和< =操作符也能正常工作。你可以先實現`__lt__`和`__eq__`，然后應用`@total_ordering`類裝飾器來提供其余的操作符： ``` from functools import total_ordering @total_ordering class WeirdSortee: def __init__(self, string, number, sort_num): self.string = string self.number = number self.sort_num = sort_num def __lt__(self, object): if self.sort_num: return self.number < object.number return self.string < object.string def __repr__(self): return"{}:{}".format(self.string, self.number) def __eq__(self, object): return all(( self.string == object.string, self.number == object.number, self.sort_num == object.number )) ``` 如果我們想在對象上使用操作符，這很有用。然而，假設我們想要做的是定制我們的排序順序，即使這么做是多余的。對于這種用例，`sort`方法可以采用可選的鍵參數。這個參數是一個函數，可以將列表中的每個對象翻譯成可以進行比較的對象。例如，我們可以使用`str.lower`作為鍵參數來執行不區分大小寫的字符串列表排序： ``` >>> l = ["hello", "HELP", "Helo"] >>> l.sort() >>> l ['HELP', 'Helo', 'hello'] >>> l.sort(key=str.lower) >>> l ['hello', 'Helo', 'HELP'] ``` 記住，即使`lower`是字符串對象上的方法，它也是一個函數，可以接受唯一的參數，`self`。換句話說，`str.lower(item)`等效于`item.lower()`。當我們將這個函數作為鍵傳遞時，它會執行基于小寫字母的比較，而不是進行默認的區分大小寫的比較。 有幾個排序關鍵操作如此常見，以至于Python團隊提供了它們，這樣你就不用自己寫了。例如，按照元組列表中第一項之外的內容對元組列表進行排序是很常見的。 `operator.itemgetter`方法可以用作實現此目的的鍵參數： ``` >>> from operator import itemgetter >>> l = [('h', 4), ('n', 6), ('o', 5), ('p', 1), ('t', 3), ('y', 2)] >>> l.sort(key=itemgetter(1)) >>> l [('p', 1), ('y', 2), ('t', 3), ('h', 4), ('o', 5), ('n', 6)] ``` `itemgetter`函數是最常用的函數(如果對象是字典，也是如此)，但有時你會發現它用于`attrgetter`和`methodcaller`，返回對象的屬性和調用對象方法的結果，基于同樣的目的。有關更多信息，請參見`operator`模塊文檔。 ## 集合列表是非常通用的工具，適合大多數容器對象應用程序。但是當我們想要確保列表中的對象是唯一的時，它們就沒有用了。例如，歌曲庫可能包含同一藝術家的許多歌曲。如果我們想整理歌曲庫，列出所有藝術家的名單，在我們再次添加藝術家之前，我們必須核對一下，查看是否已經添加這個藝術家。 這是使用集合的場景。集合來自數學，它們代表一個無序的(通常)唯一的數字組。我們可以給集合重復加一個數字5次，但它只會在集合中出現一次。 在Python中，集合可以保存任何可哈希的對象，而不僅僅是數字。哈希對象和可以在字典中用作為鍵的對象是相同的；所以，列表和字典過時了。像數學集合一樣，它們只能存儲每個對象的一個副本。所以如果我們想創建一個歌曲藝術家列表，我們可以創建一個字符串名字集合，并簡單地將它們添加到集合中。本示例以(歌曲、藝術家)元組列表開始并創建一個藝術家集合： ``` song_library = [("Phantom Of The Opera", "Sarah Brightman"), ("Knocking On Heaven's Door", "Guns N' Roses"), ("Captain Nemo", "Sarah Brightman"), ("Patterns In The Ivy", "Opeth"), ("November Rain", "Guns N' Roses"), ("Beautiful", "Sarah Brightman"), ("Mal's Song", "Vixy and Tony")] artists = set() for song, artist in song_library: artists.add(artist) print(artists) ``` 空集沒有內置語法，就像列表和字典一樣；我們使用`set()`構造函數創建一個集合。然而，我們可以使用花括號（借用字典語法）創建一個集合，只要該集合包含值。如果我們用冒號來分隔成對的值，它就是一個字典，如`{“key”: value '，' key2': 'value2'}`。如果我們用逗號分隔值，它就是一個集合，如`{'value '，' value2'}`。項目將通過`add`方法被添加到集合中。如果我們運行這個腳本，我們會看到該集合像廣告一樣工作： ``` {'Sarah Brightman', "Guns N' Roses", 'Vixy and Tony', 'Opeth'} ``` 如果你注意到輸出，你會注意到項目沒有按照它們被添加到集合中的順序被打印出來。像字典一樣，集合是無序的。兩者都使用基于哈希的底層數據結構來提高效率。因為集合是無序的，所以不能按索引查找項目。集合的主要目的就是把世界分成兩組：“在集合中的東西”和“不在集合中的東西”。很容易檢查一個項目是否在集合中或歷遍一個集合，但是如果我們想要對它們進行排序，我們必須將集合轉換為列表。下面顯示了所有這三項活動： ``` >>> "Opeth" in artists True >>> for artist in artists: ... print("{} plays good music".format(artist)) ... Sarah Brightman plays good music Guns N' Roses plays good music Vixy and Tony play good music Opeth plays good music >>> alphabetical = list(artists) >>> alphabetical.sort() >>> alphabetical ["Guns N' Roses", 'Opeth', 'Sarah Brightman', 'Vixy and Tony'] ``` 雖然集合的主要*特征*是唯一性，但這不是它的主要*目的*。當兩個或多個集合合并時，集合最有用。集合類型上的大多數方法可以在其他集合上操作，允許我們有效地合并或比較兩個或更多集合中的項目。這些方法有奇怪的名字，因為他們使用與數學中相同的術語。我們將從三種方法開始，三種方法將返回相同的結果，不管哪個是調用集，哪個是被調用集。 `union`方法是最常見和最容易理解的。它將第二個集合設置為參數并返回一個新的集合，該集合包含兩個集合中的任何一個集合的所有元素；如果一個元素同時存在于兩個原始集合中，它當然只會在新集合中出現一次。`union`就像一個邏輯or運算，事實上，如果你不喜歡調用方法，`|`運算符可以在兩個集合上使用來執行`union`操作。相反，交集方法接受第二個集合并返回一個新集合，該集合僅包含兩個集合中都有的那些元素。這就像一個邏輯and運算，也可以使用&運算符代替。 最后，`symmetric_difference`方法告訴我們還剩下什么；它是一組對象，在一個集合或另一個集合中，但不是兩者都有。下面的例子，通過比較我和我姐姐的歌曲庫中的藝術家，說明了這些方法： ``` my_artists = {"Sarah Brightman", "Guns N' Roses", "Opeth", "Vixy and Tony"} auburns_artists = {"Nickelback", "Guns N' Roses", "Savage Garden"} print("All: {}".format(my_artists.union(auburns_artists))) print("Both: {}".format(auburns_artists.intersection(my_artists))) print("Either but not both: {}".format( my_artists.symmetric_difference(auburns_artists))) ``` 如果我們運行這段代碼，我們會看到這三種方法與打印語句一樣，建議這樣做： ``` All: {'Sarah Brightman', "Guns N' Roses", 'Vixy and Tony', 'Savage Garden', 'Opeth', 'Nickelback'} Both: {"Guns N' Roses"} Either but not both: {'Savage Garden', 'Opeth', 'Nickelback', 'Sarah Brightman', 'Vixy and Tony'} ``` 不管哪個集合調用另一個集合，這些方法都返回相同的結果。我們可以說 `my_artists.union(auburns_artists)` 或 `auburns_artists. union(my_artists)`，并獲得相同的結果。也有返回不同結果的方法，這取決于誰是調用者和誰是參數。 這些方法包括`issubset`和`issuperset`，它們是反義詞。兩者都返回一個`bool`對象。如果調用集中的所有項也在作為參數傳入的集合中，`issubset`返回True。如果作為傳入參數的集合中的所有項都在調用集中，`issuperset`方法則返回True。因此，`s.issuebset(t)`和`t.ssueperset(s)`是相同的。他們都將返回True，如果t包含s的所有元素。 最后，`difference`方法返回調用集合中的、但不在作為參數傳入的集合中的所有元素；這就像半個`symmetric_difference`方法。`difference`方法也可以用-運算符表示。接下來的代碼說明了這些方法的作用: ``` my_artists = {"Sarah Brightman", "Guns N' Roses", "Opeth", "Vixy and Tony"} bands = {"Guns N' Roses", "Opeth"} print("my_artists is to bands:") print("issuperset: {}".format(my_artists.issuperset(bands))) print("issubset: {}".format(my_artists.issubset(bands))) print("difference: {}".format(my_artists.difference(bands))) print("*"*20) print("bands is to my_artists:") print("issuperset: {}".format(bands.issuperset(my_artists))) print("issubset: {}".format(bands.issubset(my_artists))) print("difference: {}".format(bands.difference(my_artists))) ``` 當從一個集合調用另外一個集合時，這些代碼簡單地打印出每個方法的響應。運行它會給出以下輸出: ``` my_artists is to bands: issuperset: True issubset: False difference: {'Sarah Brightman', 'Vixy and Tony'} ******************** bands is to my_artists: issuperset: False issubset: True difference: set() ``` 在第二種情況下，`difference`方法返回一個空集合，因為`band`中不存在的元素也不存在于`my_artists`。 `union`、`intersection`、`difference`方法都可以將多個集合視為參數；如我們所料，它們將創建一個對所有參數調用操作之后的集合。 集合上的方法清楚地表明這個集合可以在其他集合上可以執行的操作，所以它們不僅僅是容器。如果我們有兩個不同的數據來源，并需要以某種方式快速合并它們，以確定數據在哪里重疊或不同，我們可以使用集合運算來有效地比較它們。或者如果我們收到的數據可能包含已經處理后的副本，我們可以使用集合來比較兩者，并且只處理新數據。 最后，在使用`in`關鍵字檢查成員資格方面，集合比列表更有效。如果在集合或列表使用 `value in container `，如果容器存在一個等值元素，則返回True，否則返回False。但是，在列表中，它將查看容器中的每一個對象，而在集合中，它只是哈希這個值，然后檢查會員資格。這意味著不管容器有多大，集合會在相同時間內找到值，但是當列表包含越來越多的值，列表就需要越來越長的時間來搜索一個值。 ## 擴展內置類型我們在第3章“當對象相似時”簡單地討論過，內置數據類型如何使用繼承來進行擴展的。現在，我們將更詳細地討論何時我們應該這么做。 當我們有一個要添加功能的內置容器對象時，我們有兩種選擇。我們可以創建一個新對象，將容器保存為屬性（組合），或者我們可以子類化內置對象并添加或修改方法來做我們想要的（繼承）。 如果我們只想使用容器的功能存儲一些對象，組合通常是最好的選擇。這樣，很容易將數據結構傳遞到其他方法，它們知道如何與之交互。但是如果我們想改變容器的實際工作方式，就需要使用繼承。例如，如果我們想確保列表中的每一項都是恰好有5個字符的字符串，我們需要擴展列表并重寫`append()`方法來引發無效輸入的異常。我們還必須至少重寫`__setitem__(self、index、value)`，列表中的一種特殊方法，每當我們使用`x[index] = "value"`語法，都會調用這個方法。`extend()`方法也需要調整。 是的，列表是對象。所有特殊的、看起來像非面向對象的語法，一直被用在訪問列表或字典鍵，遍歷容器上，類似的任務實際上是映射到底層面向對象范式的“語法糖”。我們可能會問Python的設計者為什么這樣做。面向對象編程不總是更好嗎？這個問題很容易回答。作為一名程序員，在下面的假設例子中，哪一個更容易閱讀？哪一個需要更少的打字。 ``` c = a + b c = a.add(b) l[0] = 5 l.setitem(0, 5) d[key] = value d.setitem(key, value) for x in alist: #do something with x it = alist.iterator() while it.has_next(): x = it.next() #do something with x ``` 高亮部分顯示了面向對象的代碼可能是什么樣子（實際上，這些方法實際上以關聯對象的特殊雙下劃線方法形式存在著)。Python程序員同意非面向對象語法更容易讀和寫。然而，前面所有的Python語法都映射到“語法糖”背后面向對象的方法。這些方法有特殊的名稱（前后加雙下劃線）來提醒我們有更好的語法糖。然而，它給了我們重寫這些行為的方法。例如，我們可以生成一個特殊的整數，當我們將兩個整數相加時，該整數總是返回0： ``` class SillyInt(int): def __add__(self, num): return 0 ``` 誠然，這是一件極其奇怪的事情，但它完美地說明了面向對象的原則在起作用： ``` >>> a = SillyInt(1) >>> b = SillyInt(2) >>> a + b 0 ``` `__add__`方法最棒的一點是，我們可以將它添加到任何我們寫的類中，如果我們在該類的實例上使用+運算符，該方法將被調用。例如，字符串、元組和列表連接就是這樣工作的。 所有的特殊方法都是如此。如果我們想在一個自定義對象`myobj`中使用`x`，我們提供 `__contains__`。如果我們想`myobj[i] = value` ，我們提供 `__setitem__` 方法，如果我們想使用`somethine = myobj[i]`，我們提供 `__getitem__` 。 列表類中有33種特殊方法。我們可以使用`dir`函數來查看所有內容: ``` >>> dir(list) ['__add__', '__class__', '__contains__', '__delattr__','__delitem__', '__doc__', '__eq__', '__format__', '__ge__', '__getattribute__', '__ getitem__', '__gt__', '__hash__', '__iadd__', '__imul__', '__init__', '__iter__', '__le__', '__len__', '__lt__', '__mul__', '__ne__', '__ new__', '__reduce__', '__reduce_ex__', '__repr__', '__reversed__', '__rmul__', '__setattr__', '__setitem__', '__sizeof__', '__str__', '__ subclasshook__', 'append', 'count', 'extend', 'index', 'insert', 'pop', 'remove', 'reverse', 'sort' ``` 此外，如果我們需要關于這些方法如何工作的附加信息，我們可以使用`help`函數： ``` >>> help(list.__add__) Help on wrapper_descriptor: __add__(self, value, /) Return self+value. ``` 加號運算符將連接兩個列表。我們沒有空間討論所有本書中可用的特殊功能，但現在你可以`dir`和`help`探索所有功能。官方在線 Python 參考(https://docs.python.org/3/)也有很多有用的信息。尤其專注` collections`模塊中討論的抽象基類。 所以，回到我們何時使用組合或繼承的早期觀點：如果我們需要改變類中的任何方法——包括特殊的方法——我們當然需要使用繼承。如果我們使用組合，我們將寫一些方法進行驗證或修改，然后調用者使用這些方法，但是沒有什么可以阻止他們直接訪問屬性。他們可以在我們的列表中插入一個沒有5個字符的項目，這可能會混淆列表中的其他方法。 通常，擴展內置數據類型的需求表明我們正在使用錯誤的數據類型。情況并非總是如此，但如果我們想擴展一個內置類型，我們應該仔細考慮是否有其他更合適的數據結構。 例如，考慮創建一個能記住鍵插入順序的字典。一種方法是保留一個有序鍵列表，存儲在`dict`的一個特殊派生子類中。然后我們可以重寫`keys`、`values`、`__iter__`、`iterm`方法，按順序返回所有內容。當然，我們還得覆蓋`__setitem__`和`setdefault`以保持我們的列表是最新的。有可能是需要重寫其他方法，以保持`dir(dict)`輸出列表和字典一致（記住`clear`和`__delitem__`，以跟蹤被移除的項目），但是在這個例子中我們不擔心它們。 所以我們將擴展`dict`并添加一個有序鍵列表。微不足道，但是我們在哪里創建實際的列表？我們可以將它包含在`__init__`方法中，這很好，但是我們不能保證任何子類都會調用這個初始化方法。還記得我們在第2章“Python中的對象”討論的`__new__`方法嗎？我說它通常只在非常特殊的情況下有用。這就是其中一個特殊情況。我們知道`__new__`將被僅調用一次，我們可以一直在類的新實例上創建一個列表。記住這一點，這里是我們完整的排序詞典： ``` from collections import KeysView, ItemsView, ValuesView class DictSorted(dict): def __new__(*args, **kwargs): new_dict = dict.__new__(*args, **kwargs) new_dict.ordered_keys = [] return new_dict def __setitem__(self, key, value): '''self[key] = value syntax''' if key not in self.ordered_keys: self.ordered_keys.append(key) super().__setitem__(key, value) def setdefault(self, key, value): if key not in self.ordered_keys: self.ordered_keys.append(key) return super().setdefault(key, value) def keys(self): return KeysView(self) def values(self): return ValuesView(self) def items(self): return ItemsView(self) def __iter__(self): '''for x in self syntax''' return self.ordered_keys.__iter__() ``` `__new__`方法創建一個新詞典，然后在對象上面放一個空列表。我們不覆蓋`__init__`，因為默認實現是有效的（實際上，只有當我們初始化一個空的字典排序對象時，這才是正確的，這是標準的行為。如果我們想`dict`構造函數支持能接受字典或元組列表的其他變體，我們需要修改 `__init__`來更新我們的已排序鍵列表）。兩種設置項目的方法非常相似；它們都更新了鍵列表，但前提是之前沒有添加該項目。我們不想列表存在重復，但是我們不能在這里使用集合；集合是無序的！ `keys`、`items`、`values`方法都將視圖返回到字典中。collections庫在字典上提供三個只讀視圖對象；它們使用 `__iter__`方法循環遍歷鍵，然后使用`__getitem__`（我們不需要重寫）來檢索值。所以，我們只需要定義我們自定義`__iter__`方法使這三個視圖工作。你可能想超類會使用多態正確地創建這些視圖，但是如果我們不重寫這三種方法，它們將不返回正確排序的視圖。 最后，`__iter__`方法是真正特殊的方法；它確保如果我們循環字典的鍵（用`for ... in`語法），按正確的順序返回鍵值。它通過返回ordered _ keys列表的`__iter__`來實現這一點，該列表返回一個迭代器對象，它和我們在列表上使用`for ... in `是一樣的。因為`ordered _ keys`是所有可用鍵的列表（由于我們覆蓋了其他方法），這也是字典的正確迭代器對象。 讓我們來看看這些方法中的一些，并與普通字典進行比較: ``` >>> ds = DictSorted() >>> d = {} >>> ds['a'] = 1 >>> ds['b'] = 2 >>> ds.setdefault('c', 3) 3 >>> d['a'] = 1 >>> d['b'] = 2 >>> d.setdefault('c', 3) 3 >>> for k,v in ds.items(): ... print(k,v) ... a 1 b 2 c 3 >>> for k,v in d.items(): ... print(k,v) ... a 1 c 3 b 2 ``` 啊，我們的字典分類了，而普通的字典沒有。開心！ > 如果你想在生產中使用這個類，你必須重寫其他幾種特殊的方法使得鍵在所有的實例中是最新的。但是，你不需要這樣做；這個類的功能已在Python中提供，使用`collections`模塊中的`OrderedDict`對象。嘗試從`collections`中導入類，并使用`help(OrderedDict)`了解更多信息。 ## 隊列隊列是特殊的數據結構，因為像集合一樣，它們的功能可以完全用列表來處理。然而，盡管列表是用途極其廣泛的通用工具，對于容器操作，它們有時不是最有效的數據結構。如果你的程序使用的是小數據集（多達數百甚至更多當今處理器上的數千個元素），那么列表可能會覆蓋你的用例。但是，如果你需要將數據擴展到數百萬，您可能需要一個更有效的容器來滿足你的特定用例。因此，Python提供了三個隊列數據結構的類型，取決于你正在尋找的訪問類型。三者都使用相同的API，但是行為和數據結構都不同。 然而，在我們開始使用隊列之前，先考慮列表數據結構。Python列表是許多用例中是最有利的數據結構： * 它們支持對列表中任何元素的高效隨機訪問 * 它們有嚴格的元素排序 * 它們高效地支持追加操作但是，如果你要在任何地方插入元素，而不是在列表尾部（尤其是如果在列表開頭插入），列表會變慢。正如我們在上一節集合中討論的那樣，它們檢查列表中是否存在某元素的速度也很慢，還有搜索也是一樣。按照排序的順序存儲數據或對數據重新排序也是很低效率的。 讓我們看看Python隊列模塊提供的三種類型的容器。 ### FIFO隊列 FIFO代表先進先出，代表“隊列”定義最普遍的理解。想象一行人在銀行或收銀機排隊。第一個進入隊伍的人首先得到服務，第二個進入隊伍的人接著得到服務，如果一個新人想要獲得服務，他們得加入排隊等候輪到他們。 Python`Queue`類就是這樣。它通常被用作一種通信媒介，當一個或多個對象產生數據而一個或多個其他對象以某種方式消耗這些數據，可能速度不同。想想一個消息應用，它從網絡接收消息，但每次只能給用戶顯示一條消息。其他消息可以按接收順序緩沖在隊列中。FIFO隊列在這種并發應用中被大量使用。（我們將在第12章“測試面向對象的程序”中詳細討論并發性。) 當你不需要訪問任何數據結構的任何數據時，除下要訪問下一個要消費的對象之外，`Queue`類是一個很好的選擇。為此使用列表是效率較低的，因為如果在列表的開頭插入數據（或移除數據），需要歷遍列表中的每一個元素。 隊列有一個非常簡單的API。`Queue`可以有“無限”（直到計算機內存不足）的容量，但是它通常被限制在某個最大值。主要方法是`put()`和`get()`，它們將元素添加到的后面，就像排隊，然后從前面依次把它們拿回來。這兩種方法接受可選參數來控制如果操作沒有完成會發生什么，因為隊列要么是空的（無法獲取），要么就是滿的（無法加入）。默認值行為是阻塞或無所事事地等待，直到隊列對象有可用的數據或空間來繼續進行。你也可以拋出異常，代替傳遞`block=False`參數。或者你可以在引發異常之前讓它等一段時間，通過傳遞一個超時`timeout`參數。 該類還具有檢查隊列是滿`full()` 或空`empty()`的方法，并且有幾個額外的方法來處理并發訪問，我們不會在這里討論。以下是演示這些原則的互動會議： ``` >>> from queue import Queue >>> lineup = Queue(maxsize=3) >>> lineup.get(block=False) Traceback (most recent call last): File "<ipython-input-5-a1c8d8492c59>", line 1, in <module> lineup.get(block=False) File "/usr/lib64/python3.3/queue.py", line 164, in get raise Empty queue.Empty >>> lineup.put("one") >>> lineup.put("two") >>> lineup.put("three") >>> lineup.put("four", timeout=1) Traceback (most recent call last): File "<ipython-input-9-4b9db399883d>", line 1, in <module> lineup.put("four", timeout=1) File "/usr/lib64/python3.3/queue.py", line 144, in put raise Full queue.Full >>> lineup.full() True >>> lineup.get() 'one' >>> lineup.get() 'two' >>> lineup.get() 'three' >>> lineup.empty() True ``` 在語法糖之下，Python使用`collections.deque`數據結構實現隊列。Deques是高級數據結構，允許有效訪問集合的兩端。它提供了比Queue更靈活的接口。如果你想用它做更多的實驗，請參考Python文檔。 ### LIFO隊列 LIFO后進先出隊列更常被稱為**堆棧**。想象一堆紙，你只能訪問最上面的紙。你可以在最上面再放一張紙，使它成為新的最上面的紙，或者你可以把最上面的紙拿開，露出下面的那張。 傳統上，棧上的操作被命名為推送和彈出，但是Python隊列模塊使用與FIFO隊列完全相同的應用編程接口：`put()`和`get()`。然而，在LIFO隊列中，這些方法在堆棧的“頂部”操作，而不是在隊列的前面和后面。這是多態性的一個很好的例子。如果你看看Python標準庫中的隊列源代碼，你會發現有一個超類包含FIFO和LIFO隊列的子類，兩個子類在少數關鍵操作非常不同的（LIFO在堆棧頂部操作，FIFO在deque實例的前面和后面操作）。 下面是LIFO隊列的一個例子： ``` >>> from queue import LifoQueue >>> stack = LifoQueue(maxsize=3) >>> stack.put("one") >>> stack.put("two") >>> stack.put("three") >>> stack.put("four", block=False) Traceback (most recent call last): File "<ipython-input-21-5473b359e5a8>", line 1, in <module> stack.put("four", block=False) File "/usr/lib64/python3.3/queue.py", line 133, in put raise Full queue.Full >>> stack.get() 'three' >>> stack.get() 'two' >>> stack.get() 'one' >>> stack.empty() True >>> stack.get(timeout=1) Traceback (most recent call last): File "<ipython-input-26-28e084a84a10>", line 1, in <module> stack.get(timeout=1) File "/usr/lib64/python3.3/queue.py", line 175, in get raise Empty queue.Empty ``` 你可能想知道為什么不能標準列表使用`append()`和`pop() `。坦白地說，那可能是我會做的。我很少有機會在生產代碼中使用`LifoQueue`類。處理列表的末尾是一個有效操作；事實上，列表如此有效，以至于`LifoQueue`隊列是建在列表之上的！ 你可能更希望使用`LifoQueue`而不是列表。最重要的一點是`LifoQueue`支持干凈的來自多個線程并發訪問。如果在并發設置中你需要類似堆棧的行為，你應該把列表留在家里。其次，`LifoQueue`強制實施堆棧接口。你不會無意中將值插入`LifoQueue`隊列中的錯誤位置，例如（盡管，作為一個練習，你可以完全有意識地想出如何做到這一點）。 ### 優先級隊列優先級隊列實施了與之前隊列非常不同的排序方式。同樣，它們遵循完全相同的`get()`和`put()`API，但是不是依賴物品到達的順序來決定它們應該在什么時候返回，而是返回最“重要”的項目。按照慣例，最重要的是，或者最高優先級項目是使用小于運算符排序的最低項目。 一個常見的約定是在優先級隊列中存儲元組，其中元組中第一個元素是該元素的優先級，第二個元素是數據。另一個常見的范例是實現`__lt__`方法，正如我們在這章前面討論的那樣。在隊列中具有相同優先級的多個元素是完全可以接受的，盡管不能保證哪一個會先返回。 例如，搜索引擎在爬取最不可能被搜索到的網站之前，可以使用優先級隊列來確保它獲得最流行網頁的最新內容。產品推薦工具可以使用它來顯示信息關于排名最高的產品，同時仍然加載排名較低的數據。 請注意，優先級隊列將始終返回當前隊列最重要的元素。如果隊列為空，`get()`方法將阻塞（默認情況下)，但如果隊列中有元素，它將不會阻塞并等待更高優先級的元素被添加。隊列對沒有被添加的元素一無所知（或者甚至是先前已經被提取的元素），而僅根據隊列的當前內容做出決定。 下面交互式會話顯示了正在運行的優先級隊列，使用元組作為權重確定處理項目的順序： ``` >>> heap.put((3, "three")) >>> heap.put((4, "four")) >>> heap.put((1, "one") ) >>> heap.put((2, "two")) >>> heap.put((5, "five"), block=False) Traceback (most recent call last): File "<ipython-input-23-d4209db364ed>", line 1, in <module> heap.put((5, "five"), block=False) File "/usr/lib64/python3.3/queue.py", line 133, in put raise Full Full >>> while not heap.empty(): print(heap.get()) (1, 'one') (2, 'two') (3, 'three') (4, 'four') ``` 優先級隊列幾乎普遍使用堆數據結構來實現。Python的實現利用`heapq`模塊有效地在普通列表內部存儲堆。你可以看有關堆的算法和數據結構的教科書，以獲得更多的信息，我們將不再這里提及其他迷人的結構了。不管數據結構是什么，都可以使用面向對象的原則包裝相關的算法（行為），例如`heapq`模塊中提供的算法，圍繞著它們在計算機內存中構建的數據，就像`queue`模塊已經代表我們在標準庫中完成了的工作。` ## 個案研究為了將所有東西聯系在一起，我們將編寫一個簡單的鏈接收集器，它將訪問一個網站，并收集它在該網站中存在的每個頁面上的每個鏈接。在我們開始之前，不過，我們需要一些測試數據來處理。只需編寫一些超文本標記語言文件要使用彼此之間以及到互聯網上其他站點容器鏈接，像這樣: ``` <html> <body> <a href="contact.html">Contact us</a> <a href="blog.html">Blog</a> <a href="esme.html">My Dog</a> <a href="/hobbies.html">Some hobbies</a> <a href="/contact.html">Contact AGAIN</a> <a href="http://www.archlinux.org/">Favorite OS</a> </body> </html> ``` 說出index.html文件中的一個，這樣當頁面被提供時它會首先出現。確保其他文件存在，并保持事情的復雜性，以便有很多他們之間的聯系。本章的例子包括一個名為 case_study_serve(現存最爛的個人網站之一！)如果你我寧愿不自己設計。現在，通過輸入包含所有這些內容的目錄來啟動一個簡單的網絡服務器文件并運行以下命令: ``` python3 -m http.server ``` 這將啟動在端口8000上運行的服務器；你可以看到你制作的頁面請訪問您的web瀏覽器中的http://localhost:8000/。 > 我懷疑任何人都可以用更少的工作建立并運行一個網站！永遠不要讓別人說，“你不能用蟒蛇輕易做到這一點。” 目標是向我們的收集器傳遞該站點的基本網址(在這種情況下:http:// localhost:8000/)，并讓它創建一個包含站點上每個唯一鏈接的列表。我們需要考慮三種類型的網址(鏈接到外部網站以http://開頭，絕對內部鏈接，以/字符開頭，和相對聯系，對于其他一切)。我們還需要注意頁面可能鏈接到彼此循環；我們需要確保我們不會多次處理同一個頁面時代，否則它可能永遠不會結束。隨著所有這些獨特性的繼續，聽起來我們需要一些器械包。在開始之前，讓我們先從基礎開始。我們需要連接什么代碼并解析該頁面中的所有鏈接？ ``` from urllib.request import urlopen from urllib.parse import urlparse import re import sys LINK_REGEX = re.compile( "<a [^>]*href=['\"]([^'\"]+)['\"][^>]*>") class LinkCollector: def __init__(self, url): self.url = "" + urlparse(url).netloc def collect_links(self, path="/"): full_url = self.url + path page = str(urlopen(full_url).read()) links = LINK_REGEX.findall(page) print(links) if __name__ == "__main__": LinkCollector(sys.argv[1]).collect_links() ``` 考慮到它在做什么，這是一小段代碼。它連接到中的服務器命令行上傳遞的參數下載頁面，并提取所有頁面上的鏈接。__init__方法使用urlparse函數僅提取網址中的主機名；所以即使我們傳入http://localhost:8000/some/page。 html，它仍將運行在主機的頂層http://localhost:8000/。這有道理，因為我們想收集網站上的所有鏈接，盡管它假設每一頁都通過一些鏈接序列連接到索引。 collect_links方法連接到指定頁面并從其下載服務器，并使用正則表達式查找頁面中的所有鏈接。常規表達式是一個非常強大的字符串處理工具。不幸的是，他們學習曲線陡峭；如果你以前沒有用過，我強烈推薦研究關于這個主題的所有書籍或網站。如果你不認為他們值得知道的是，嘗試在沒有它們的情況下編寫前面的代碼，你將會改變你的思想。該示例還在collect_links方法的中間停止打印值鏈接。這是我們編寫程序時測試程序的一種常見方式:停止并輸出確保它是我們期望的價值。以下是它為我們的示例輸出的內容: ``` ['contact.html', 'blog.html', 'esme.html', '/hobbies.html', '/contact.html', 'http://www.archlinux.org/'] ``` 現在我們在第一頁收集了所有的鏈接。我們能做什么是嗎？我們不能只將鏈接放入一個集合中來刪除重復項，因為鏈接可能相對的或絕對的。例如，contact.html和/contact.html指向同一頁。所以我們應該做的第一件事是將所有鏈接規范化到它們的完整網址，包括主機名和相對路徑。我們可以通過添加一個規范化的網址來做到這一點方法到我們的對象: ``` def normalize_url(self, path, link): if link.startswith("http://"): return link elif link.startswith("/"): return self.url + link else: return self.url + path.rpartition( '/')[0] + '/' + link ``` 此方法將每個網址轉換為一個完整的地址，其中包括協議和主機名。現在，兩個聯系人頁面具有相同的值，我們可以存儲它們一套。我們必須修改__init__來創建集合，并收集_鏈接來放置所有的鏈接。然后，我們將不得不訪問所有非外部鏈接并收集它們。但是等等分鐘；如果我們這樣做，當我們遇到同一頁兩次？看起來我們實際上需要兩套:一套收集的鏈接和一組訪問過的鏈接。這表明我們明智地選擇了一套代表我們的數據；我們知道當我們操作的時候布景是最有用的不止一個。讓我們設置這些: ``` class LinkCollector: def __init__(self, url): self.url = "http://+" + urlparse(url).netloc self.collected_links = set() self.visited_links = set() def collect_links(self, path="/"): full_url = self.url + path self.visited_links.add(full_url) page = str(urlopen(full_url).read()) links = LINK_REGEX.findall(page) links = {self.normalize_url(path, link ) for link in links} self.collected_links = links.union( self.collected_links) unvisited_links = links.difference( self.visited_links) print(links, self.visited_links, self.collected_links, unvisited_links) ``` 創建規范化鏈接列表的行使用集合理解，否不同于列表理解，除了結果是一組值。我們會的下一章將詳細介紹這些內容。該方法再次停止打印當前的值，所以我們可以驗證我們沒有混淆我們的集合，并且不同的是我們想要調用的收集未訪問鏈接的方法。然后我們可以添加幾行代碼，循環遍歷所有未訪問的鏈接，并添加他們也來收藏: ``` for link in unvisited_links: if link.startswith(self.url): self.collect_links(urlparse(link).path) ``` if聲明確保我們只從一個網站收集鏈接；我們我不想離開并收集互聯網上所有頁面的所有鏈接(除非我們是谷歌或互聯網檔案館！)。如果我們修改程序輸出收集到的鏈接，我們可以看到它似乎已經收集了所有鏈接: ``` if __name__ == "__main__": collector = LinkCollector(sys.argv[1]) collector.collect_links() for link in collector.collected_links: print(link) ``` 它顯示我們收集到的所有鏈接，而且只顯示一次，盡管我的示例中的頁面相互鏈接了多次: ``` $ python3 link_collector.py http://localhost:8000 http://localhost:8000/ http://en.wikipedia.org/wiki/Cavalier_King_Charles_Spaniel http://beluminousyoga.com http://archlinux.me/dusty/ http://localhost:8000/blog.html http://ccphillips.net/ http://localhost:8000/contact.html http://localhost:8000/taichi.html http://www.archlinux.org/ http://localhost:8000/esme.html http://localhost:8000/hobbies.html ``` 即使它收集到外部頁面的鏈接，它也不會從任何頁面收集鏈接我們鏈接的外部頁面。如果我們想收集，這是一個很棒的小程序網站中的所有鏈接。但是它并沒有給我構建一個站點地圖；它會告訴我我有哪些頁面，但不會告訴我哪些頁面鏈接到其他頁面頁數。如果我們想這樣做，我們就必須做一些修改。我們應該做的第一件事是查看我們的數據結構。收集的鏈接集已經不起作用了；我們想知道哪些鏈接與哪些鏈接相關聯頁數。那么，我們能做的第一件事就是把這個集合變成一個集合字典我們瀏覽的每一頁。字典鍵將代表完全相同的數據目前在片場。這些值將是該頁面上所有鏈接的集合。這是變化: ``` from urllib.request import urlopen from urllib.parse import urlparse import re import sys LINK_REGEX = re.compile( "<a [^>]*href=['\"]([^'\"]+)['\"][^>]*>") class LinkCollector: def __init__(self, url): self.url = "http://%s" % urlparse(url).netloc self.collected_links = {} self.visited_links = set() def collect_links(self, path="/"): full_url = self.url + path self.visited_links.add(full_url) page = str(urlopen(full_url).read()) links = LINK_REGEX.findall(page) links = {self.normalize_url(path, link ) for link in links} self.collected_links[full_url] = links for link in links: self.collected_links.setdefault(link, set()) unvisited_links = links.difference( self.visited_links) for link in unvisited_links: if link.startswith(self.url): self.collect_links(urlparse(link).path) def normalize_url(self, path, link): if link.startswith("http://"): return link elif link.startswith("/"): return self.url + link else: return self.url + path.rpartition('/' )[0] + '/' + link if __name__ == "__main__": collector = LinkCollector(sys.argv[1]) collector.collect_links() for link, item in collector.collected_links.items(): print("{}: {}".format(link, item)) ``` 這是一個驚人的小變化；最初創建兩組并集的線具有替換為更新字典的三行。第一個簡單地告訴我們字典為那一頁收集的鏈接是什么。第二個創建一個空的為字典中尚未添加到字典中的任何項目設置，使用setdefault。結果是一個包含所有鏈接作為關鍵字的字典，映射到所有內部鏈接的鏈接集，以及外部鏈接的空集。最后，我們可以使用隊列來存儲，而不是遞歸調用collect_links 尚未處理的鏈接。這個實現不支持它，但是這將是創建多線程版本的良好的第一步并行處理多個請求以節省時間。 ``` from urllib.request import urlopen from urllib.parse import urlparse import re import sys from queue import Queue LINK_REGEX = re.compile("<a [^>]*href=['\"]([^'\"]+)['\"][^>]*>") class LinkCollector: def __init__(self, url): self.url = "http://%s" % urlparse(url).netloc self.collected_links = {} self.visited_links = set() def collect_links(self): queue = Queue() queue.put(self.url) while not queue.empty(): url = queue.get().rstrip('/') self.visited_links.add(url) page = str(urlopen(url).read()) links = LINK_REGEX.findall(page) links = { self.normalize_url(urlparse(url).path, link) for link in links } self.collected_links[url] = links for link in links: self.collected_links.setdefault(link, set()) unvisited_links = links.difference(self.visited_links) for link in unvisited_links: if link.startswith(self.url): queue.put(link) def normalize_url(self, path, link): if link.startswith("http://"): return link.rstrip('/') elif link.startswith("/"): return self.url + link.rstrip('/') else: return self.url + path.rpartition('/')[0] + '/' + link. rstrip('/') if __name__ == "__main__": collector = LinkCollector(sys.argv[1]) collector.collect_links() for link, item in collector.collected_links.items(): print("%s: %s" % (link, item)) ``` 我不得不手動刪除normalize_url方法中的任何尾隨斜杠刪除此版本代碼中的重復項。因為最終結果是一個未排序的字典，所以對順序沒有限制鏈接應該在中處理。因此，我們可以很容易地使用這里是一個后進先出隊列，而不是隊列。優先級隊列可能不會很有意義，因為在這種情況下，沒有明顯的優先級賦予鏈接。 ## 摘要我們已經討論了幾個內置的數據結構，并試圖理解如何為特定應用選擇一個。有時候，我們能做的最好的事情就是創建一個新的對象類，但通常，其中一個內置對象正好提供了我們需要的東西。如果沒有，我們總是可以使用繼承或組合來使它們適應我們的用例。我們甚至可以覆蓋特殊方法來完全改變行為內置語法。在下一章中，我們將討論如何集成Python的面向對象和非面向對象方面。一路上，我們會發現它更面向對象比第一眼看到的還多！