# 第十三章 案例學習：數據結構的選擇
到現在為止，你已經學過 Python 中最核心的數據結構了，也學過了一些與之對應的各種算法了。如果你想要對算法進行深入的了解，就可以來讀一下第十三章。但不讀這一章也可以繼續；無論什么時候讀都可以，感興趣了就來看即可。
本章通過一個案例和一些練習，來講解一下如何選擇和使用數據結構。
## 13.1 詞頻統計
跟往常一樣，你最起碼也得先自己嘗試做一下這些練習，然后再看參考答案。
### 練習 1
寫一個讀取文件的程序，把每一行拆分成一個個詞，去掉空白和標點符號，然后把所有單詞都轉換成小寫字母的。
提示：字符串模塊 string 提供了一個名為 whitespace 的字符串，包含了空格、跳表符、另起一行等等，然后還有個 punctuation 模塊，包含了各種標點符號的字符。咱們可以試試讓 Python 把標點符號都給顯示一下：
```py
>>> import string
>>>string.punctuation
'!"#$%&'()*+,-./:;<=>?@[\]^_`{|}~'
```
另外你也可以試試字符串模塊的其他方法，比如 strip、replace 以及 translate。
### 練習 2
訪問[古登堡計劃網站] (http://gutenberg.org)，然后下載一個你最喜歡的公有領域的書，要下載純文本格式的哈。
修改一下剛才上一個練習你寫的程序，讓這個程序能讀取你下載的這本書，跳過文件開頭部分的信息，繼續以上個練習中的方式來處理一下整本書的正文。
然后再修改一下程序，讓程序能統計一下整本書的總單詞數目，以及每個單詞出現的次數。
輸出一下這本書中不重復的單詞的個數。對比一下不同作者、不同地域的書籍。哪個作者的詞匯量最豐富？
### 練習 3
再接著修改程序，輸出一下每本書中最頻繁出現的 20 個詞。
### 練習 4
接著修改，讓程序能讀取一個單詞列表（參考 9.1），然后輸出一下所有包含在書中，但不包含于單詞列表中的單詞。看看這些單詞中有多少是排版錯誤的？有多少是本應被單詞列表包含的常用單詞？有多少是很晦澀艱深的罕見詞匯？
## 13.2 隨機數
輸入相同的情況下，大多數計算機程序每次都會給出相同的輸出，這也叫做確定性。確定性通常是一件好事，因為我們都希望同樣的運算產生同樣的結構。但有時候為了一些特定用途，咱們就需要讓計算機能有不可預測性。比如游戲等等，有很多很多這樣的情景。
然而，想讓一個程序真正變成不可預測的，也是很難的，但好在有辦法能讓程序看上去不太確定。其中一種方法就是通過算法來產生假隨機數。假隨機數，顧名思義就知道不是真正隨機的了，因為它們是通過一種確定性的運算來得到的，但這些數字看上去是隨機的，很難與真正的隨機數區分。
（譯者注：這里大家很容易一帶而過，而不去探究到底怎樣能確定是真隨機數。實際上隨機數是否能得到以及是否存在會影響哲學判斷，可知論和不可知論等等。那么就建議大家思考和搜索一下，隨機數算法產生的隨機數和真正隨機數有什么本質的區別，以及是否有辦法得到真正的隨機數。如果有，如何得到呢？）
random 模塊提供了生成假隨機數的函數（從這里開始，咱們就用隨機數來簡稱假隨機數了哈）。
函數 random 返回一個在 0.0 到 1.0 的前閉后開區間（就是包括 0.0 但不包括 1.0，這個特性在 Python 隨處都是，比如序列的索引等等）的隨機數。每次調用 random，就會得到一個很長的數列中的下一個數。如下這個循環就是一個例子了：
```py
import random for i in range(10):
x = random.random()
print(x)
```
randint 函數接收兩個參數作為下界和上界，然后返回一個二者之間的整數，這個整數可以是下界或者上界。
```py
>>> random.randint(5, 10)
5
>>> random.randint(5, 10)
9
```
choice 函數可以用來從一個序列中隨機選出一個元素：
```py
>>> t = [1, 2, 3]
>>> random.choice(t)
2
>>> random.choice(t)
3
```
random 模塊還提供了其他一些函數，可以計算某些連續分布的隨機值，比如 Gaussian 高斯分布, exponential 指數分布, gamma γ分布等等。
### 練習 5
寫一個名為 choose_from_hist 的函數，用這個函數來處理一下 11.2 中定義的那個 histogram 函數，從 histogram 的值當中隨機選擇一個，這個選擇的概率按照比例來定。比如下面這個 histogram：
```py
>>> t = ['a', 'a', 'b']
>>> hist = histogram(t)
>>> hist
{'a': 2, 'b': 1}
```
你的函數就應該返回 a 的概率為 2/3，返回 b 的概率為 1/3
## 13.3 詞頻
你得先把前面的練習作一下，然后再繼續哈。可以從[這里](http://thinkpython2.com/code/analyze_book1.py)下載我的樣例代碼。
此外還要下載[這個](http://thinkpython2.com/code/emma.txt)。
下面這個程序先讀取一個文件，然后對該文件中的詞頻進行了統計：
```py
import string
def process_file(filename):
hist = dict()
fp = open(filename)
for line in fp:
process_line(line, hist)
return hist
def process_line(line, hist):
line = line.replace('-', ' ')
for word in line.split():
word = word.strip(string.punctuation + string.whitespace)
word = word.lower()
hist[word] = hist.get(word, 0) + 1
hist = process_file('emma.txt')
```
上面這個程序讀取的是 emma.txt 這個文件，該文件是簡奧斯汀的小說《艾瑪》。
process_file 這個函數遍歷整個文件，逐行讀取，然后把每行的內容發給 process_line 函數。詞頻統計函數 hist 在該程序中是一個累加器。
process_line 使用字符串的方法 replace 把各種連字符都用空格替換，然后用 split 方法把整行打散成一個字符串列表。程序遍歷整個單詞列表，然后用 strip 和 lower 這兩個方法移除了標點符號，并且把所有字母都轉換成小寫的。（一定要記住，這里說的『轉換』是圖方便而已，實際上并不能轉換，要記住字符串是不可以修改的，strip 和 lower 這些方法都是返回了新的字符串，一定要記得！）
最終，process_line 函數通過建立新項或者累加已有項，對字頻統計 histogram 進行了更新。
要計算整個文件中的單詞總數，就可以把 histogram 中的所有頻數加到一起就可以了：
```py
def total_words(hist):
return sum(hist.values())
```
不重復的單詞的數目也就是字典中項的個數了：
```py
def different_words(hist):
return len(hist)
```
輸出結果的代碼如下：
```py
print('Total number of words:', total_words(hist))
print('Number of different words:', different_words(hist))
```
結果如下所示：
```py
Total number of words: 161080
Number of different words: 7214
```
## 13.4 最常用的單詞
要找到最常用的詞，可以做一個元組列表，每一個元組包含一個單詞和該單詞出現的次數，然后整理一下這個列表，就可以了。
下面的函數就接收了詞頻統計結果，然后返回一個『單詞-次數』元組組成的列表：
```py
def most_common(hist):
t = []
for key, value in hist.items():
t.append((value, key))
t.sort(reverse=True)
return t
```
這些元組中，要先考慮詞頻，返回的列表因此根據詞頻來排序。下面是一個輸出最常用單詞的循環體：
```py
t = most_common(hist)
print('The most common words are:')
for freq, word in t[:10]:
print(word, freq, sep='\t')
```
此處用了關鍵詞 sep 來讓 print 輸出的時候以一個 tab 跳表符來作為分隔，而不是一個空格，這樣第二列就會對齊。下面就是對《艾瑪》這本小說的統計結果：
(譯者注：這個效果在 Python 下很明顯，此處 markdown 我剛開始熟悉，不清楚咋實現。)
```py
The most common words are:
to 5242
the 5205
and 4897
of 4295
i 3191
a 3130
it 2529
her 2483
was 2400
she 2364
```
如果使用 sort 函數的 key 參數，上面的代碼還可以進一步簡化。如果你好奇的話，可以進一步閱讀一下[說明](https://wiki.python.org/moin/HowTo/Sorting)
## 13.5 可選的參數
咱們已經看過好多有可選參數的內置函數和方法了。實際上咱們自己也可以寫，寫這種有可選參數的自定義函數。比如下面就是一個根據詞頻數據來統計最常用單詞的函數：
```py
def print_most_common(hist, num=10):
t = most_common(hist)
print('The most common words are:')
for freq, word in t[:num]:
print(word, freq, sep='\t')
```
上面這個函數中，第一個參數是必須輸入的；而第二個參數就是可選的了。第二個參數 num 的默認值是 10.
如果只提供第一個參數：
```py
print_most_common(hist)
```
這樣 num 就用默認值了。如果提供兩個參數：
```py
print_most_common(hist, 20)
```
這樣 num 就用參數值來賦值了。換句話說，可選參數可以覆蓋默認值。
如果一個函數同時含有必需參數和可選參數，就必須在定義函數的時候，把必需參數全都放到前面，而可選的參數要放到后面。
## 13.6 字典減法
有的單詞存在于書當中，但沒有包含在文件 words.txt 的單詞列表中，找這些單詞就有點難了，你估計已經意識到了，這是一種集合的減法；也就是要從一個集合（也就是書）中所有不被另一個集合（也就是單詞列表）包含的單詞。
下面的代碼中定義的 subtrac t 這個函數，接收兩個字典 d1 和 d2，然后返回一個新字典，這個新字典包含所有 d1 中包含而 d2 中不包含的鍵。鍵值就無所謂了，就都設置為空即可。
```py
def subtract(d1, d2):
res = dict()
for key in d1:
if key not in d2:
res[key] = None
return res
```
要找到書中含有而 words.txt 中不含有的單詞，就可以用 process_file 函數來建立一個 words.txt 的詞頻統計，然后用 subtract 函數來相減：
```py
words = process_file('words.txt')
diff = subtract(hist, words)
print("Words in the book that aren't in the word list:")
for word in diff.keys():
print(word, end=' ')
```
下面依然還是對《艾瑪》得到的結果：
```py
Words in the book that aren't in the word list:
rencontre
jane's
blanche
woodhouses
disingenuousness
friend's
venice
apartment
...
```
這些單詞有的是名字或者所有格之類的。另外的一些，比如『rencontre』，都是現在不怎么常用的了。不過也確實有一些單詞是挺常用的，挺應該被列表所包含的！
### 練習 6
Python 提供了一個數據結構叫 set（集合），該類型提供了很多常見的集合運算。可以在 19.5 閱讀一下，或者閱讀一下[這里的官方文檔](http://docs.python.org/3/library/stdtypes.html#types-set)。
寫一個程序吧，用集合的減法，來找一下書中包含而列表中不包含的單詞吧。 [樣例代碼](http://thinkpython2.com/code/analyze_book2.py)。
## 13.7 隨機單詞
要從詞頻數據中選一個隨機的單詞，最簡單的算法就是根據已知的單詞頻率來將每個單詞復制相對應的個數的副本，然后組建成一個列表，從列表中選擇單詞：
```py
def random_word(h):
t = []
for word, freq in h.items():
t.extend([word] * freq)
return random.choice(t)
```
上面代碼中的[word] * freq 表達式建立了一個列表，列表中字符串單詞的出現次數即其原來的詞頻數。extend 方法和 append 方法相似，區別是前者的參數是一個序列，而后者是單獨的元素。
上面這個算法確實能用，但效率實在不怎么好；每次選擇隨機單詞的時候，程序都要重建列表，這個列表就和源書一樣大了。很顯然，一次性建立列表，而多次使用該列表來進行選擇，這樣能有明顯改善，但列表依然還是很大。
備選的思路如下：
1. 用鍵來存儲書中單詞的列表。
2. 再建立一個列表，該列表包含所有詞頻的累加總和（參考練習 2）。該列表的最后一個元素是書中所有單詞的總數 n。
3. 選擇一個 1 到 n 之間的隨機數。使用折半法搜索（參考練習 10），找到隨機數在累計總和中所在位置的索引值。
4. 用該索引值來找到單詞列表中對應的單詞。
### 練習 7
寫一個程序，用上面說的算法來從一本書中隨機挑選單詞。[樣例代碼](http://thinkpython2.com/code/analyze_book3.py)。
## 13.8 馬科夫分析法
如果讓你從一本書中隨機挑選一些單詞，這些單詞都能理解，但估計難以成為一句話：
```py
this the small regard harriet which knightley's it most things
```
一系列隨機次很少能組成整句的話，因為這些單詞連接起來并沒有什么關系。例如，成句的話中，冠詞 the 后面應該是跟著形容詞或者名詞，而不應該是動詞或者副詞。
衡量單詞之間關系的一種方法就是馬科夫分析法，這一方法就是：對給定的單詞序列，分析一個詞跟著另一個詞后面出現的概率。比如，Eric, the Half a Bee 這首歌的開頭：
```py
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?
```
在上面的文本中，『half the』這個詞組后面總是跟著『bee』，但詞組『the bee』后面可以是 『has』，也可以是 『is』。
馬科夫分析的結果是從每個前綴（比如『half the』和『the bee』）到所有可能的后綴（比如『has』和『is』）的映射。
有了這一映射，你就可以制造隨機文本了，用任意的前綴開頭，然后從可能的后綴中隨機選一個。下一次就把前綴的末尾和新的后綴結合起來，作為新的前綴，然后重復上面的步驟。
例如，你用前綴『Half a』來開始，那接下來的就必須是『bee』了，因為這個前綴只在文本中出現了一次。接下來，第二次了，前綴就變成了『a bee』了，所以接下來的后綴可以是『philosophically』, 『be』或者『due』。
在這個例子中，前綴的長度總是兩個單詞，但你可以以任意長度的前綴來進行馬科夫分析。
### 練習 8
Markov analysis 馬科夫分析：
1. 寫一個程序，讀取文件中的文本，然后進行馬科夫分析。結果應該是一個字典，從前綴到一個可能的后綴組成的序列的映射。這個序列可以是列表，元組，也可以是字典；你自己來選擇合適的類型來寫就好。你可以用兩個單詞長度的前綴來測試你的程序，但應該讓程序能夠兼容其他長度的前綴。
2. 在上面的程序中添加一個函數，基于馬科夫分析來生成隨機文本。下面是用《艾瑪》使用兩個單詞長度的前綴來生成的一個隨機文本樣例：
```py
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.
```
這個例子中，我保留了單詞中連接的標點符號。得到的結果在語法上基本是正確的，但也還差點。語義上，這些單詞連起來也還能有一些意義，但也不咋對勁。
如果增加前綴的單詞長度會怎么樣？隨機文本是不是讀起來更通順呢？
3. O 一旦你的程序能用了，你可以試試混搭一下：如果你把兩本以上的書合并起來，生成的隨機文本就會以很有趣的方式從多種來源混合單詞和短語來生成隨機文本。
引用：這個案例研究是基于 Kernighan 和 Pike 在 1999 年由 Addison-Wesley 出版社出版的《The Practice of Programming》一書中的一個例子。
你應該自己獨立嘗試一下這些練習，然后再繼續；然后你可以下載[我的樣例代碼](http://thinkpython2.com/code/markov.py)。另外你可能需要下載 [《艾瑪》這本書的文本文件](http://thinkpython2.com/code/emma.txt)。
## 13.9 數據結構
使用馬科夫分析來生成隨機文本挺有意思的，但這個練習還有另外一個要點：數據結構的選擇。在前面這些練習中，你必須要選擇以下內容：
* 如何表示前綴。
* 如何表示可能后綴的集合。
* 如何表示每個前綴與對應的后綴集合之間的映射。
最后一個最簡單了：明顯就應該用字典了，這樣來把每個鍵映射到對應的多個值。
前綴的選擇，明顯可以使用字符串、字符串列表，或者字符串元組。
后綴的先澤，要么是用列表，要么就用咱們之前寫過的詞頻函數 histogram（這個也是個字典）。
該咋選呢？第一步就是想一下，每種數據結構都需要用到哪些運算。比如對前綴來說，咱們就得能刪掉頭部，然后在尾部添加新詞。例如，加入現在的前綴是『Half a』，接下來的單詞是『bee』，就得能夠組成下一個前綴，也就是『a bee』。
你的首選估計就是列表了，因為列表很容易增加和剔除元素，但我們還需要能用前綴做字典中的鍵，所以列表就不合格了。那就剩元組了，元組沒法添加和刪除元素，但可以用加法運算符來建立新的元組。
```py
def shift(prefix, word):
return prefix[1:] + (word,)
```
上面這個 shift 函數，接收一個單詞的元組，也就是前綴，然后還接收一個字符串，也就是單詞了，然后形成一個新的元組，就是把原有的前綴去掉頭部，用新單詞拼接到尾部。
對后綴的集合來說，我們需要進行的運算包括添加新的后綴（或者增加一個已有后綴的頻次），然后選擇一個隨機的后綴。
添加新后綴，無論是用列表還是用詞頻字典，實現起來都一樣容易。不過從列表中選擇一個隨機元素很容易；但從詞頻字典中選擇隨機元素實現起來就不太有效率了（參考練習 7）。
目前為止，我們說完了實現難度，但對數據結構的選擇還要考慮一些其他的因素。比如運行時間。有時候要考慮理論上的原因來考慮，最好的數據結構要比其他的快；例如我之前提到了 in 運算符在字典中要比列表中速度快，最起碼當元素數量增多的時候會體現出來。
但一般情況下，咱們不能提前知道哪一種實現方法的速度更快。所以就可以兩種都寫出來，然后運行對比一下，看看到底哪個快。這種方法就叫對比測試。另外一種方法是選一個實現起來最簡單的數據結構，然后看看運行速度是不是符合問題的要求。如果可以，就不用再改進了。如果速度不夠快，就虧用到一些工具，比如 profile 模塊，來判斷程序的哪些部分消耗了最多的運行時間。
此外還要考慮的一個因素就是存儲空間了。比如用一個詞頻字典作為后綴集合就可能省一些存儲空間，因為無論這些單詞在穩重出現了多少次，在該字典中每個單詞只存儲一次。有的情況下，節省空間也能讓你的程序運行更快，此外在一些極端情況下，比如內存耗盡了，你的程序就根本無法運行了。不過對大多數應用來說，都是優先考慮運行時間，存儲空間只是次要因素了。
最后再考慮一下：上文中，我已經暗示了，咱們選擇某種數據結構，要兼顧分析和生成。但這二者是分開的步驟，所以也可以分析的時候用一種數據結構，而生成的時候再轉換成另外一種結構。只要生成時候節省的時間勝過轉換所花費的時間，相權衡之下依然是劃算的。
## 13.10 調試
調試一個程序的時候，尤其是遇到特別嚴峻的問題的時候，有以下五個步驟一定要做好：
* 閱讀代碼：
好好檢查代碼，多讀幾次，好好看看代碼所表述的內容是不是跟你的設想相一致。
* 運行程序：
做一些修改，然后運行各個版本來對比實驗一下。通常來說，只要你在程序對應的位置加上輸出，問題就能比較明確了，不過有時候你還是得搭建一些腳手架代碼來幫忙找錯誤。
* 反復思考：
多花點時間去思考！想下到底是什么類型的錯誤：語法，運行，還是語義錯誤？從錯誤信息以及程序的輸出能得到什么信息？想想哪種錯誤能引起你所看到的問題？問題出現之前的那一次你做了什么修改？
* 小黃鴨調試法：
如果你對另外一個人解釋問題，你有時候就能在問完問題之前就找到答案。通常你根本不用找另外一個人；就根一個橡膠鴨子說就可以了。這就是很著名的所謂小黃鴨調試法的起源了。我可不是瞎編的哈；看[這里的解釋](https://en.wikipedia.org/wiki/Rubber_duck_debugging)。
* 以退為進：
有時候，最佳的策略反而就是后撤，取消最近的修改，一直到程序恢復工作，并且你能清楚理解。然后再重頭來改進。
新手程序員經常會在上面這些步驟中的某一項上卡殼，然后忘了其他的步驟。上面的每一步都有各自的失靈情況。
比如，錯誤很典型的情況下，閱讀代碼也許有效，但如果錯誤是概念上誤解導致的，這就沒啥用了。如果你不理解你程序的功能，你就算讀上一百測也找不到錯誤，因為是你腦中的理解有錯誤。
在你進行小規模的簡單測試的時候，進行試驗會有用。但如果不思考和閱讀代碼，你就可以陷入到我稱之為『隨機走路編程』的陷阱中，這種過程就是隨機做一些修改，一直到程序工作位置。毋庸置疑，這種隨機修改肯定得浪費好多時間的。
最重要的就是思考，一定要花時間去思考。調試就像是一種實驗科學。你至少應該對問題的本質有一種假設。如果有兩種或者兩種以上的可能性，就要設計個測試，來逐個排除可能性。
然而一旦錯誤特別多了，再好的調試技術也不管用的，程序太大太復雜也會容易有類似情況。所以有時候最好的方法就是以退為進，簡化一下程序，直到能工作了，并且你能理解整個程序了為止。
新手程序員經常不愿意后撤，因為他們不情愿刪掉一行代碼（哪怕是錯誤的代碼）。可以這樣，復制一下整個代碼到另外一個文件中做個備份，然后再刪減，這樣是不是感覺好些。然后你可以再復制回來的。
找到一個困難問題的解決方法，需要閱讀、測試、分析，有時候還要后撤。如果你在某一步驟中卡住了，試試其他方法。
## 13.11 Glossary 術語列表
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 appears to be random, but is 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.
>對比測試：
rubber duck debugging:
Debugging by explaining your problem to an inanimate object such as a rubber duck. Articulating the problem can help you solve it, even if the rubber duck doesn’t know Python.
>小黃鴨調試法：對一個無生命的對象來解釋你的問題，比如小黃鴨之類的，這樣來調試。描述清楚問題很有助于解決問題，所以雖然小黃鴨并不會理解 Python 也不要緊。
## 13.12 練習
### 練習 9
單詞的『排名』就是在一個單詞列表中，按照出現頻率而排的位置：最常見的單詞就排名第一了，第二常見的就排第二，依此類推。
[Zipf 定律](http://en.wikipedia.org/wiki/Zipf's_law) 描述了自然語言中排名和頻率的關系。該定律預言了排名 r 與詞頻 f 之間的關系如下：
$$
f = cr^{?s}
$$
這里的 s 和 c 都是參數，依據語言和文本而定。如果對等式兩邊同時取對數，得到如下公式：
$$
\log f = \log c ? s*\log r
$$
（譯者注：Zipf 定律是美國學者 G.K.齊普夫提出的。可以表述為：在自然語言的語料庫里，一個單詞出現的頻率與它在頻率表里的排名成反比。）
因此如果你將 log f 和 log r 進行二維坐標系投點，就應該得到一條直線，斜率是-s，截距是 log c。
寫一個程序，從一個文件中讀取文本，統計單詞頻率，然后每個單詞一行來輸出，按照詞頻的降序，同時輸出一下 log f 和 log r。
選一種投圖程序，把結果進行投圖，然后檢查一下是否為一條直線。
能否估計一下 s 的值呢？
[樣例代碼](http://thinkpython2.com/code/zipf.py)。要運行剛剛這個代碼的話，你需要有投圖模塊 matplotlib。如果你安裝了 Anaconda，就已經有 matplotlib 了；或者你就可能需要安裝一下了。
（譯者注：matplotlib 的安裝方法有很多，比如 pip install matplotlib 或者 easy_install -U matplotlib）
