Chapter 11  Dictionaries 第 11 章 字典

本页译自 Think Python 2e（Allen B. Downey）· Chapter 11 Dictionaries。代码块保留英文原文不翻译；正文段段对照，中文块可用右下角按钮隐藏。

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.

You can think of a dictionary as a mapping between a set of indices (which are called keys) and a set of values. Each key maps to a value. The association of a key and a value is called a key-value pair or sometimes an item.

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.

The squiggly-brackets, {}, represent an empty dictionary. To add items to the dictionary, you can use square brackets:

This line creates an item that maps from the key dict0 to the value dict0. If we print the dictionary again, we see a key-value pair with a colon between the key and value:

This output format is also an input format. For example, you can create a new dictionary with three items:

But if you print dict00, you might be surprised:

The order of the key-value pairs is not the same. In fact, 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:

The key dict0 always maps to the value dict0 so the order of the items doesn’t matter.

If the key isn’t in the dictionary, you get an exception:

The {}0 function works on dictionaries; it returns the number of key-value pairs:

The {} operator works on dictionaries; it tells you whether something appears as a key in the dictionary (appearing as a value is not good enough).

To see whether something appears as a value in a dictionary, you can use the method dict00, which returns the values as a list, and then use the {} operator:

The {} operator uses different algorithms for lists and dictionaries. For lists, it uses a search algorithm, as in Section 8.6. As the list gets longer, the search time gets longer in direct proportion. For dictionaries, Python uses an algorithm called a hashtable that has a remarkable property: the {} operator takes about the same amount of time no matter how many items there are in a dictionary. I won’t explain how that’s possible, but you can read more about it at dict00040




























.

Exercise 1

Write a function that reads the words in dict00044 and stores them as keys in a dictionary. It doesn’t matter what the values are. Then you can use the {} operator as a fast way to check whether a string is in the dictionary.

If you did Exercise 11, you can compare the speed of this implementation with the list {} operator and the bisection search.

11.1 Dictionary as a set of counters 11.1 字典作计数器集合

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.
2. You could create a list with 26 elements. Then you could convert each character to a number (using the built-in function {}0), use the number as an index into the list, and increment the appropriate counter.
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.

1. 建 26 个变量，字母表里每个字母一个。然后遍历字符串，对每个字符把相应的计数器加一——大概得用一长串链式条件语句。
2. 建一个含 26 个元素的列表。然后把每个字符转成数字（用内置函数 {}0），拿这个数字当列表的索引，给对应的计数器加一。
3. 建一个字典，以字符为键、计数器为对应的值。第一次遇到某个字符时，往字典里添一个条目；之后就给已有条目的值加一。

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:

The name of the function is histogram, which is a statistical term for a set of counters (or frequencies).

The first line of the function creates an empty dictionary. The {}0 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 dict.

Here’s how it works:

The histogram indicates that the letters {}0 and {}0 appear once; {}0 appears twice, and so on.

Exercise 2

Dictionaries have a method called {}0 that takes a key and a default value. If the key appears in the dictionary, {}0 returns the corresponding value; otherwise it returns the default value. For example:

Use {}0 to write dict00076 more concisely. You should be able to eliminate the {} statement.

11.2 Looping and dictionaries 11.2 循环与字典

If you use a dictionary in a {}0 statement, it traverses the keys of the dictionary. For example, dict00082 prints each key and the corresponding value:

Here’s what the output looks like:

Again, the keys are in no particular order.

Exercise 3

Dictionaries have a method called dict that returns the keys of the dictionary, in no particular order, as a list.

Modify dict00089 to print the keys and their values in alphabetical order.

11.3 Reverse lookup 11.3 反向查找

Given a dictionary c and a key c, it is easy to find the corresponding value dict0009. This operation is called a lookup.

But what if you have c and you want to find c? You have two problems: first, there might be more than one key that maps to the value c. 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:

This function is yet another example of the search pattern, but it uses a feature we haven’t seen before, dict0. The dict0 statement causes an exception; in this case it causes a dict00106, which generally indicates that there is something wrong with the value of a parameter.

