Think Python/字典

Think Python

一个字典类似于列表，但更通用。在列表中，索引必须是整数；在字典中，它们可以是（几乎）任何类型。

你可以将字典视为一组索引（称为键）和一组值之间的映射。每个键都映射到一个值。键和值的关联称为键值对，有时也称为项。

例如，我们将构建一个从英语到西班牙语单词的映射字典，因此键和值都是字符串。

函数dict创建一个没有项目的空字典。因为dict是内置函数的名称，所以应避免将其用作变量名。

>>> eng2sp = dict()
>>> print eng2sp
{}

波浪括号 {} 表示空字典。要向字典中添加项目，可以使用方括号

>>> eng2sp['one'] = 'uno'

此行创建了一个从键’one’映射到值 'uno' 的项。如果我们再次打印字典，我们将看到一个键值对，键和值之间用冒号分隔

>>> print eng2sp
{'one': 'uno'}

此输出格式也是输入格式。例如，您可以创建一个包含三个项目的字典

>>> eng2sp = {'one': 'uno', 'two': 'dos', 'three': 'tres'}

但是，如果您打印eng2sp，您可能会感到惊讶

>>> print eng2sp
{'one': 'uno', 'three': 'tres', 'two': 'dos'}

键值对的顺序不相同。事实上，如果您在您的计算机上键入相同的示例，您可能会得到不同的结果。通常，字典中项目的顺序是不可预测的。

但这不成问题，因为字典的元素永远不会用整数索引来索引。相反，您使用键来查找对应的值

>>> print eng2sp['two']
'dos'

键’two’始终映射到值 'dos'，因此项目的顺序无关紧要。

如果键不在字典中，则会引发异常

>>> print eng2sp['four']
KeyError: 'four'

该len函数适用于字典；它返回键值对的数量

>>> len(eng2sp)
3

该in运算符适用于字典；它告诉您某个内容是否作为字典中的键出现（作为值出现是不够的）。

>>> 'one' in eng2sp
True
>>> 'uno' in eng2sp
False

要查看某个内容是否作为字典中的值出现，您可以使用方法values，它将值作为列表返回，然后使用in运算符

>>> vals = eng2sp.values()
>>> 'uno' in vals
True

您可以对keys:

>>> kees = eng2sp.keys()
>>> ‘one’ in kees
True

该in运算符对列表和字典使用不同的算法。对于列表，它使用搜索算法，如第 8.6 节所述。随着列表变长，搜索时间与之成正比地变长。对于字典，Python 使用称为哈希表的算法，该算法具有一个显著的特性：该in运算符花费的时间大致相同，无论字典中有多少项。我不会解释这是如何实现的，但您可以在以下网站了解更多信息：wikipedia.org/wiki/Hash_table.

练习 1

编写一个函数，读取 words.txt 中的单词，并将它们存储为字典中的键。值是什么无关紧要。然后，您可以使用 in 运算符作为快速检查字符串是否在字典中的方法。

如果您完成了练习 '10.8'，则可以将此实现的速度与列表 'in' 运算符和二分查找进行比较。

字典作为计数器集合

假设您给定一个字符串，并且您想统计每个字母出现的次数。您可以用多种方法做到这一点

您可以为字母表中的每个字母创建一个 26 个变量。然后，您可以遍历字符串，对于每个字符，递增相应的计数器，可能使用链式条件。
您可以创建一个包含 26 个元素的列表。然后，您可以将每个字符转换为数字（使用内置函数ord），使用该数字作为列表中的索引，并递增相应的计数器。
您可以创建一个字典，其中字符作为键，计数器作为对应值。第一次看到某个字符时，您会向字典中添加一个项。之后，您将递增现有项的值。

这些选项中的每一个都执行相同的计算，但它们中的每一个都以不同的方式实现该计算。

实现是一种执行计算的方式；一些实现优于其他实现。例如，字典实现的一个优点是我们不必预先知道字符串中出现了哪些字母，并且我们只需要为确实出现的字母腾出空间。

