Chapter 11 Dictionaries 字典 · Think Python 2e 中文版

# Chapter 11 Dictionaries 字典 This chapter presents another built-in type called a dictionary. Dictionaries are one of Python’s best features; they are the building blocks of many efficient and elegant algorithms. > 本章要講的內容是另外一種內置的類型，叫字典。字典是 Python 最有特色的功能之一；使用字典能構建出很多高效率又很優雅的算法。 ## 11.1 A dictionary is a mapping 字典是一種映射 A dictionary is like a list, but more general. In a list, the indices have to be integers; in a dictionary they can be (almost) any type. > 字典就像是一個列表一樣，但更加泛化了，是列表概念的推廣。在列表里面，索引必須是整數；而在字典里面，你可以用幾乎任何類型來做索引了。 > （譯者注：從字符串 string，到列表 list，再到字典 dictionary，Python 這個變量類型就是一種泛化的過程，內容在逐步推廣，適用范圍更大了，這里大家一定要對泛化好好理解一下，以后自己寫類的時候很有用。） A dictionary contains a collection of indices, which are called keys, and a collection of values. Each key is associated with a single value. The association of a key and a value is called a key-value pair or sometimes an item. > 字典包括一系列的索引，不過就已經不叫索引了，而是叫鍵，然后還對應著一個個值，就叫鍵值。每個鍵對應著各自的一個單獨的鍵值。這種鍵和鍵值的對應關系也叫鍵值對，有時候也叫項。 > （譯者注：計算機科學上很多內容都是對數學的應用，大家真應該加油學數學啊。） In mathematical language, a dictionary represents a mapping from keys to values, so you can also say that each key “maps to” a value. As an example, we’ll build a dictionary that maps from English to Spanish words, so the keys and the values are all strings. > 用數學語言來說，一個字典就代表了從鍵到鍵值的一種映射關系，所以你也可以說每個鍵映射到一個鍵值。舉例來說，我們可以建立一個從英語單詞映射到西班牙語單詞的字典，這樣鍵和簡直就都是字符串了。 The function dict creates a new dictionary with no items. Because dict is the name of a built-in function, you should avoid using it as a variable name. > dict 這個函數創建一個沒有項目的空字典。因為 dict 似乎內置函數的名字了，所以你應該避免用來做變量名。 ```Python >>> eng2sp = dict() >>> eng2sp = dict() >>> eng2sp >>> eng2sp {} ``` The squiggly-brackets, {}, represent an empty dictionary. To add items to the dictionary, you can use square brackets: > 大括號，也叫花括號，就是{}，代表了一個空字典。要在字典里面加項，可以使用方括號： ```Python >>> eng2sp['one'] = 'uno' >>> eng2sp['one'] = 'uno' ``` This line creates an item that maps from the key ’one’ to the value 'uno'. If we print the dictionary again, we see a key-value pair with a colon between the key and value: > 這一行代碼建立了一個項，這個項映射了鍵 'one' 到鍵值 'uno'。如果我們再來打印輸出一下這個字典，就會看到里面有這樣一個鍵值對了，鍵值對中間用冒號隔開了： ```Python >>> eng2sp >>> eng2sp {'one': 'uno'} ``` This output format is also an input format. For example, you can create a new dictionary with three items: > 這種輸出的格式也可以用來輸入。比如你可以這樣建立一個有三個項的字典： ```Python >>> eng2sp = {'one': 'uno', 'two': 'dos', 'three': 'tres'} >>> eng2sp = {'one': 'uno', 'two': 'dos', 'three': 'tres'} ``` But if you print eng2sp, you might be surprised: > 再來輸出一下，你就能看到字典建好了，但順序不一樣： ```Python >>> eng2sp >>> eng2sp {'one': 'uno', 'three': 'tres', 'two': 'dos'} ``` The order of the key-value pairs might not be the same. If you type the same example on your computer, you might get a different result. In general, the order of items in a dictionary is unpredictable. > 這些鍵值對的順序不一樣了。如果你在你電腦上測試上面這段代碼，你得到的結果也可能不一樣，實際上，字典中的項的順序是不確定的。 But that’s not a problem because the elements of a dictionary are never indexed with integer indices. Instead, you use the keys to look up the corresponding values: > 但者其實也不要緊，因為字典里面的元素并不是用整數索引來排列的。所以你就可以直接用鍵來查找對應的鍵值： ```Python >>> eng2sp['two'] >>> eng2sp['two'] 'dos' ``` The key ’two’ always maps to the value 'dos' so the order of the items doesn’t matter. If the key isn’t in the dictionary, you get an exception: > 鍵'two'總會映射到鍵值'dos'，所以項的排列順序并不要緊。 > 如果你字典中沒有你指定的鍵，你就得到如下提示： ```Python >>> eng2sp['four'] >>> eng2sp['four'] KeyError: 'four' ``` The len function works on dictionaries; it returns the number of key-value pairs: > len 函數也可以用在字典上；它會返回鍵值對的數目： ```Python >>> len(eng2sp) >>> len(eng2sp) 3 ``` The in operator works on dictionaries, too; it tells you whether something appears as a key in the dictionary (appearing as a value is not good enough). > in 運算符也適用于字典；你可以用它來判斷某個鍵是不是存在于字典中（是判斷鍵，不能判斷鍵值）。 ```Python >>> 'one' in eng2sp >>> 'one' in eng2sp True >>> 'uno' in eng2sp >>> 'uno' in eng2sp False ``` To see whether something appears as a value in a dictionary, you can use the method values, which returns a collection of values, and then use the in operator: > 要判斷鍵值是否在字典中，你就要用到 values 方法，這個方法會把鍵值返回，然后用 in 判斷就可以了： ```Python >>> vals = eng2sp.values() >>> vals = eng2sp.values() >>> 'uno' in vals >>> 'uno' in vals True ``` The in operator uses different algorithms for lists and dictionaries. For lists, it searches the elements of the list in order, as in Section 8.6. As the list gets longer, the search time gets longer in direct proportion. > in 運算符在字典中和列表中有不同的算法了。對列表來說，它就按照順序搜索列表中的每一個元素，如8.6所示。隨著列表越來越長了，這種搜索就消耗更多的時間，才能找到正確的位置。 For dictionaries, Python uses an algorithm called a hashtable that has a remarkable property: the in operator takes about the same amount of time no matter how many items are in the dictionary. I explain how that’s possible in Section 13.4, but the explanation might not make sense until you’ve read a few more chapters. > 而對字典來說，Python 使用了一種叫做哈希表的算法，這就有一種很厲害的特性：in 運算符在對字典來使用的時候無論字典規模多大，無論里面的項有多少個，花費的時間都是基本一樣的。我在13.4會解釋一下其實現原理，不過你要多學幾章之后才能理解對此的解釋。 ## 11.2 Dictionary as a collection of counters 用字典作為計數器 Suppose you are given a string and you want to count how many times each letter appears. There are several ways you could do it: > 假設你得到一個字符串，然后你想要查一下每個字母出現了多少次。你可以通過一下方法來實現： 1. You could create 26 variables, one for each letter of the alphabet. Then you could traverse the string and, for each character, increment the corresponding counter, probably using a chained conditional. > 你可以建立26個變量，每一個代表一個字母。然后你遍歷整個字符串，每個字母的個數都累加到對應的計數器里面，可能會用到分支條件判斷。 2. You could create a list with 26 elements. Then you could convert each character to a number (using the built-in function ord), use the number as an index into the list, and increment the appropriate counter. > 你可以建立一個有26個元素的列表。然后你把每個字母轉換成一個數字（用內置的 ord 函數），用這些數字作為這個列表的索引，然后累加相應的計數器。 3. You could create a dictionary with characters as keys and counters as the corresponding values. The first time you see a character, you would add an item to the dictionary. After that you would increment the value of an existing item. > 你可以建立一個字典，用字母作為鍵，用該字母出現的次數作為對應的鍵值。第一次遇到一個字母，就在字典里面加一個項。此后再遇到這個字母，就每次在已有的項上進行累加即可。 Each of these options performs the same computation, but each of them implements that computation in a different way. > 上面這些方法進行的都是一樣的運算，但它們各自計算的實現方法是不同的。 An implementation is a way of performing a computation; some implementations are better than others. For example, an advantage of the dictionary implementation is that we don’t have to know ahead of time which letters appear in the string and we only have to make room for the letters that do appear. Here is what the code might look like: > 實現是一種運算進行的方式；有的實現要比其他的更好一些。比如用字典來實現的優勢就是我們不需要實現知道字符串中有哪些字母，只需要為其中存在的字母來提供存儲空間。 > 下面是代碼樣例： ```Python def histogram(s): d = dict() for c in s: if c not in d: d[c] = 1 else: d[c] += 1 return d ``` The name of the function is histogram, which is a statistical term for a collection of counters (or frequencies). The first line of the function creates an empty dictionary. The for loop traverses the string. Each time through the loop, if the character c is not in the dictionary, we create a new item with key c and the initial value 1 (since we have seen this letter once). If c is already in the dictionary we increment d[c]. Here’s how it works: > 函數的名字為 histogram，這是一個統計學術語，意思是計數（或者頻次）的集合。 > 函數的第一行創建了一個空字典。for 循環遍歷了整個字符串、每次經過循環的時候，如果字符 c 沒有在字典中，就在字典中創建一個新的項，鍵為 c，初始值為1（因為這就算遇到一次了）。如果 c 已經存在于字典中了，就對 d[c]進行一下累加。 > 下面是使用的樣例： ```Python >>> h = histogram('brontosaurus') >>> h = histogram('brontosaurus') >>> h >>> h {'a': 1, 'b': 1, 'o': 2, 'n': 1, 's': 2, 'r': 2, 'u': 2, 't': 1} ``` The histogram indicates that the letters ’a’ and 'b' appear once; 'o' appears twice, and so on. Dictionaries have a method called get that takes a key and a default value. If the key appears in the dictionary, get returns the corresponding value; otherwise it returns the default value. For example: > histogram的結果表明字母a 和 b 出現了一次，o 出現了兩次，等等。 > 字典有一個方法，叫做 get，接收一個鍵和一個默認值。如果這個鍵在字典中存在，get 就會返回對應的鍵值；如果不存在，它就會返回這個默認值。比如： ```Python >>> h = histogram('a') >>> h = histogram('a') >>> h >>> h {'a': 1} >>> h.get('a', 0) >>> h.get('a', 0) 1 >>> h.get('b', 0) >>> h.get('b', 0) 0 ``` As an exercise, use get to write histogram more concisely. You should be able to eliminate the if statement. > 做個練習，用 get 這個方法，來縮寫一下 histogram 這個函數，讓它更簡潔些。可以去掉那些 if 語句。 ## 11.3 Looping and dictionaries 循環與字典 If you use a dictionary in a for statement, it traverses the keys of the dictionary. For example, print_hist prints each key and the corresponding value: > 如果你在 for 語句里面用字典，程序會遍歷字典中的所有鍵。例如下面這個 print_hist 函數就輸出其中的每一個鍵與對應的鍵值： ```Python def print_hist(h): for c in h: print(c, h[c]) ``` Here’s what the output looks like: > 輸出如下所示： ```Python >>> h = histogram('parrot') >>> h = histogram('parrot') >>> print_hist(h) >>> print_hist(h) a 1 p 1 r 2 t 1 o 1 ``` Again, the keys are in no particular order. Dictionaries have a method called keys that returns the keys of the dictionary, in no particular order, as a list. As an exercise, modify print_hist to print the keys and their values in alphabetical order. > 明顯這些鍵的輸出并沒有特定順序。字典有一個內置的叫做 keys 的方法，返回字典中的所有鍵成一個列表，以不確定的順序。做個練習，修改一下上面這個 print_hist 函數，讓它按照字母表的順序輸出鍵和鍵值。 ## 11.4 Reverse lookup 逆向查找 Given a dictionary d and a key k, it is easy to find the corresponding value v = d[k]. This operation is called a lookup. But what if you have v and you want to find k? You have two problems: first, there might be more than one key that maps to the value v. Depending on the application, you might be able to pick one, or you might have to make a list that contains all of them. Second, there is no simple syntax to do a reverse lookup; you have to search. Here is a function that takes a value and returns the first key that maps to that value: > 給定一個字典 d，以及一個鍵 k，很容易找到對應的鍵值 v=d[k]。這個操作就叫查找。 > 但如果你有鍵值 v 而要找鍵 k 呢？你有兩個問題了：首先，可能有不止一個鍵的鍵值為 v。根據應用的不同，你也許可以從中選一個，或者就可以把所有對應的鍵做成一個列表。其次，沒有一種簡單的語法能實現這樣一種逆向查找；你必須搜索一下。 ```Python def reverse_lookup(d, v): for k in d: if d[k] == v: return k raise LookupError() ``` This function is yet another example of the search pattern, but it uses a feature we haven’t seen before, raise. The raise statement causes an exception; in this case it causes a LookupError, which is a built-in exception use to indicate that a lookup operation failed. > 這個函數是搜索模式的另一個例子，用到了一個新的功能：raise。raise語句會導致一個異常；在這種情況下是 LookupError，這是一個內置異常，表示查找操作失敗。 If we get to the end of the loop, that means v doesn’t appear in the dictionary as a value, so we raise an exception. Here is an example of a successful reverse lookup: > 如果我們運行了整個循環，就意味著 v 在字典中沒有作為鍵值出現果，所以就 raise 一個異常回去。 > 下面是一個成功進行逆向查找的樣例： ```Python >>> h = histogram('parrot') >>> h = histogram('parrot') >>> k = reverse_lookup(h, 2) >>> k = reverse_lookup(h, 2) >>> k >>> k 'r' ``` And an unsuccessful one: > 下面這個是一個不成功的： ```Python >>> k = reverse_lookup(h, 3) >>> k = reverse_lookup(h, 3) Traceback (most recent call last): File "<stdin>", line 1, in <module> File "<stdin>", line 5, in reverse_lookup ValueError ``` The effect when you raise an exception is the same as when Python raises one: it prints a traceback and an error message. > 你自己 raise 一個異常的效果就和 Python 拋出的異常是一樣的：程序會輸出一個追溯以及一個錯誤信息。 The raise statement can take a detailed error message as an optional argument. For example: > raise 語句可以給出詳細的錯誤信息作為可選的參數。如下所示： ```Python >>> raise ValueError('value does not appear in the dictionary') >>> 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 ``` A reverse lookup is much slower than a forward lookup; if you have to do it often, or if the dictionary gets big, the performance of your program will suffer. > 逆向查找要比正常查找慢很多很多；如果要經常用到的話，或者字典變得很大了，程序的性能就會大打折扣。 ## 11.5 Dictionaries and lists 字典和列表 Lists can appear as values in a dictionary. For example, if you are given a dictionary that maps from letters to frequencies, you might want to invert it; that is, create a dictionary that maps from frequencies to letters. Since there might be several letters with the same frequency, each value in the inverted dictionary should be a list of letters. Here is a function that inverts a dictionary: > 列表可以視作字典中的值。比如給你一個字典，映射了字符與對應的頻率，你可能需要逆轉一下；也就是建立一個從頻率映射到字母的字典。因為可能有幾個字母有同樣的頻率，在這個逆轉字典中的每個值就應該是一個字母的列表。 > 下面就是一個逆轉字典的函數： ```Python 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 ``` Each time through the loop, key gets a key from d and val gets the corresponding value. If val is not in inverse, that means we haven’t seen it before, so we create a new item and initialize it with a singleton (a list that contains a single element). Otherwise we have seen this value before, so we append the corresponding key to the list. Here is an example: > 每次循環的時候，key這個變量都得到 d 中的一個鍵，val 獲取對應的鍵值。如果 val 不在 inverse 這個字典里面，就意味著這是首次遇到它，所以就建立一個新項，然后用一個單元素集來初始化。否則就說明這個鍵值已經存在了，這樣我們就在對應的鍵的列表中添加上新的這一個鍵就可以了。 > 下面是一個樣例： ```Python >>> hist = histogram('parrot') >>> hist = histogram('parrot') >>> hist >>> hist {'a': 1, 'p': 1, 'r': 2, 't': 1, 'o': 1} >>> inverse = invert_dict(hist) >>> inverse = invert_dict(hist) >>> inverse >>> 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. * * * Figure 11.1 is a state diagram showing hist and inverse. A dictionary is represented as a box with the type dict above it and the key-value pairs inside. If the values are integers, floats or strings, I draw them inside the box, but I usually draw lists outside the box, just to keep the diagram simple. Lists can be values in a dictionary, as this example shows, but they cannot be keys. Here’s what happens if you try: > 圖11.1為hist 和 inverse 兩個字典的狀態圖。字典用方框表示，上方標示了類型 dict，方框內為鍵值對。如果鍵值為整數、浮點數或者字符串，就把它們放到一個方框內，不過通常我習慣把它們放到方框外面，這樣圖表看著簡單干凈。 > 如圖所示，用字典中的鍵值組成列表，而不能用鍵。如果你要用鍵的話，就會遇到如下所示的錯誤： ```Python >>> t = [1, 2, 3] >>> t = [1, 2, 3] >>> d = dict() >>> d = dict() >>> d[t] = 'oops' >>> d[t] = 'oops' Traceback (most recent call last): File "<stdin>", line 1, in ? TypeError: list objects are unhashable ``` I mentioned earlier that a dictionary is implemented using a hashtable and that means that the keys have to be hashtable. > 我之前說過，字典是用哈希表（散列表）來實現的，這就意味著所有鍵都必須是散列的。 A hash is a function that takes a value (of any kind) and returns an integer. Dictionaries use these integers, called hash values, to store and look up key-value pairs. > hash 是一個函數，接收任意一種值，然后返回一個整數。字典用這些整數來存儲和查找鍵值對，這些整數也叫做哈希值。 This system works fine if the keys are immutable. But if the keys are mutable, like lists, bad things happen. For example, when you create a key-value pair, Python hashes the key and stores it in the corresponding location. If you modify the key and then hash it again, it would go to a different location. In that case you might have two entries for the same key, or you might not be able to find a key. Either way, the dictionary wouldn’t work correctly. > 如果鍵不可修改，系統工作正常。但如果鍵可以修改，比如是列表，就悲劇了。例如，你創建一個鍵值對的時候，Python 計算鍵的哈希值，然后存在相應的位置。如果你修改了鍵，然后在計算哈希值，就不會指向同一個位置了。這時候一個鍵就可以有兩個指向了，或者你就可能找不到某個鍵了。總之字典都不能正常工作了。 That’s why keys have to be hashable, and why mutable types like lists aren’t. The simplest way to get around this limitation is to use tuples, which we will see in the next chapter. Since dictionaries are mutable, they can’t be used as keys, but they can be used as values. > 這就是為什么這些鍵必須是散列的，而像列表這樣的可變類型就不行。解決這個問題的最簡單方式就是使用元組，這個我們會在下一章來學習。 > 因為字典是可以修改的，所以不能用來做鍵，只能用來做鍵值。 > > （譯者注：哈希表是一種散列表，相關內容譯者知道的太少，所以這段翻譯的質量大打折扣，實在抱歉。） ## 11.6 Memos 備忘 If you played with the fibonacci function from Section 6.7, you might have noticed that the bigger the argument you provide, the longer the function takes to run. Furthermore, the run time increases quickly. To understand why, consider Figure 11.2, which shows the call graph forfibonacci with n=4: > 如果你試過了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. * * * A call graph shows a set of function frames, with lines connecting each frame to the frames of the functions it calls. At the top of the graph, fibonacci with n=4 calls fibonacci with n=3 and n=2. In turn, fibonacci with n=3 calls fibonacciwith n=2 and n=1. And so on. > 調用圖展示了一系列的函數圖框，圖框直接的連線表示了函數只見的調用關系。頂層位置函數的參數 n =4，調用了 n=3和 n=2兩種情況的函數。相應的 n=3的時候要調用 n=2和 n=1兩種情況。依此類推。 Count how many times fibonacci(0) and fibonacci(1) are called. This is an inefficient solution to the problem, and it gets worse as the argument gets bigger. > 算算fibonacci(0)和fibonacci(1)要被調用多少次吧。這樣的解決方案是低效率的，隨著參數增大，效率就越來越低了。 One solution is to keep track of values that have already been computed by storing them in a dictionary. A previously computed value that is stored for later use is called a memo. Here is a “memoized” version of fibonacci: > 另外一種思路就是保存一下已經被計算過的值，然后保存在一個字典中。之前計算過的值存儲起來，這樣后續的運算中能夠使用，這就叫備忘。下面是一個用這種思路來實現的斐波那契函數： ```Python 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 is a dictionary that keeps track of the Fibonacci numbers we already know. It starts with two items: 0 maps to 0 and 1 maps to 1. > known 是一個用來保存已經計算斐波那契函數值的字典。開始項目有兩個，0對應0，1對應1，各自分別是各自的斐波那契函數值。 Whenever fibonacci is called, it checks known. If the result is already there, it can return immediately. Otherwise it has to compute the new value, add it to the dictionary, and return it. If you run this version of fibonacci and compare it with the original, you will find that it is much faster. > 這樣只要斐波那契函數被調用了，就會檢查 known 這個字典，如果里面有計算過的可用結果，就立即返回。不然的話就計算出新的值，并且存到字典里面，然后返回這個新計算的值。 > 如果你運行這一個版本的斐波那契函數，你會發現比原來那個版本要快得多。 ## 11.7 Global variables 全局變量 In the previous example, known is created outside the function, so it belongs to the special frame called \_\_main\_\_. Variables in \_\_main\_\_ are sometimes called global because they can be accessed from any function. Unlike local variables, which disappear when their function ends, global variables persist from one function call to the next. > 在上面的例子中，known 這個字典是在函數外創建的，所以它屬于主函數內，這是一個特殊的層。在主函數中的變量也叫全局變量，因為所有函數都可以訪問這些變量。局部變量在所屬的函數結束后就消失了，而主函數在其他函數調用結束后依然還存在。 It is common to use global variables for flags; that is, boolean variables that indicate (“flag”) whether a condition is true. For example, some programs use a flag named verbose to control the level of detail in the output: > 一般常用全局變量作為 flag，也就是標識；比如用來判斷一個條件是否成立的布爾變量之類的。比如有的程序用名字為 verbose 的標識變量，來控制輸出內容的詳細程度： ```Python verbose = True def example1(): if verbose: print('Running example1') ``` If you try to reassign a global variable, you might be surprised. The following example is supposed to keep track of whether the function has been called: > 如果你想給全局變量重新賦值，結果會很意外。下面的例子中，本來是想要追蹤確定函數是否被調用了： ```Python been_called = False def example2(): been_called = True # WRONG ``` But if you run it you will see that the value of been_called doesn’t change. The problem is that example2 creates a new local variable named been_called. The local variable goes away when the function ends, and has no effect on the global variable. > 你可以運行一下，并不報錯，只是 been_called 的值并不會變化。這個情況的原因是 example2這個函數創建了一個新的名為 been_called 的局部變量。函數結束之后，局部變量就釋放了，并不會影響全局變量。 To reassign a global variable inside a function you have to declare the global variable before you use it: > 要在函數內部來給全局變量重新賦值，必須要在使用之前聲明這個全局變量： ```Python been_called = False def example2(): global been_called been_called = True ``` The global statement tells the interpreter something like, “In this function, when I say been_called, I mean the global variable; don’t create a local one.” Here’s an example that tries to update a global variable: > global 那句代碼的效果是告訴解釋器：『在這個函數內，been_called 使之全局變量；不要創建一個同名的局部變量。』 > 下面的例子中，試圖對全局變量進行更新： ```Python count = 0 def example3(): count = count + 1 # WRONG ``` If you run it you get: > 運行的話，你會得到如下提示： ```Python UnboundLocalError: local variable 'count' referenced before assignment ``` > 譯者注：錯誤提示的意思是未綁定局部錯誤：局部變量 count 未經賦值就被引用。 Python assumes that count is local, and under that assumption you are reading it before writing it. The solution, again, is to declare count global. > Python 會假設這個 count 是局部的，然后基于這樣的假設，你就是在寫出該變量之前就試圖讀取。這樣問題的解決方法依然就是聲稱count 為全局變量。 ```Python def example3(): global count count += 1 ``` If a global variable refers to a mutable value, you can modify the value without declaring the variable: > 如果全局變量指向的是一個可修改的值，你可以無需聲明該變量就直接修改： ```Python known = {0:0, 1:1} def example4(): known[2] = 1 ``` So you can add, remove and replace elements of a global list or dictionary, but if you want to reassign the variable, you have to declare it: > 所以你可以在全局的列表或者字典里面添加、刪除或者替換元素，但如果你要重新給這個全局變量賦值，就必須要聲明了： ```Python def example5(): global known known = dict() ``` Global variables can be useful, but if you have a lot of them, and you modify them frequently, they can make programs hard to debug. > 全局變量很有用，但不能濫用，要是總修改全局變量的值，就讓程序很難調試了。 ## 11.8 Debugging 調試 As you work with bigger datasets it can become unwieldy to debug by printing and checking the output by hand. Here are some suggestions for debugging large datasets: > 現在數據結構逐漸復雜了，再用打印輸出和手動檢驗的方法來調試就很費勁了。下面是一些對這種復雜數據結構下的建議： Scale down the input: If possible, reduce the size of the dataset. For example if the program reads a text file, start with just the first 10 lines, or with the smallest example you can find. You can either edit the files themselves, or (better) modify the program so it reads only the first n lines. > 縮減輸入： > 盡可能縮小數據的規模。如果程序要讀取一個文本文檔，而只讀前面的十行，或者用你能找到的最小規模的樣例。你可以編輯一下文件本身，或者直接修改程序來僅讀取前面的 n 行，這樣更好。 If there is an error, you can reduce n to the smallest value that manifests the error, and then increase it gradually as you find and correct errors. > 如果存在錯誤了，你可以減小一下 n，一直到錯誤存在的最小的 n 值，然后再逐漸增加 n，這樣就能找到錯誤并改正了。 Check summaries and types: Instead of printing and checking the entire dataset, consider printing summaries of the data: for example, the number of items in a dictionary or the total of a list of numbers. > 檢查概要和類型： > 這回咱就不再打印檢查整個數據表，而是打印輸出數據的概要：比如字典中的項的個數，或者一個列表中的數目總和。 A common cause of runtime errors is a value that is not the right type. For debugging this kind of error, it is often enough to print the type of a value. > 導致運行錯誤的一種常見原因就是類型錯誤。對這類錯誤進行調試，輸出一下值的類型就可以了。 Write self-checks: Sometimes you can write code to check for errors automatically. For example, if you are computing the average of a list of numbers, you could check that the result is not greater than the largest element in the list or less than the smallest. This is called a “sanity check” because it detects results that are “insane”. Another kind of check compares the results of two different computations to see if they are consistent. This is called a “consistency check”. > 寫自檢代碼： > 有時你也可以寫自動檢查錯誤的代碼。舉例來說，假如你計算一個列表中數字的平均值，你可以檢查一下結果是不是比列表中的最大值還大或者比最小值還小。這也叫『心智檢查』，因為是來檢查結果是否『瘋了』（譯者注：也就是錯得很荒誕的意思。）另外一種檢查方法是用兩種不同運算，然后對比結果，看看他們是否一致。后面這種叫『一致性檢查』。 Format the output: Formatting debugging output can make it easier to spot an error. We saw an example in Section 6.9. The pprint module provides a pprint function that displays built-in types in a more human-readable format (pprint stands for “pretty print”). > 格式化輸出： > 格式化的調試輸出，更容易找到錯誤。在6.9的時候我們見過一個例子了。pprint 模塊內置了一個 pprint 函數，該函數能夠把內置的類型用人讀起來更容易的格式來顯示出來（pprint 就是『pretty print』的縮寫）。 Again, time you spend building scaffolding can reduce the time you spend debugging. > 再次強調一下，搭建腳手架代碼的時間越長，用來調試的時間就會相應地縮短。 ## 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 Exercises 練習 ### Exercise 1 練習1 Write a function that reads the words in words.txt and stores them as keys in a dictionary. It doesn’t matter what the values are. Then you can use the in operator as a fast way to check whether a string is in the dictionary. If you did Exercise 10, you can compare the speed of this implementation with the list in operator and the bisection search. > 寫一個函數來讀取 words.txt 文件中的單詞，然后作為鍵存到一個字典中。鍵值是什么不要緊。然后用 in 運算符來快速檢查一個字符串是否在字典中。 > 如果你做過第十章的練習，你可以對比一下這種實現和列表中的 in 運算符以及對折搜索的速度。 ### Exercise 2 練習2 Read the documentation of the dictionary method setdefault and use it to write a more concise version of invert_dict. (Solution)[http://thinkpython2.com/code/invert_dict.py]. > 讀一下字典中 setdefault 方法的相關文檔，然后用這個方法來寫一個更精簡版本的 invert_dict 函數。 (S樣例代碼)[http://thinkpython2.com/code/invert_dict.py]。 ### Exercise 3 練習3 Memoize the Ackermann function from Exercise 2 and see if memoization makes it possible to evaluate the function with bigger arguments. Hint: no. (Solution)[http://thinkpython2.com/code/ackermann_memo.py]. > 用備忘的方法來改進一下第二章練習中的Ackermann函數，看看是不是能讓讓函數處理更大的參數。提示：不行。(樣例代碼)[http://thinkpython2.com/code/ackermann_memo.py]。 ### Exercise 4 練習4 If you did Exercise 7, you already have a function named has_duplicates that takes a list as a parameter and returns True if there is any object that appears more than once in the list. Use a dictionary to write a faster, simpler version of has_duplicates. (Solution)[http://thinkpython2.com/code/has_duplicates.py]. > 如果你做過了第七章的練習，應該已經寫過一個名叫 has_duplicates 的函數了，這個函數用列表做參數，如果里面有元素出現了重復，就返回真。 > 用字典來寫一個更快速更簡單的版本。(樣例代碼)[http://thinkpython2.com/code/has_duplicates.py]。 ### Exercise 5 練習5 Two words are “rotate pairs” if you can rotate one of them and get the other (see rotate_word in Exercise 5). Write a program that reads a word list and finds all the rotate pairs. (Solution)[http://thinkpython2.com/code/rotate_pairs.py]. > 一個詞如果翻轉順序成為另外一個詞，這兩個詞就為『翻轉詞對』（參見第五章練習的 rotate_word，譯者注：作者這個練習我沒找到。。。）。 > 寫一個函數讀取一個單詞表，然后找到所有這樣的單詞對。(樣例代碼)[http://thinkpython2.com/code/rotate_pairs.py]. ### Exercise 6 練習6 Here’s another Puzzler from (Car Talk)[http://www.cartalk.com/content/puzzlers]: This was sent in by a fellow named Dan O’Leary. He came upon a common one-syllable, five-letter word recently that has the following unique property. When you remove the first letter, the remaining letters form a homophone of the original word, that is a word that sounds exactly the same. Replace the first letter, that is, put it back and remove the second letter and the result is yet another homophone of the original word. And the question is, what’s the word? > 下面是一個來自(Car Talk)[http://www.cartalk.com/content/puzzlers]的謎語： > 這條謎語來自一個名叫 Dan O'Leary的朋友。他最近發現一個單詞，這個單詞有一個音節，五個字母，然后有以下所述的特定性質。 > 去掉第一個字母，得到的是與原詞同音異形異義詞，發音與原詞一模一樣。替換一下首字母，也就是把第一個字母放回去，然后把第二個字母去掉，得到的是另外一個這樣的同音異形異義詞。那么問題來了，這是個什么詞呢？ Now I’m going to give you an example that doesn’t work. Let’s look at the five-letter word, ‘wrack.’ W-R-A-C-K, you know like to ‘wrack with pain.’ If I remove the first letter, I am left with a four-letter word, ’R-A-C-K.’ As in, ‘Holy cow, did you see the rack on that buck! It must have been a nine-pointer!’ It’s a perfect homophone. If you put the ‘w’ back, and remove the ‘r,’ instead, you’re left with the word, ‘wack,’ which is a real word, it’s just not a homophone of the other two words. > 現在我給你提供一個錯誤的例子。咱們先看一下五個字母的單詞，「wrack」。去掉第一個字母，得到的四個字母單詞是「R-A-C-K」。但去掉第二個字母得到的是「W-A-C-K」，這就不是前兩個詞的同音異形異義詞。（譯者注：詞義的細節就略去了，沒有太大必要。） But there is, however, at least one word that Dan and we know of, which will yield two homophones if you remove either of the first two letters to make two, new four-letter words. The question is, what’s the word? > 但這個詞至少有一個，Dan 和咱們都知道的，分別刪除前兩個字母會產生兩個同音異形異義的四個字母的單詞。問題就是，這是哪個詞？ You can use the dictionary from Exercise 1 to check whether a string is in the word list. To check whether two words are homophones, you can use the CMU Pronouncing Dictionary. You can download it from (Here)[http://www.speech.cs.cmu.edu/cgi-bin/cmudict] or from (Here)[http://thinkpython2.com/code/c06d] and you can also download (Here)[http://thinkpython2.com/code/pronounce.py], which provides a function namedread_dictionary that reads the pronouncing dictionary and returns a Python dictionary that maps from each word to a string that describes its primary pronunciation. Write a program that lists all the words that solve the Puzzler. (Solution)[http://thinkpython2.com/code/homophone.py]. > 你可以用本章練習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]。