If we get to the end of the loop, that means c doesn’t appear in the dictionary as a value, so we raise an exception.

Here is an example of a successful reverse lookup:

And an unsuccessful one:

The result when you raise an exception is the same as when Python raises one: it prints a traceback and an error message.

The dict0 statement takes a detailed error message as an optional argument. For example:

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.

Exercise 4

Modify dict00117



so that it builds and returns a list of all keys that map to c, or an empty list if there are none.

11.4 Dictionaries and lists 11.4 字典与列表

Lists can appear as values in a dictionary. For example, if you were 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:

Each time through the loop, {}0 gets a key from c and {}0 gets the corresponding value. If {}0 is not in dict001, 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:

Figure 11.1: State diagram.

Figure 11.1 is a state diagram showing dict and dict001. 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 usually 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:

I mentioned earlier that a dictionary is implemented using a hashtable and that means that the keys have to be hashable.

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.

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.

That’s why the 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 lists and dictionaries are mutable, they can’t be used as keys, but they can be used as values.

Exercise 5

Read the documentation of the dictionary method dict00140 and use it to write a more concise version of dict00141
. Solution: dict00142































.

11.5 Memos 11.5 备忘录

If you played with the dict00146 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 very quickly.

To understand why, consider Figure 11.2, which shows the call graph for dict00148 with {}0:

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, dict00152 with {}0 calls dict00154 with {}0 and {}0. In turn, dict00157 with {}0 calls dict00159 with {}0 and {}0. And so on.

Count how many times dict00172

and dict00173

are called. This is an inefficient solution to the problem, and it gets worse as the argument gets bigger.

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 dict00176:

dict0 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.

Whenever dict00181 is called, it checks dict0. 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.

Exercise 6

Run this version of dict00185 and the original with a range of parameters and compare their run times.

Exercise 7

Memoize the Ackermann function from Exercise 5 and see if memoization makes it possible to evaluate the function with bigger arguments. Hint: no. Solution: dict00187


































.

11.6 Global variables 11.6 全局变量

In the previous example, dict0 is created outside the function, so it belongs to the special frame called dict0019. Variables in dict0019 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.

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 dict001 to control the level of detail in the output:

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:

But if you run it you will see that the value of dict00199
doesn’t change. The problem is that dict0020 creates a new local variable named dict00201
. The local variable goes away when the function ends, and has no effect on the global variable.

To reassign a global variable inside a function you have to declare the global variable before you use it:

The dict00 statement tells the interpreter something like, “In this function, when I say dict00207
, I mean the global variable; don’t create a local one.”

Here’s an example that tries to update a global variable:

If you run it you get:

Python assumes that dict0 is local, which means that you are reading it before writing it. The solution, again, is to declare dict0 global.

If the global value is mutable, you can modify it without declaring it:

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:

11.7 Long integers 11.7 长整数

If you compute dict00219


, you get:

The c at the end indicates that the result is a long integer, or type dict. In Python 3, dict is gone; all integers, even really big ones, are type {}0.

Values with type {}0 have a limited range; long integers can be arbitrarily big, but as they get bigger they consume more space and time.

The mathematical operators work on long integers, and the functions in the dict module, too, so in general any code that works with {}0 will also work with dict.

Any time the result of a computation is too big to be represented with an integer, Python converts the result as a long integer:

In the first case the result has type {}0; in the second case it is dict.

Exercise 8

Exponentiation of large integers is the basis of common algorithms for public-key encryption. Read the Wikipedia page on the RSA algorithm (dict00243

































) and write functions to encode and decode messages.

11.8 Debugging 11.8 调试

As you work with bigger datasets it can become unwieldy to debug by printing and checking data 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 c lines. If there is an error, you can reduce c to the smallest value that manifests the error, and then increase it gradually as you find and correct errors.

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.”

Pretty print the output:

Formatting debugging output can make it easier to spot an error. We saw an example in Section 6.9. The dict00 module provides a dict00 function that displays built-in types in a more human-readable format.

缩小输入规模：