以下是代码可能的样子

def histogram(s):
    d = dict()
    for c in s:
        if c not in d:
            d[c] = 1
        else:
            d[c] += 1
    return d

函数的名称是直方图，它是指一组计数器（或频率）的统计术语。

函数的第一行创建一个空字典。该for循环遍历字符串。每次循环时，如果字符c不在字典中，我们创建一个新的项，其键为c以及初始值 1（因为我们已经看到过这个字母一次）。如果c已经存在于字典中，我们递增d[c].

以下是它的工作原理

>>> h = histogram('brontosaurus')
>>> print h
{'a': 1, 'b': 1, 'o': 2, 'n': 1, 's': 2, 'r': 2, 'u': 2, 't': 1}

直方图表明字母’a’和 'b' 出现一次；'o' 出现两次，依此类推。

练习 2

字典有一个名为 'get' 的方法，它接收一个键和一个默认值。如果键出现在字典中，'get' 返回相应的值；否则，它返回默认值。例如

''>>> h = histogram('a')
>>> print h
{'a': 1}
>>> h.get('a', 0)
1
>>> h.get('b', 0)
0
''

使用 'get' 更简洁地编写 'histogram'。您应该能够消除 'if' 语句。

循环和字典

如果您在for语句中使用字典，它会遍历字典的键。例如，print_hist 打印每个键及其对应的值

def print_hist(h):
    for c in h:
        print c, h[c]

输出如下所示

>>> h = histogram('parrot')
>>> print_hist(h)
a 1
p 1
r 2
t 1
o 1

同样，键没有特定的顺序。

练习 3

字典有一个名为 'keys' 的方法，它以列表的形式返回字典的键，没有特定的顺序。

修改 print_hist 以按字母顺序打印键及其值。

反向查找

给定一个字典d和一个键k，很容易找到对应的值v = d[k]。此操作称为查找。

但是，如果您有v并且您想找到k？您有两个问题：首先，可能有多个键映射到值v。根据应用程序的不同，您可能能够选择一个，或者您可能需要创建一个包含所有这些键的列表。其次，没有简单的语法来执行反向查找；您必须搜索。

这是一个函数，它接收一个值并返回第一个映射到该值的键

def reverse_lookup(d, v):
    for k in d:
        if d[k] == v:
            return k
    raise ValueError

此函数是搜索模式的另一个示例，但它使用了我们以前从未见过的功能，raise。该raise语句会导致异常；在这种情况下，它会导致ValueError，这通常表示参数的值存在问题。

如果我们到达循环的末尾，这意味着v未作为字典中的值出现，因此我们引发异常。

以下是一个成功反向查找的示例

>>> h = histogram('parrot')
>>> k = reverse_lookup(h, 2)
>>> print k
r

以及一个不成功的示例

>>> k = reverse_lookup(h, 3)
Traceback (most recent call last):
  File "&lt;stdin>", line 1, in ?
  File "&lt;stdin>", line 5, in reverse_lookup
ValueError

引发异常时产生的结果与 Python 引发异常时相同：它打印回溯和错误消息。

该raise语句可以可选地接受一个详细的错误消息作为参数。例如

>>> raise ValueError, 'value does not appear in the dictionary'
Traceback (most recent call last):
  File "&lt;stdin>", line 1, in ?
ValueError: value does not appear in the dictionary

反向查找比正向查找慢得多；如果您必须经常执行反向查找，或者字典变得很大，程序的性能将会受到影响。

练习 4 修改 reverse_lookup 使其构建并返回一个包含所有映射到 v 的键的列表，如果没有则返回空列表。

字典和列表

列表可以作为字典中的值出现。例如，如果您得到一个将字母映射到频率的字典，您可能希望将其反转；也就是说，创建一个将频率映射到字母的字典。由于可能有多个字母具有相同的频率，因此反转后的字典中的每个值都应该是一个字母列表。

