Chapter 13  Case study: data structure selection 第 13 章 案例研究：数据结构选择

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

13.1 Word frequency analysis 13.1 词频分析

As usual, you should at least attempt the following exercises before you read my solutions.

Exercise 1

Write a program that reads a file, breaks each line into words, strips whitespace and punctuation from the words, and converts them to lowercase.

Hint: The string module provides strings named string005, which contains space, tab, newline, etc., and string006
which contains the punctuation characters. Let’s see if we can make Python swear:

Also, you might consider using the string methods strip, string0 and string013.

Exercise 2

Go to Project Gutenberg (string017









) and download your favorite out-of-copyright book in plain text format.

Modify your program from the previous exercise to read the book you downloaded, skip over the header information at the beginning of the file, and process the rest of the words as before.

Then modify the program to count the total number of words in the book, and the number of times each word is used.

Print the number of different words used in the book. Compare different books by different authors, written in different eras. Which author uses the most extensive vocabulary?

Exercise 3

Modify the program from the previous exercise to print the 20 most frequently-used words in the book.

Exercise 4

Modify the previous program to read a word list (see Section 9.1) and then print all the words in the book that are not in the word list. How many of them are typos? How many of them are common words that should be in the word list, and how many of them are really obscure?

13.2 Random numbers 13.2 随机数

Given the same inputs, most computer programs generate the same outputs every time, so they are said to be deterministic. Determinism is usually a good thing, since we expect the same calculation to yield the same result. For some applications, though, we want the computer to be unpredictable. Games are an obvious example, but there are more.

Making a program truly nondeterministic turns out to be not so easy, but there are ways to make it at least seem nondeterministic. One of them is to use algorithms that generate pseudorandom numbers. Pseudorandom numbers are not truly random because they are generated by a deterministic computation, but just by looking at the numbers it is all but impossible to distinguish them from random.

The string module provides functions that generate pseudorandom numbers (which I will simply call “random” from here on).

The function string returns a random float between 0.0 and 1.0 (including 0.0 but not 1.0). Each time you call string, you get the next number in a long series. To see a sample, run this loop:

The function string0 takes parameters low and low0 and returns an integer between low and low0 (including both).

To choose an element from a sequence at random, you can use string:

The string module also provides functions to generate random values from continuous distributions including Gaussian, exponential, gamma, and a few more.

Exercise 5

Write a function named string042





that takes a histogram as defined in Section 11.1 and returns a random value from the histogram, chosen with probability in proportion to frequency. For example, for this histogram:

your function should return low with probability 2/3 and low with probability 1/3.

13.3 Word histogram 13.3 词直方图

You should attempt the previous exercises before you go on. You can download my solution from string049
































. You will also need string050

























.

Here is a program that reads a file and builds a histogram of the words in the file:

This program reads string05, which contains the text of Emma by Jane Austen.

string056

loops through the lines of the file, passing them one at a time to string057

. The histogram low0 is being used as an accumulator.

string062

uses the string method string0 to replace hyphens with spaces before using strip to break the line into a list of strings. It traverses the list of words and uses strip and strip to remove punctuation and convert to lower case. (It is a shorthand to say that strings are “converted;” remember that string are immutable, so methods like strip and strip return new strings.)

Finally, string076

updates the histogram by creating a new item or incrementing an existing one.

To count the total number of words in the file, we can add up the frequencies in the histogram:

The number of different words is just the number of items in the dictionary:

Here is some code to print the results:

And the results:

13.4 Most common words 13.4 最常见的词

To find the most common words, we can apply the DSU pattern; string082
takes a histogram and returns a list of word-frequency tuples, sorted in reverse order by frequency:

Here is a loop that prints the ten most common words:

And here are the results from Emma:

13.5 Optional parameters 13.5 可选形参

We have seen built-in functions and methods that take a variable number of arguments. It is possible to write user-defined functions with optional arguments, too. For example, here is a function that prints the most common words in a histogram

The first parameter is required; the second is optional. The default value of low is 10.

If you only provide one argument:

low gets the default value. If you provide two arguments:

low gets the value of the argument instead. In other words, the optional argument overrides the default value.

If a function has both required and optional parameters, all the required parameters have to come first, followed by the optional ones.

13.6 Dictionary subtraction 13.6 字典减法

Finding the words from the book that are not in the word list from string096 is a problem you might recognize as set subtraction; that is, we want to find all the words from one set (the words in the book) that are not in another set (the words in the list).