可能的话，把数据集缩小。比如程序要读一个文本文件，就先只拿前 10 行、或者你能找到的最小样例来试。你可以直接改文件，也可以（更好的做法）改程序，让它只读前 c 行。 出错时，把 c 缩到刚好还能暴露错误的最小值；随着错误被找出来并改掉，再逐步加大。

检查摘要与类型：

别把整个数据集打印出来一一核对，不妨打印数据的摘要，比如字典里的条目数，或者一个数字列表的总和。 运行时错误常常源于某个值类型不对。要查这类错误，往往打印出值的类型就够了。

写自检代码：

有时可以写代码自动检查错误。比如在算一个数字列表的平均值，就可以检查结果是否既不大于列表中最大的元素、也不小于最小的元素。这叫「合理性检查」（sanity check），因为它能揪出「不合常理」的结果。 另一类检查是拿两种不同算法的结果作比较，看它们是否一致，这叫「一致性检查」（consistency check）。

美化输出：

把调试输出排版一下，错误更容易看出来。6.9 节见过一个例子。dict00 模块提供了一个 dict00 函数，能以更易读的格式显示内置类型。

Again, time you spend building scaffolding can reduce the time you spend debugging.

11.9 Glossary 11.9 术语表

dictionary:

A mapping from a set of keys to their corresponding values.

key-value pair:

The representation of the mapping from a key to a value.

item:

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.

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.

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.

histogram:

A set of counters.

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.

flag:

A boolean variable used to indicate whether a condition is true.

declaration:

A statement like dict00 that tells the interpreter something about a variable.

dictionary 字典：

从一组键到其对应值的映射。

key-value pair 键值对：

「一个键映射到一个值」这种关系的表示形式。

item 条目：

键值对的另一种叫法。

key 键：

在字典中作为键值对第一部分出现的对象。

value 值：

在字典中作为键值对第二部分出现的对象。这个含义比我们之前用的「值」更为具体。

implementation 实现：

完成某项计算的具体方式。

hashtable 散列表：

用来实现 Python 字典的算法。

hash function 散列函数：

散列表用来计算某个键存放位置的函数。

hashable 可散列：

具备散列函数的类型。整数、浮点数、字符串这类不可变类型是可散列的；列表、字典这类可变类型则不可散列。

lookup 查找：

字典的一种操作：给定一个键，找出对应的值。

reverse lookup 反向查找：

字典的一种操作：给定一个值，找出映射到它的一个或多个键。

singleton 单元素列表：

只含一个元素的列表（或其他序列）。

call graph 调用图：

展示程序执行期间创建的每一个栈帧的图，从每个调用方到每个被调方各画一个箭头。

histogram 直方图：

一组计数器。

memo 备忘录：

存下来的已算出的值，用以省去日后不必要的计算。

global variable 全局变量：

在函数外定义的变量。任何函数都能访问全局变量。

flag 标志：

用来标示某个条件是否成立的布尔变量。

declaration 声明：

像 dict00 这样、向解释器交代某个变量的某些信息的语句。

11.10 Exercises 11.10 习题

Exercise 9

If you did Exercise 8, you already have a function named dict00255



that takes a list as a parameter and returns dict if there is any object that appears more than once in the list.

Use a dictionary to write a faster, simpler version of dict00259



. Solution: dict00260


































.

Exercise 10

Two words are “rotate pairs” if you can rotate one of them and get the other (see dict00263
in Exercise 12).

Write a program that reads a wordlist and finds all the rotate pairs. Solution: dict00265
































.

Exercise 11

Here’s another Puzzler from Car Talk (dict00267




























):

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?

这题是一位叫 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」，W-R-A-C-K，就是「wrack with pain（痛得死去活来）」里那个。去掉第一个字母，剩下四字母词「R-A-C-K」，就像「我的天，你看见那头公鹿的角架没有！准是九叉的！」这可是个完美的同音词。可要是把「w」放回去、改去掉「r」，剩下的是「wack」——确实是个词，只不过跟前两个词不同音。

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 dict00269

































or from dict00270





















and you can also download dict00271





























, which provides a function named dict00272




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: dict00277





























.