第十一章字典 · Think Python

# 第十一章字典本章要講的內容是另外一種內置的類型，叫字典。字典是 Python 最有特色的功能之一；使用字典能構建出很多高效率又很優雅的算法。 ## 11.1 字典是一種映射字典就像是一個列表一樣，但更加泛化了，是列表概念的推廣。在列表里面，索引必須是整數；而在字典里面，你可以用幾乎任何類型來做索引了。（譯者注：從字符串 string，到列表 list，再到字典 dictionary，Python 這個變量類型就是一種泛化的過程，內容在逐步推廣，適用范圍更大了，這里大家一定要對泛化好好理解一下，以后自己寫類的時候很有用。）字典包括一系列的索引，不過就已經不叫索引了，而是叫鍵，然后還對應著一個個值，就叫鍵值。每個鍵對應著各自的一個單獨的鍵值。這種鍵和鍵值的對應關系也叫鍵值對，有時候也叫項。（譯者注：計算機科學上很多內容都是對數學的應用，大家真應該加油學數學啊。）用數學語言來說，一個字典就代表了從鍵到鍵值的一種映射關系，所以你也可以說每個鍵映射到一個鍵值。舉例來說，我們可以建立一個從英語單詞映射到西班牙語單詞的字典，這樣鍵和簡直就都是字符串了。 dict 這個函數創建一個沒有項目的空字典。因為 dict 似乎內置函數的名字了，所以你應該避免用來做變量名。 ```py >>> eng2sp = dict() >>> eng2sp {} ``` 大括號，也叫花括號，就是{}，代表了一個空字典。要在字典里面加項，可以使用方括號： ```py >>> eng2sp['one'] = 'uno' ``` 這一行代碼建立了一個項，這個項映射了鍵 'one' 到鍵值 'uno'。如果我們再來打印輸出一下這個字典，就會看到里面有這樣一個鍵值對了，鍵值對中間用冒號隔開了： ```py >>> eng2sp {'one': 'uno'} ``` 這種輸出的格式也可以用來輸入。比如你可以這樣建立一個有三個項的字典： ```py >>> eng2sp = {'one': 'uno', 'two': 'dos', 'three': 'tres'} ``` 再來輸出一下，你就能看到字典建好了，但順序不一樣： ```py >>> eng2sp {'one': 'uno', 'three': 'tres', 'two': 'dos'} ``` 這些鍵值對的順序不一樣了。如果你在你電腦上測試上面這段代碼，你得到的結果也可能不一樣，實際上，字典中的項的順序是不確定的。但者其實也不要緊，因為字典里面的元素并不是用整數索引來排列的。所以你就可以直接用鍵來查找對應的鍵值： ```py >>> eng2sp['two'] 'dos' ``` 鍵'two'總會映射到鍵值'dos'，所以項的排列順序并不要緊。如果你字典中沒有你指定的鍵，你就得到如下提示： ```py >>> eng2sp['four'] KeyError: 'four' ``` len 函數也可以用在字典上；它會返回鍵值對的數目： ```py >>> len(eng2sp) 3 ``` in 運算符也適用于字典；你可以用它來判斷某個鍵是不是存在于字典中（是判斷鍵，不能判斷鍵值）。 ```py >>> 'one' in eng2sp True >>> 'uno' in eng2sp False ``` 要判斷鍵值是否在字典中，你就要用到 values 方法，這個方法會把鍵值返回，然后用 in 判斷就可以了： ```py >>> vals = eng2sp.values() >>> 'uno' in vals True ``` in 運算符在字典中和列表中有不同的算法了。對列表來說，它就按照順序搜索列表中的每一個元素，如 8.6 所示。隨著列表越來越長了，這種搜索就消耗更多的時間，才能找到正確的位置。而對字典來說，Python 使用了一種叫做哈希表的算法，這就有一種很厲害的特性：in 運算符在對字典來使用的時候無論字典規模多大，無論里面的項有多少個，花費的時間都是基本一樣的。我在 13.4 會解釋一下其實現原理，不過你要多學幾章之后才能理解對此的解釋。 ## 11.2 用字典作為計數器假設你得到一個字符串，然后你想要查一下每個字母出現了多少次。你可以通過一下方法來實現： 1. 你可以建立 26 個變量，每一個代表一個字母。然后你遍歷整個字符串，每個字母的個數都累加到對應的計數器里面，可能會用到分支條件判斷。 2. 你可以建立一個有 26 個元素的列表。然后你把每個字母轉換成一個數字（用內置的 ord 函數），用這些數字作為這個列表的索引，然后累加相應的計數器。 3. 你可以建立一個字典，用字母作為鍵，用該字母出現的次數作為對應的鍵值。第一次遇到一個字母，就在字典里面加一個項。此后再遇到這個字母，就每次在已有的項上進行累加即可。上面這些方法進行的都是一樣的運算，但它們各自計算的實現方法是不同的。實現是一種運算進行的方式；有的實現要比其他的更好一些。比如用字典來實現的優勢就是我們不需要實現知道字符串中有哪些字母，只需要為其中存在的字母來提供存儲空間。下面是代碼樣例： ```py def histogram(s): d = dict() for c in s: if c not in d: d[c] = 1 else: d[c] += 1 return d ``` 函數的名字為 histogram，這是一個統計學術語，意思是計數（或者頻次）的集合。函數的第一行創建了一個空字典。for 循環遍歷了整個字符串、每次經過循環的時候，如果字符 c 沒有在字典中，就在字典中創建一個新的項，鍵為 c，初始值為 1（因為這就算遇到一次了）。如果 c 已經存在于字典中了，就對 d[c]進行一下累加。下面是使用的樣例： ```py >>> h = histogram('brontosaurus') >>> h {'a': 1, 'b': 1, 'o': 2, 'n': 1, 's': 2, 'r': 2, 'u': 2, 't': 1} ``` histogram 的結果表明字母 a 和 b 出現了一次，o 出現了兩次，等等。字典有一個方法，叫做 get，接收一個鍵和一個默認值。如果這個鍵在字典中存在，get 就會返回對應的鍵值；如果不存在，它就會返回這個默認值。比如： ```py >>> h = histogram('a') >>> h {'a': 1} >>> h.get('a', 0) 1 >>> h.get('b', 0) 0 ``` 做個練習，用 get 這個方法，來縮寫一下 histogram 這個函數，讓它更簡潔些。可以去掉那些 if 語句。 ## 11.3 循環與字典如果你在 for 語句里面用字典，程序會遍歷字典中的所有鍵。例如下面這個 print_hist 函數就輸出其中的每一個鍵與對應的鍵值： ```py def print_hist(h): for c in h: print(c, h[c]) ``` 輸出如下所示： ```py >>> h = histogram('parrot') >>> print_hist(h) a 1 p 1 r 2 t 1 o 1 ``` 明顯這些鍵的輸出并沒有特定順序。字典有一個內置的叫做 keys 的方法，返回字典中的所有鍵成一個列表，以不確定的順序。做個練習，修改一下上面這個 print_hist 函數，讓它按照字母表的順序輸出鍵和鍵值。 ## 11.4 逆向查找給定一個字典 d，以及一個鍵 k，很容易找到對應的鍵值 v=d[k]。這個操作就叫查找。但如果你有鍵值 v 而要找鍵 k 呢？你有兩個問題了：首先，可能有不止一個鍵的鍵值為 v。根據應用的不同，你也許可以從中選一個，或者就可以把所有對應的鍵做成一個列表。其次，沒有一種簡單的語法能實現這樣一種逆向查找；你必須搜索一下。 ```py def reverse_lookup(d, v): for k in d: if d[k] == v: return k raise LookupError() ``` 這個函數是搜索模式的另一個例子，用到了一個新的功能：raise。raise 語句會導致一個異常；在這種情況下是 LookupError，這是一個內置異常，表示查找操作失敗。如果我們運行了整個循環，就意味著 v 在字典中沒有作為鍵值出現果，所以就 raise 一個異常回去。下面是一個成功進行逆向查找的樣例： ```py >>> h = histogram('parrot') >>> k = reverse_lookup(h, 2) >>> k 'r' ``` 下面這個是一個不成功的： ```py >>> k = reverse_lookup(h, 3) Traceback (most recent call last): File "<stdin>", line 1, in <module> File "<stdin>", line 5, in reverse_lookup ValueError ``` 你自己 raise 一個異常的效果就和 Python 拋出的異常是一樣的：程序會輸出一個追溯以及一個錯誤信息。 raise 語句可以給出詳細的錯誤信息作為可選的參數。如下所示： ```py >>> raise ValueError('value does not appear in the dictionary') Traceback (most recent call last): File "<stdin>", line 1, in ? ValueError: value does not appear in the dictionary ``` 逆向查找要比正常查找慢很多很多；如果要經常用到的話，或者字典變得很大了，程序的性能就會大打折扣。 ## 11.5 字典和列表列表可以視作字典中的值。比如給你一個字典，映射了字符與對應的頻率，你可能需要逆轉一下；也就是建立一個從頻率映射到字母的字典。因為可能有幾個字母有同樣的頻率，在這個逆轉字典中的每個值就應該是一個字母的列表。下面就是一個逆轉字典的函數： ```py def invert_dict(d): inverse = dict() for key in d: val = d[key] if val not in inverse: inverse[val] = [key] else: inverse[val].append(key) return inverse ``` 每次循環的時候，key 這個變量都得到 d 中的一個鍵，val 獲取對應的鍵值。如果 val 不在 inverse 這個字典里面，就意味著這是首次遇到它，所以就建立一個新項，然后用一個單元素集來初始化。否則就說明這個鍵值已經存在了，這樣我們就在對應的鍵的列表中添加上新的這一個鍵就可以了。下面是一個樣例： ```py >>> hist = histogram('parrot') >>> hist {'a': 1, 'p': 1, 'r': 2, 't': 1, 'o': 1} >>> inverse = invert_dict(hist) >>> inverse {1: ['a', 'p', 't', 'o'], 2: ['r']} ``` ________________________________________ ![Figure 11.1: State diagram](http://7xnq2o.com1.z0.glb.clouddn.com/ThinkPython11.1.png) Figure 11.1: State diagram. ________________________________________ 圖 11.1 為 hist 和 inverse 兩個字典的狀態圖。字典用方框表示，上方標示了類型 dict，方框內為鍵值對。如果鍵值為整數、浮點數或者字符串，就把它們放到一個方框內，不過通常我習慣把它們放到方框外面，這樣圖表看著簡單干凈。如圖所示，用字典中的鍵值組成列表，而不能用鍵。如果你要用鍵的話，就會遇到如下所示的錯誤： ```py >>> t = [1, 2, 3] >>> d = dict() >>> d[t] = 'oops' Traceback (most recent call last): File "<stdin>", line 1, in ? TypeError: list objects are unhashable ``` 我之前說過，字典是用哈希表（散列表）來實現的，這就意味著所有鍵都必須是散列的。 hash 是一個函數，接收任意一種值，然后返回一個整數。字典用這些整數來存儲和查找鍵值對，這些整數也叫做哈希值。如果鍵不可修改，系統工作正常。但如果鍵可以修改，比如是列表，就悲劇了。例如，你創建一個鍵值對的時候，Python 計算鍵的哈希值，然后存在相應的位置。如果你修改了鍵，然后在計算哈希值，就不會指向同一個位置了。這時候一個鍵就可以有兩個指向了，或者你就可能找不到某個鍵了。總之字典都不能正常工作了。這就是為什么這些鍵必須是散列的，而像列表這樣的可變類型就不行。解決這個問題的最簡單方式就是使用元組，這個我們會在下一章來學習。因為字典是可以修改的，所以不能用來做鍵，只能用來做鍵值。（譯者注：哈希表是一種散列表，相關內容譯者知道的太少，所以這段翻譯的質量大打折扣，實在抱歉。） ## 11.6 Memos 備忘如果你試過了 6.7 中提到的斐波那契數列，你估計會發現隨著參數增大，函數運行的時間也變長了。另外，運行時間的增長很顯著。要理解這是怎么回事，就要參考一下圖 11.2，圖中展示了當 n=4 的時候函數調用的情況。 ________________________________________ ![Figure 11.2: Call graph](http://7xnq2o.com1.z0.glb.clouddn.com/ThinkPython11.2.png) Figure 11.2: Call graph. ________________________________________ 調用圖展示了一系列的函數圖框，圖框直接的連線表示了函數只見的調用關系。頂層位置函數的參數 n =4，調用了 n=3 和 n=2 兩種情況的函數。相應的 n=3 的時候要調用 n=2 和 n=1 兩種情況。依此類推。算算 fibonacci(0)和 fibonacci(1)要被調用多少次吧。這樣的解決方案是低效率的，隨著參數增大，效率就越來越低了。另外一種思路就是保存一下已經被計算過的值，然后保存在一個字典中。之前計算過的值存儲起來，這樣后續的運算中能夠使用，這就叫備忘。下面是一個用這種思路來實現的斐波那契函數： ```py known = {0:0, 1:1} def fibonacci(n): if n in known: return known[n] res = fibonacci(n-1) + fibonacci(n-2) known[n] = res return res ``` known 是一個用來保存已經計算斐波那契函數值的字典。開始項目有兩個，0 對應 0，1 對應 1，各自分別是各自的斐波那契函數值。這樣只要斐波那契函數被調用了，就會檢查 known 這個字典，如果里面有計算過的可用結果，就立即返回。不然的話就計算出新的值，并且存到字典里面，然后返回這個新計算的值。如果你運行這一個版本的斐波那契函數，你會發現比原來那個版本要快得多。 ## 11.7 全局變量在上面的例子中，known 這個字典是在函數外創建的，所以它屬于主函數內，這是一個特殊的層。在主函數中的變量也叫全局變量，因為所有函數都可以訪問這些變量。局部變量在所屬的函數結束后就消失了，而主函數在其他函數調用結束后依然還存在。一般常用全局變量作為 flag，也就是標識；比如用來判斷一個條件是否成立的布爾變量之類的。比如有的程序用名字為 verbose 的標識變量，來控制輸出內容的詳細程度： ```py verbose = True def example1(): if verbose: print('Running example1') ``` 如果你想給全局變量重新賦值，結果會很意外。下面的例子中，本來是想要追蹤確定函數是否被調用了： ```py been_called = False def example2(): been_called = True # WRONG ``` 你可以運行一下，并不報錯，只是 been_called 的值并不會變化。這個情況的原因是 example2 這個函數創建了一個新的名為 been_called 的局部變量。函數結束之后，局部變量就釋放了，并不會影響全局變量。要在函數內部來給全局變量重新賦值，必須要在使用之前聲明這個全局變量： ```py been_called = False def example2(): global been_called been_called = True ``` global 那句代碼的效果是告訴解釋器：『在這個函數內，been_called 使之全局變量；不要創建一個同名的局部變量。』下面的例子中，試圖對全局變量進行更新： ```py count = 0 def example3(): count = count + 1 # WRONG ``` 運行的話，你會得到如下提示： ```py UnboundLocalError: local variable 'count' referenced before assignment ``` （譯者注：錯誤提示的意思是未綁定局部錯誤：局部變量 count 未經賦值就被引用。） Python 會假設這個 count 是局部的，然后基于這樣的假設，你就是在寫出該變量之前就試圖讀取。這樣問題的解決方法依然就是聲稱 count 為全局變量。 ```py def example3(): global count count += 1 ``` 如果全局變量指向的是一個可修改的值，你可以無需聲明該變量就直接修改： ```py known = {0:0, 1:1} def example4(): known[2] = 1 ``` 所以你可以在全局的列表或者字典里面添加、刪除或者替換元素，但如果你要重新給這個全局變量賦值，就必須要聲明了： ```py def example5(): global known known = dict() ``` 全局變量很有用，但不能濫用，要是總修改全局變量的值，就讓程序很難調試了。 ## 11.8 調試現在數據結構逐漸復雜了，再用打印輸出和手動檢驗的方法來調試就很費勁了。下面是一些對這種復雜數據結構下的建議：縮減輸入：盡可能縮小數據的規模。如果程序要讀取一個文本文檔，而只讀前面的十行，或者用你能找到的最小規模的樣例。你可以編輯一下文件本身，或者直接修改程序來僅讀取前面的 n 行，這樣更好。如果存在錯誤了，你可以減小一下 n，一直到錯誤存在的最小的 n 值，然后再逐漸增加 n，這樣就能找到錯誤并改正了。檢查概要和類型：這回咱就不再打印檢查整個數據表，而是打印輸出數據的概要：比如字典中的項的個數，或者一個列表中的數目總和。導致運行錯誤的一種常見原因就是類型錯誤。對這類錯誤進行調試，輸出一下值的類型就可以了。寫自檢代碼：有時你也可以寫自動檢查錯誤的代碼。舉例來說，假如你計算一個列表中數字的平均值，你可以檢查一下結果是不是比列表中的最大值還大或者比最小值還小。這也叫『心智檢查』，因為是來檢查結果是否『瘋了』（譯者注：也就是錯得很荒誕的意思。）另外一種檢查方法是用兩種不同運算，然后對比結果，看看他們是否一致。后面這種叫『一致性檢查』。格式化輸出：格式化的調試輸出，更容易找到錯誤。在 6.9 的時候我們見過一個例子了。pprint 模塊內置了一個 pprint 函數，該函數能夠把內置的類型用人讀起來更容易的格式來顯示出來（pprint 就是『pretty print』的縮寫）。再次強調一下，搭建腳手架代碼的時間越長，用來調試的時間就會相應地縮短。 ## 11.9 Glossary 術語列表 mapping: A relationship in which each element of one set corresponds to an element of another set. >映射：一組數據中元素與另一組數據中元素的一一對應的關系。 dictionary: A mapping from keys to their corresponding values. >字典：從鍵到對應鍵值的映射。 key-value pair: The representation of the mapping from a key to a value. >鍵值對：有映射關系的一對鍵和對應的鍵值。 item: In a dictionary, another name for a key-value pair. >項：字典中鍵值對也叫項。 key: An object that appears in a dictionary as the first part of a key-value pair. >鍵：字典中的一個對象，鍵值對中的第一部分。 value: An object that appears in a dictionary as the second part of a key-value pair. This is more specific than our previous use of the word “value”. >鍵值：字典中的一個對象，鍵值對的第二部分。這個和之前提到的值不同，在字典使用過程中指代的是鍵值，而不是數值。 implementation: A way of performing a computation. >實現：進行計算的一種方式。 hashtable: The algorithm used to implement Python dictionaries. >哈希表：Python 實現字典的一種算法。 hash function: A function used by a hashtable to compute the location for a key. >哈希函數：哈希表使用的一種函數，能計算出一個鍵的位置。 hashable: A type that has a hash function. Immutable types like integers, floats and strings are hashable; mutable types like lists and dictionaries are not. >散列的：一種類型，有哈希函數。不可變類型比如整形、浮點數和字符串都是散列的；可變類型比如列表和字典則不是。 >（譯者注：這段我翻譯的很狗，因為術語不是很熟悉，等有空我再查查去。） lookup: A dictionary operation that takes a key and finds the corresponding value. >查找：字典操作的一種，根據已有的鍵查找對應的鍵值。 reverse lookup: A dictionary operation that takes a value and finds one or more keys that map to it. >逆向查找：字典操作的一種，根據一個鍵值找對應的一個或者多個鍵。 raise statement: A statement that (deliberately) raises an exception. >raise 語句：特地要求拋出異常的一個語句。 singleton: A list (or other sequence) with a single element. >單元素集：只含有一個單獨元素的列表或者其他序列。 call graph: A diagram that shows every frame created during the execution of a program, with an arrow from each caller to each callee. >調用圖：一種圖解，解釋程序運行過程中每一個步驟，用箭頭來來連接調用者和被調用者之間。 memo: A computed value stored to avoid unnecessary future computation. >備忘：將計算得到的值存儲起來，避免后續的額外計算。 global variable: A variable defined outside a function. Global variables can be accessed from any function. >全局變量：函數外定義的變量。全局變量能被所有函數來讀取使用。 global statement: A statement that declares a variable name global. >global 語句：聲明一個變量為全局的語句。 flag: A boolean variable used to indicate whether a condition is true. >標識：一個布爾變量，用來指示一個條件是否為真。 declaration: A statement like global that tells the interpreter something about a variable. >聲明：比如 global 這樣的語句，用來告訴解釋器變量的特征。 ## 11.10 練習 ### 練習 1 寫一個函數來讀取 words.txt 文件中的單詞，然后作為鍵存到一個字典中。鍵值是什么不要緊。然后用 in 運算符來快速檢查一個字符串是否在字典中。如果你做過第十章的練習，你可以對比一下這種實現和列表中的 in 運算符以及對折搜索的速度。 ### 練習 2 讀一下字典中 setdefault 方法的相關文檔，然后用這個方法來寫一個更精簡版本的 invert_dict 函數。 [樣例代碼](http://thinkpython2.com/code/invert_dict.py])。 ### 練習 3 用備忘的方法來改進一下第二章練習中的 Ackermann 函數，看看是不是能讓讓函數處理更大的參數。提示：不行。[樣例代碼](http://thinkpython2.com/code/ackermann_memo.py)。 ### 練習 4 如果你做過了第七章的練習，應該已經寫過一個名叫 has_duplicates 的函數了，這個函數用列表做參數，如果里面有元素出現了重復，就返回真。用字典來寫一個更快速更簡單的版本。[樣例代碼](http://thinkpython2.com/code/has_duplicates.py)。 ### 練習 5 一個詞如果翻轉順序成為另外一個詞，這兩個詞就為『翻轉詞對』（參見第五章練習的 rotate_word，譯者注：作者這個練習我沒找到。。。）。寫一個函數讀取一個單詞表，然后找到所有這樣的單詞對。[樣例代碼](http://thinkpython2.com/code/rotate_pairs.py)。 ### 練習 6 下面是一個來自[Car Talk](http://www.cartalk.com/content/puzzlers)的謎語： >這條謎語來自一個名叫 Dan O'Leary 的朋友。他最近發現一個單詞，這個單詞有一個音節，五個字母，然后有以下所述的特定性質。 >去掉第一個字母，得到的是與原詞同音異形異義詞，發音與原詞一模一樣。替換一下首字母，也就是把第一個字母放回去，然后把第二個字母去掉，得到的是另外一個這樣的同音異形異義詞。那么問題來了，這是個什么詞呢？ >現在我給你提供一個錯誤的例子。咱們先看一下五個字母的單詞，「wrack」。去掉第一個字母，得到的四個字母單詞是「R-A-C-K」。但去掉第二個字母得到的是「W-A-C-K」，這就不是前兩個詞的同音異形異義詞。（譯者注：詞義的細節就略去了，沒有太大必要。） >但這個詞至少有一個，Dan 和咱們都知道的，分別刪除前兩個字母會產生兩個同音異形異義的四個字母的單詞。問題就是，這是哪個詞？你可以用本章練習 1 的字典來檢查一個字符串是否在一個字典之中。檢查兩個單詞是不是同音異形異義詞，可以用 CMU 發音字典。可以從[這里](http://www.speech.cs.cmu.edu/cgi-bin/cmudict)或者[這里](http://thinkpython2.com/code/c06d)或者[這里](http://thinkpython2.com/code/pronounce.py)來下載，該字典提供了一個名為 read_dictionary 的函數，該函數會讀取發音詞典，然后返回一個 Python 詞典，返回的這個詞典會映射每一個單詞到描述單詞讀音的字符串。寫一個函數來找到所有滿足謎語要求的單詞。[樣例代碼](http://thinkpython2.com/code/homophone.py)。