string09 takes dictionaries d1 and d1 and returns a new dictionary that contains all the keys from d1 that are not in d1. Since we don’t really care about the values, we set them all to None.

To find the words in the book that are not in string109, we can use string110

to build a histogram for string111, and then subtract:

Here are some of the results from Emma:

Some of these words are names and possessives. Others, like “rencontre,” are no longer in common use. But a few are common words that should really be in the list!

Exercise 6

Python provides a data structure called low that provides many common set operations. Read the documentation at string118













































and write a program that uses set subtraction to find words in the book that are not in the word list. Solution: string119

































.

13.7 Random words 13.7 随机词

To choose a random word from the histogram, the simplest algorithm is to build a list with multiple copies of each word, according to the observed frequency, and then choose from the list:

The expression string124


creates a list with low0 copies of the string low0. The string method is similar to string except that the argument is a sequence.

Exercise 7

This algorithm works, but it is not very efficient; each time you choose a random word, it rebuilds the list, which is as big as the original book. An obvious improvement is to build the list once and then make multiple selections, but the list is still big.

An alternative is:

1. Use low0 to get a list of the words in the book.
2. Build a list that contains the cumulative sum of the word frequencies (see Exercise 3). The last item in this list is the total number of words in the book, n.
3. Choose a random number from 1 to n. Use a bisection search (See Exercise 11) to find the index where the random number would be inserted in the cumulative sum.
4. Use the index to find the corresponding word in the word list.

1. 用 low0 取出书中所有单词的列表。
2. 建一个列表，存放词频的累积和（见习题 3）。这个列表的最后一项就是全书的总词数 n。
3. 从 1 到 n 取一个随机数。用二分查找（见习题 11）找出这个随机数插入累积和序列时所在的索引。
4. 用这个索引到单词列表里找出对应的词。

Write a program that uses this algorithm to choose a random word from the book. Solution: string136

































.

13.8 Markov analysis 13.8 马尔可夫分析

If you choose words from the book at random, you can get a sense of the vocabulary, you probably won’t get a sentence:

A series of random words seldom makes sense because there is no relationship between successive words. For example, in a real sentence you would expect an article like “the” to be followed by an adjective or a noun, and probably not a verb or adverb.

One way to measure these kinds of relationships is Markov analysis, which characterizes, for a given sequence of words, the probability of the word that comes next. For example, the song Eric, the Half a Bee begins:

Half a bee, philosophically,
Must, ipso facto, half not be.
But half the bee has got to be
Vis a vis, its entity. D’you see?

But can a bee be said to be
Or not to be an entire bee
When half the bee is not a bee
Due to some ancient injury?

半只蜜蜂，从哲学上讲，
依此推论，必有一半不成其为蜂。
可那存在的半只蜜蜂，
终究要面对它自己的本体。明白吗？

但一只蜜蜂究竟能不能说是
或者不是一只完整的蜜蜂，
当半只蜜蜂已算不得蜜蜂，
只因某处古老的旧伤？

In this text, the phrase “half the” is always followed by the word “bee,” but the phrase “the bee” might be followed by either “has” or “is”.

The result of Markov analysis is a mapping from each prefix (like “half the” and “the bee”) to all possible suffixes (like “has” and “is”).

Given this mapping, you can generate a random text by starting with any prefix and choosing at random from the possible suffixes. Next, you can combine the end of the prefix and the new suffix to form the next prefix, and repeat.

For example, if you start with the prefix “Half a,” then the next word has to be “bee,” because the prefix only appears once in the text. The next prefix is “a bee,” so the next suffix might be “philosophically,” “be” or “due.”

In this example the length of the prefix is always two, but you can do Markov analysis with any prefix length. The length of the prefix is called the “order” of the analysis.

Exercise 8

Markov analysis:

1. Write a program to read a text from a file and perform Markov analysis. The result should be a dictionary that maps from prefixes to a collection of possible suffixes. The collection might be a list, tuple, or dictionary; it is up to you to make an appropriate choice. You can test your program with prefix length two, but you should write the program in a way that makes it easy to try other lengths.
2. Add a function to the previous program to generate random text based on the Markov analysis. Here is an example from Emma with prefix length 2:
3. Once your program is working, you might want to try a mash-up: if you analyze text from two or more books, the random text you generate will blend the vocabulary and phrases from the sources in interesting ways.