这是一个反转字典的函数

def invert_dict(d):
    inv = dict()
    for key in d:
        val = d[key]
        if val not in inv:
            inv[val] = [key]
        else:
            inv[val].append(key)
    return inv

每次循环时，key从d获取一个键，val获取相应的value。如果val不在inv中，这意味着我们以前从未见过它，因此我们创建一个新项并将其初始化为一个单例（包含单个元素的列表）。否则，我们之前见过此值，因此我们将相应的键追加到列表中。

这是一个例子

>>> hist = histogram('parrot')
>>> print hist
{'a': 1, 'p': 1, 'r': 2, 't': 1, 'o': 1}
>>> inv = invert_dict(hist)
>>> print inv
{1: ['a', 'p', 't', 'o'], 2: ['r']}

这是一个显示hist获取一个键，inv:

字典表示为一个框，其中包含类型dict在其上方，以及框内的键值对。如果值是整数、浮点数或字符串，我通常将它们绘制在框内，但我通常将列表绘制在框外，只是为了使图表更简单。

列表可以作为字典中的值，如本例所示，但不能作为键。以下是尝试时发生的情况

>>> t = [1, 2, 3]
>>> d = dict()
>>> d[t] = 'oops'
Traceback (most recent call last):
  File "&lt;stdin>", line 1, in ?
TypeError: list objects are unhashable

我之前提到过字典是使用哈希表实现的，这意味着键必须是可哈希的。

哈希是一个函数，它接受任何类型的value并返回一个整数。字典使用这些整数（称为哈希值）来存储和查找键值对。

如果键是不可变的，此系统可以正常工作。但是，如果键是可变的，例如列表，则会发生不好的事情。例如，当您创建键值对时，Python 会对键进行哈希处理并将其存储在相应的位置。如果您修改键然后再次对其进行哈希处理，它将转到另一个位置。在这种情况下，您可能对同一个键有两个条目，或者您可能无法找到键。无论哪种方式，字典都无法正常工作。

这就是为什么键必须是可哈希的，以及为什么像列表这样的可变类型不是可哈希的原因。解决此限制的最简单方法是使用元组，我们将在下一章中看到。

由于字典是可变的，因此不能用作键，但可以用作值。

练习 5

阅读字典方法 setdefault 的文档，并使用它编写更简洁的 invert_dict 版本。

备忘录

如果您玩过第 6.7 节中的fibonacci函数，您可能已经注意到，您提供的参数越大，函数运行的时间就越长。此外，运行时间会非常快地增加。

要了解原因，请考虑以下fibonacci的调用图，其中n=4:

调用图显示了一组函数帧，每帧都用线连接到其调用的函数的帧。在图的顶部，fibonacci的调用图，其中n=4调用fibonacci的调用图，其中n=3获取一个键，n=2。依此类推，fibonacci的调用图，其中n=3调用fibonacci的调用图，其中n=2获取一个键，n=1。等等。

计算fibonacci(0)获取一个键，fibonacci(1)被调用的次数。这是一个低效的解决方案，并且随着参数的增大而变得更糟。

一种解决方案是跟踪已经计算过的值，方法是将它们存储在字典中。为以后使用而存储的先前计算的值称为备忘录^[1]。以下是使用备忘录实现的fibonacci。

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是一个字典，用于跟踪我们已经知道的斐波那契数。它以两个项目开始：0 映射到 0，1 映射到 1。

每当fibonacci被调用时，它都会检查known。如果结果已存在，则可以立即返回。否则，它必须计算新值，将其添加到字典中，然后返回它。

练习 6

运行此版本的“fibonacci”和原始版本，并使用一系列参数，比较它们的运行时间。

全局变量

在前面的示例中，known是在函数外部创建的，因此它属于名为 __main__ 的特殊帧。__main__ 中的变量有时称为全局变量，因为可以从任何函数访问它们。与在函数结束时消失的局部变量不同，全局变量会从一个函数调用持续到下一个函数调用。

