第十三章:案例研究:数据结构选择

目前为止,你已经学完了 Python 的核心数据结构,同时你也接触了利用到这些数据结构的一些算法。如果你希望学习更多算法知识, 那么现在是阅读第二十一章的好时机。 但是不必急着马上读,什么时候感兴趣了再去读即可。

本章是一个案例研究,同时给出了一些习题, 目的是启发你思考如何选择数据结构,并练习数据结构使用。

词频分析

和之前一样,在查看答案之前,你至少应该试着解答一下这些习题。

习题13-1

编写一个程序,读取一个文件,将每一行转换成单词列表, 删掉单词中的空格和标点,然后将它们转换为小写字母。

提示:string 模块提供了名为 whitespace 的字符串, 其包括空格、制表符、新行等等,以及名为 punctuation 的字符串, 其包括标点字符。试试能否让Python说脏话:

>>> import string
>>> string.punctuation
'!"#$%&'()*+,-./:;<=>?@[\]^_`{|}~'

同时,你可以考虑使用字符串方法 stripreplacetranslate

习题13-2

前往古腾堡项目(gutenberg.org),以纯文本格式下载你喜欢的已无版权保护的图书。

修改前面习题的程序,读取你下载的书, 跳过文件开始的头部信息,像之前那样处理其余的单词。

然后修改程序,计算书中单词的总数,以及每个单词使用的次数。

打印该书使用单词的总数。 比较不同年代、不同作者写的书。 哪个作者使用的词汇量最大?

习题13-3

修改上一个习题中的程序,打印书中最常使用的20个单词。

习题13-4

修改上一个习题中的程序,读取一个单词列表(见读取单词列表一节), 然后打印书中所有没有出现在该单词表中的单词。 它们中有多少是拼写错误的?有多少是词表中 应该 包括的常用词?有多少是生僻词?

随机数

给定相同的输入,大多数计算机程序每次都会生成相同的输出, 它们因此被称作确定性的(deterministic)。 确定性通常是个好东西,因为我们期望相同的计算产生相同的结果。 然而,对于有些应用,我们希望计算机不可预知。 游戏是一个明显的例子,但是不限于此。

让程序具备真正意义上的非确定性并不容易,但是有办法使它至少看起来是不确定的。 其中之一是使用生成伪随机(pseudorandom)数的算法。 伪随机数不是真正的随机数,因为它们由一个确定性的计算生成, 但是仅看其生成的数字,不可能将它们和随机生成的相区分开。

random模块提供了生成伪随机数(下文中简称为“随机数”)的函数。

函数 random 返回一个 0.0 到 1.0 之间的随机浮点数(包括 0.0 ,但是不包括 1.0 )。 每次调用 random ,你获得一个长序列中的下一个数。 举个例子,运行此循环:

import random

for i in range(10):
    x = random.random()
    print(x)

函数 randint 接受参数 lowhigh , 返回一个 lowhigh 之间的整数(两个都包括)。

>>> random.randint(5, 10)
5
>>> random.randint(5, 10)
9

你可以使用 choice ,从一个序列中随机选择一个元素:

>>> t = [1, 2, 3]
>>> random.choice(t)
2
>>> random.choice(t)
3

random模块提供的函数,还可以生成符合高斯、指数、伽马等连续分布的随机值。

习题13-5

编写一个名为choose_from_hist的函数, 其接受一个如字典作为计数器集合一节中定义的 histogram 对象作为参数, 并从该对象中返回一个随机值,其选择概率和值出现的频率成正比。 例如:

>>> t = ['a', 'a', 'b']
>>> hist = histogram(t)
>>> hist
{'a': 2, 'b': 1}

你的函数返回 'a' 的概率应该是