1. 写一个程序，从文件读入一段文本并做马尔可夫分析。结果应是一个字典，把前缀映射到一组可能的后缀。这组后缀可以用列表、元组或字典表示，怎么选合适由你决定。测试时可以用前缀长度 2，但程序要写得便于改用其他长度。
2. 给上面的程序加一个函数，基于马尔可夫分析生成随机文本。下面是取自《爱玛》、前缀长度为 2 的一个例子：
3. 程序跑通之后，不妨试试「混搭」：如果分析两本或更多书的文本，生成的随机文本会以有趣的方式把各来源的词汇和短语揉在一起。

He was very clever, be it sweetness or be angry, ashamed or only amused, at such a stroke. She had never thought of Hannah till you were never meant for me?" "I cannot make speeches, Emma:" he soon cut it all himself.

他非常聪明，无论是甜言蜜语还是发怒，是羞愧还是只觉得好笑，面对这样一记打击。她从没想到过汉娜，直到你从来就不是为我准备的？「我不会讲漂亮话，爱玛：」他很快就自己把话全打断了。（机器生成的随机文本，语法勉强通顺、语义似通非通，中文只作示意。）

For this example, I left the punctuation attached to the words. The result is almost syntactically correct, but not quite. Semantically, it almost makes sense, but not quite.

What happens if you increase the prefix length? Does the random text make more sense?

Credit: This case study is based on an example from Kernighan and Pike, The Practice of Programming, Addison-Wesley, 1999.

You should attempt this exercise before you go on; then you can can download my solution from string139


























. You will also need string140

























.

13.9 Data structures 13.9 数据结构

Using Markov analysis to generate random text is fun, but there is also a point to this exercise: data structure selection. In your solution to the previous exercises, you had to choose:

• How to represent the prefixes.
• How to represent the collection of possible suffixes.
• How to represent the mapping from each prefix to the collection of possible suffixes.

• 如何表示前缀。
• 如何表示可能后缀的集合。
• 如何表示从每个前缀到后缀集合的映射。

Ok, the last one is easy; the only mapping type we have seen is a dictionary, so it is the natural choice.

For the prefixes, the most obvious options are string, list of strings, or tuple of strings. For the suffixes, one option is a list; another is a histogram (dictionary).

How should you choose? The first step is to think about the operations you will need to implement for each data structure. For the prefixes, we need to be able to remove words from the beginning and add to the end. For example, if the current prefix is “Half a,” and the next word is “bee,” you need to be able to form the next prefix, “a bee.”

Your first choice might be a list, since it is easy to add and remove elements, but we also need to be able to use the prefixes as keys in a dictionary, so that rules out lists. With tuples, you can’t append or remove, but you can use the addition operator to form a new tuple:

strip takes a tuple of words, string, and a string, low0, and forms a new tuple that has all the words in string except the first, and low0 added to the end.

For the collection of suffixes, the operations we need to perform include adding a new suffix (or increasing the frequency of an existing one), and choosing a random suffix.

Adding a new suffix is equally easy for the list implementation or the histogram. Choosing a random element from a list is easy; choosing from a histogram is harder to do efficiently (see Exercise 7).

So far we have been talking mostly about ease of implementation, but there are other factors to consider in choosing data structures. One is run time. Sometimes there is a theoretical reason to expect one data structure to be faster than other; for example, I mentioned that the d1 operator is faster for dictionaries than for lists, at least when the number of elements is large.

But often you don’t know ahead of time which implementation will be faster. One option is to implement both of them and see which is better. This approach is called benchmarking. A practical alternative is to choose the data structure that is easiest to implement, and then see if it is fast enough for the intended application. If so, there is no need to go on. If not, there are tools, like the string1 module, that can identify the places in a program that take the most time.

The other factor to consider is storage space. For example, using a histogram for the collection of suffixes might take less space because you only have to store each word once, no matter how many times it appears in the text. In some cases, saving space can also make your program run faster, and in the extreme, your program might not run at all if you run out of memory. But for many applications, space is a secondary consideration after run time.

One final thought: in this discussion, I have implied that we should use one data structure for both analysis and generation. But since these are separate phases, it would also be possible to use one structure for analysis and then convert to another structure for generation. This would be a net win if the time saved during generation exceeded the time spent in conversion.

13.10 Debugging 13.10 调试

When you are debugging a program, and especially if you are working on a hard bug, there are four things to try:

reading:

Examine your code, read it back to yourself, and check that it says what you meant to say.

running:

Experiment by making changes and running different versions. Often if you display the right thing at the right place in the program, the problem becomes obvious, but sometimes you have to spend some time to build scaffolding.

ruminating:

Take some time to think! What kind of error is it: syntax, runtime, semantic? What information can you get from the error messages, or from the output of the program? What kind of error could cause the problem you’re seeing? What did you change last, before the problem appeared?

retreating:

At some point, the best thing to do is back off, undoing recent changes, until you get back to a program that works and that you understand. Then you can start rebuilding.

reading 读代码：

仔细看你的代码，念给自己听，核对它说的是不是你想说的。

running 跑程序：

动手改一改，跑不同的版本试试。常常只要在程序里合适的位置打印出合适的东西，问题就一目了然；但有时得花点工夫搭脚手架。

ruminating 静下来想：

花点时间思考！这是哪类错误：语法错误、运行时错误还是语义错误？从错误消息或程序输出里能得到什么信息？什么样的错误会导致你看到的现象？问题出现前，你最后改动了什么？

retreating 往回退：

到了某个时候，最好的办法是后退，把最近的改动撤掉，退回到一个能跑、你也看得懂的版本，然后重新往上搭。

Beginning programmers sometimes get stuck on one of these activities and forget the others. Each activity comes with its own failure mode.

For example, reading your code might help if the problem is a typographical error, but not if the problem is a conceptual misunderstanding. If you don’t understand what your program does, you can read it 100 times and never see the error, because the error is in your head.

Running experiments can help, especially if you run small, simple tests. But if you run experiments without thinking or reading your code, you might fall into a pattern I call “random walk programming,” which is the process of making random changes until the program does the right thing. Needless to say, random walk programming can take a long time.

You have to take time to think. Debugging is like an experimental science. You should have at least one hypothesis about what the problem is. If there are two or more possibilities, try to think of a test that would eliminate one of them.

Taking a break helps with the thinking. So does talking. If you explain the problem to someone else (or even yourself), you will sometimes find the answer before you finish asking the question.

But even the best debugging techniques will fail if there are too many errors, or if the code you are trying to fix is too big and complicated. Sometimes the best option is to retreat, simplifying the program until you get to something that works and that you understand.

Beginning programmers are often reluctant to retreat because they can’t stand to delete a line of code (even if it’s wrong). If it makes you feel better, copy your program into another file before you start stripping it down. Then you can paste the pieces back in a little bit at a time.

Finding a hard bug requires reading, running, ruminating, and sometimes retreating. If you get stuck on one of these activities, try the others.

13.11 Glossary 13.11 术语表

deterministic:

Pertaining to a program that does the same thing each time it runs, given the same inputs.

pseudorandom:

Pertaining to a sequence of numbers that appear to be random, but are generated by a deterministic program.

default value:

The value given to an optional parameter if no argument is provided.

override:

To replace a default value with an argument.

benchmarking:

The process of choosing between data structures by implementing alternatives and testing them on a sample of the possible inputs.

deterministic 确定性的：

用于形容这样的程序：给定同样的输入，每次运行都做同样的事。

pseudorandom 伪随机：

用于形容这样的数列：看上去是随机的，实际由确定性的程序生成。

default value 默认值：

未提供实参时，可选形参取到的值。

override 覆盖：

用实参取代默认值。

benchmarking 基准测试（性能测试）：

在几种数据结构之间做选择的过程：把备选方案都实现出来，用一批可能的输入样本测试它们。

13.12 Exercises 13.12 习题

Exercise 9

The “rank” of a word is its position in a list of words sorted by frequency: the most common word has rank 1, the second most common has rank 2, etc.

Zipf’s law describes a relationship between the ranks and frequencies of words in natural languages (string158




























). Specifically, it predicts that the frequency, f, of the word with rank r is:

f = c r^−s

where s and c are parameters that depend on the language and the text. If you take the logarithm of both sides of this equation, you get:

logf = logc − s logr

So if you plot log f versus log r, you should get a straight line with slope −s and intercept log c.

Write a program that reads a text from a file, counts word frequencies, and prints one line for each word, in descending order of frequency, with log f and log r. Use the graphing program of your choice to plot the results and check whether they form a straight line. Can you estimate the value of s?

Solution: string160
























. To make the plots, you might have to install matplotlib (see string161























).