通常使用全局变量作为标志；也就是说，布尔变量指示（标志）某个条件是否为真。例如，某些程序使用名为verbose的标志来控制输出的详细程度

verbose = True

def example1():
    if verbose:
        print 'Running example1'

如果您尝试重新分配全局变量，您可能会感到惊讶。以下示例旨在跟踪函数是否已被调用

been_called = False

def example2():
    been_called = True         # WRONG

但是，如果您运行它，您会发现 been_called 的值不会改变。问题在于example2创建了一个名为 been_called 的新局部变量。局部变量在函数结束时消失，并且对全局变量没有影响。

要在函数内部重新分配全局变量，您必须在使用它之前声明全局变量

been_called = False

def example2():
    global been_called 
    been_called = True

该global语句告诉解释器类似于“在此函数中，当我使用 been_called 时，我的意思是全局变量；不要创建局部变量”。

这是一个尝试更新全局变量的示例

count = 0

def example3():
    count = count + 1          # WRONG

如果您运行它，您将获得

UnboundLocalError: local variable 'count' referenced before assignment

Python 假设count是局部的，这意味着您在写入之前正在读取它。解决方案，同样，是声明countglobal。

def example3():
    global count
    count += 1

如果全局值是可变的，则可以在不声明它的情况下修改它

known = {0:0, 1:1}

def example4():
    known[2] = 1

因此，您可以添加、删除和替换全局列表或字典中的元素，但如果您想重新分配变量，则必须声明它

def example5():
    global known
    known = dict()

长整数

如果您计算fibonacci(50)，您将获得

>>> fibonacci(50)
12586269025L

该L结尾处的表示结果是长整数^[2]，或类型long.

类型为int的值具有有限的范围；长整数可以任意大，但随着它们变得越来越大，它们会消耗更多空间和时间。

数学运算符适用于长整数，以及math模块中的函数，因此一般来说，任何与int一起工作的代码也将与long.

一起工作。任何时候计算结果太大而无法用整数表示时，Python 会将结果转换为长整数

>>> 1000 * 1000
1000000
>>> 100000 * 100000
10000000000L

在第一种情况下，结果的类型为int；在第二种情况下，它是long.

练习 7

大整数的指数运算是一些常用公钥加密算法的基础。阅读维基百科上关于 RSA 算法^[3]的页面，并编写用于编码和解码消息的函数。

调试

当您使用更大的数据集时，手动打印和检查数据进行调试可能会变得笨拙。以下是一些调试大型数据集的建议

缩减输入: 如果可能，请减少数据集的大小。例如，如果程序读取文本文件，请从前 10 行开始，或使用您可以找到的最小的示例。您可以编辑文件本身，或者（更好）修改程序，使其仅读取前n行。如果存在错误，您可以将n减少到能够显示错误的最小值，然后在找到并纠正错误时逐渐增加它。
检查摘要和类型: 与其打印和检查整个数据集，不如考虑打印数据的摘要：例如，字典中的项目数或数字列表的总和。运行时错误的常见原因是值类型不正确。为了调试此类错误，通常足以打印值的类型。
编写自检: 有时你可以编写代码来自动检查错误。例如，如果你正在计算一组数字的平均值，你可以检查结果是否不超过列表中的最大元素或小于最小元素。这被称为“健全性检查”，因为它检测“不合理”的结果。另一种检查方法是比较两个不同计算的结果，以查看它们是否一致。这被称为“一致性检查”。
漂亮打印输出: 格式化调试输出可以更容易地发现错误。我们在第 6.9 节中看到了一个示例。pprint模块提供了一个pprint函数，该函数以更易于人类阅读的格式显示内置类型。

同样，花在构建脚手架上的时间可以减少花在调试上的时间。

词汇表

字典: 从一组键到其对应值的映射。
键值对: 从键到值的映射的表示。
项目: 键值对的另一个名称。
key: 作为键值对第一部分出现在字典中的对象。
值: 作为键值对第二部分出现在字典中的对象。这比我们之前使用“值”一词更具体。
实现: 执行计算的一种方法。
哈希表: 用于实现 Python 字典的算法。
哈希函数: 哈希表用来计算键位置的函数。
可哈希的: 具有哈希函数的类型。不可变类型（如整数、浮点数和字符串）是可哈希的；可变类型（如列表和字典）不可哈希。
查找: 字典操作，它接收一个键并找到对应的值。
反向查找: 字典操作，它接收一个值并找到映射到它的一个或多个键。
单例: 具有单个元素的列表（或其他序列）。
调用图: 一个图表，显示程序执行期间创建的每个框架，从每个调用者到每个被调用者都有一条箭头。
直方图: 一组计数器。
备忘录: 存储的计算值，以避免不必要的未来计算。
全局变量: 在函数外部定义的变量。可以从任何函数访问全局变量。
标志: 用于指示条件是否为真的布尔变量。
声明: 像global这样的语句告诉解释器有关变量的信息。

练习-8

        Dictionaries have a method called 'keys' that returns the keys of the dictionary, in

没有特定的顺序，作为列表。修改 print_hist 以按字母顺序打印键及其值。

练习 9

如果您可以旋转其中一个单词并得到另一个单词，则两个单词是“旋转对”（请参阅练习 '8.12' 中的 rotate_word ）。

编写一个程序，读取单词列表并找到所有旋转对。

练习 10

这是来自 Car Talk^[4]的另一个难题：

这是丹·奥利里发送的。他最近遇到一个常见的单音节五字母词，它具有以下独特属性。当您删除第一个字母时，剩余的字母构成原始单词的同音词，即发音完全相同的词。替换第一个字母，即放回它并删除第二个字母，结果是原始单词的另一个同音词。问题是，这个词是什么？
现在我将举一个不成功的例子。让我们看看五字母词“wrack”。W-R-A-C-K，你知道，就像“wrack with pain”。如果我删除第一个字母，我将得到一个四字母词，“R-A-C-K”。就像“天哪，你看到那只雄鹿的角了吗？它一定是一个九点！”这是一个完美的同音词。如果你把“w”放回去，然后删除“r”，你就会得到“wack”这个词，它是一个真实的词，但它不是其他两个词的同音词。
但是，确实至少有一个单词，丹和我们知道的，如果你删除前两个字母中的任何一个以创建两个新的四字母词，它将产生两个同音词。问题是，这个词是什么？

您可以使用练习 '11.1' 中的字典来检查字符串是否在单词列表中。

要检查两个单词是否为同音词，您可以使用 CMU 发音词典。您可以从 www.speech.cs.cmu.edu/cgi-bin/cmudict 或 thinkpython.com/code/c06d 下载它，您还可以下载 thinkpython.com/code/pronounce.py ，它提供了一个名为 read_dictionary 的函数，该函数读取发音词典并返回一个 Python 字典，该字典将每个单词映射到描述其主要发音的字符串。

编写一个程序，列出解决此难题的所有单词。您可以在 thinkpython.com/code/homophone.py 上看到我的解决方案。

注释

↑ 请参阅 wikipedia.org/wiki/Memoization
↑ 在 Python 3.0 中，long 类型消失了；所有整数，即使是非常大的整数，也都是 int 类型。
↑ wikipedia.org/wiki/RSA
↑ www.cartalk.com/content/puzzler/transcripts/200717

[1] 请参阅 wikipedia.org/wiki/Memoization

[2] 在 Python 3.0 中，long 类型消失了；所有整数，即使是非常大的整数，也都是 int 类型。

[3] wikipedia.org/wiki/RSA

[4] www.cartalk.com/content/puzzler/transcripts/200717

[1]

[2]

[3]

[4]