MIT 6.0001：Python 计算和编程入门第三版（二）

原文：zh.z-lib.gs/md5/b81f9400901fb07c6e4e456605c4cd1f

译者：飞龙

协议：CC BY-NC-SA 4.0

第八章：测试和调试

我们不想提起这一点，但庞格洛斯博士⁴⁹错了。我们并不生活在“所有可能世界中最好的世界”里。有些地方降雨太少，有些地方降雨太多。有些地方太冷，有些地方太热，有些地方夏天太热而冬天太冷。有时股市大幅下跌。有时作弊者会赢（参见休斯顿太空人队）。而且令人恼火的是，我们的程序并不总是在第一次运行时就正常工作。

关于如何处理最后一个问题已经有书籍问世，从这些书中有很多可以学习的东西。然而，为了给你提供一些可能帮助你按时完成下一个问题集的提示，本章提供了这一主题的高度浓缩讨论。虽然所有的编程示例都是用 Python 写的，但一般原则适用于让任何复杂系统正常工作。

测试是运行程序以试图确定其是否按预期工作的过程。调试是尝试修复一个你已经知道不按预期工作的程序的过程。

测试和调试并不是你在程序构建后才应该考虑的过程。优秀的程序员以更容易进行测试和调试的方式设计他们的程序。做到这一点的关键是将程序拆分成可以独立实现、测试和调试的组件。在本书的这一点上，我们只讨论了一种模块化程序的机制，即函数。因此，目前为止，我们的所有示例将围绕函数进行。当我们涉及其他机制，特别是类时，我们会回到本章讨论的一些主题。

使程序正常工作的第一步是让语言系统同意运行它——也就是说，消除那些在不运行程序的情况下就能检测到的语法错误和静态语义错误。如果你在编程中还没有过这一关，那你还不准备好进入本章。多花点时间做一些小程序，然后再回来。

8.1 测试

测试的目的是显示存在错误，而不是证明程序没有错误。引用艾兹格·迪杰斯特拉的话：“程序测试可以用来显示错误的存在，但永远不能证明它们的缺失！” ⁵⁰ 或者，正如阿尔伯特·爱因斯坦所说：“任何实验都无法证明我正确；一个实验可以证明我错误。”

为什么会这样？即使是最简单的程序也有数十亿种可能的输入。比如，考虑一个声称满足规格的程序。

def is_smaller(x, y):
     """Assumes x and y are ints
        Returns True if x is less than y and False otherwise."""

在所有整数对上运行它，至少可以说是乏味的。我们能做的最好是对那些在程序中存在错误的情况下，有合理概率产生错误答案的整数对进行测试。

测试的关键在于找到一个输入集合，称为测试套件（test suite），它有较高的可能性揭示缺陷，但运行时间不应过长。做到这一点的关键是将所有可能输入的空间划分为提供关于程序正确性的等效信息的子集，然后构建一个包含每个划分至少一个输入的测试套件。（通常，构建这样的测试套件实际上是不可能的。可以将其视为一个不可实现的理想。）

一个集合的划分将该集合分为一组子集，使得原集合的每个元素正好属于一个子集。例如，考虑is_smaller(x, y)。可能输入的集合是所有整数的成对组合。划分这个集合的一种方式是将其分为九个子集：

`x positive, y positive, x < y x positive, y positive, y < x x negative, y negative, x < y x negative, y negative, y < x x negative, y positive x positive, y negative x = 0, y = 0 x = 0, y` `≠ 0 x ≠ 0, y = 0`

如果我们在这些子集的每个值上测试实现，如果存在缺陷，我们有很好的机会（但没有保证）暴露出该缺陷。

对于大多数程序，找到良好的输入划分远比说起来容易。通常，人们依赖于基于探索代码和规范某种组合的不同路径的启发式方法。基于通过代码探索路径的启发式方法属于透明盒（glass-box）（或白盒（white-box））测试类。基于通过规范探索路径的启发式方法属于黑盒测试（black-box testing）类。

8.1.1 黑盒测试

原则上，黑盒测试是在不查看要测试代码的情况下构建的。黑盒测试允许测试人员和实现人员来自不同的群体。当我们这些教授编程课程的人为分配给学生的问题集生成测试用例时，我们正在开发黑盒测试套件。商业软件的开发者通常拥有与开发组基本独立的质量保证组。他们也会开发黑盒测试套件。

这种独立性降低了生成测试套件时错误与代码中错误相关联的可能性。例如，假设程序的作者做出了隐含但无效的假设，即一个函数永远不会被负数调用。如果同一个人构建了程序的测试套件，他很可能会重复这个错误，而不测试负参数的函数。

黑盒测试的另一个积极特征是它对实现变化的鲁棒性。由于测试数据是在不知实现的情况下生成的，因此实现变更时测试无需更改。

正如我们之前所说，生成黑盒测试数据的一个好方法是通过规范探索路径。考虑这个规范。

def sqrt(x, epsilon):
    """Assumes x, epsilon floats
               x >= 0
               epsilon > 0
       Returns result such that
               x-epsilon <= result*result <= x+epsilon"""

在这个规范中似乎只有两条不同的路径：一条对应于x = 0，另一条对应于x > 0。然而，常识告诉我们，虽然必须测试这两种情况，但这远远不够。

边界条件也应进行测试。查看类型为列表的参数通常意味着查看空列表、只有一个元素的列表、不可变元素的列表、可变元素的列表，以及包含列表的列表。处理数字时，通常意味着查看非常小和非常大的值以及“典型”值。例如，对于sqrt，尝试值x和epsilon与图 8-1 中的值相似可能是有意义的。

图 8-1 测试边界条件

前四行旨在表示典型案例。注意，x的值包括一个完全*方数、一个小于一的数和一个具有无理*方根的数。如果这些测试中的任何一个失败，则程序中存在需要修复的错误。

剩余的行测试x和epsilon的极大和极小值。如果这些测试中的任何一个失败，就需要修复某些内容。可能代码中存在一个需要修复的错误，或者可能需要更改规范，以便更容易满足。例如，期望在epsilon极小的情况下找到*方根的*似值可能是不合理的。

另一个重要的边界条件是别名。考虑代码

def copy(L1, L2):
    """Assumes L1, L2 are lists
       Mutates L2 to be a copy of L1"""
    while len(L2) > 0: #remove all elements from L2
        L2.pop() #remove last element of L2
    for e in L1: #append L1's elements to initially empty L2
        L2.append(e)

这通常可以正常工作，但在L1和L2指向同一列表时则不然。任何未包含形式为copy(L, L)的调用的测试套件，都无法揭示这个错误。

8.1.2 玻璃盒测试

黑箱测试绝不能被跳过，但它通常是不够的。没有查看代码的内部结构，无法知道哪些测试用例可能提供新信息。考虑这个简单的例子：

def is_prime(x):
    """Assumes x is a nonnegative int
       Returns True if x is prime; False otherwise"""
    if x <= 2:
        return False
    for i in range(2, x):
        if x%i == 0:
            return False
    return True

查看代码后，我们可以看到由于测试if x <= 2，值0、1和2被视为特例，因此需要进行测试。如果不查看代码，可能不会测试is_prime(2)，因此不会发现函数调用is_prime(2)返回False，错误地表示2不是素数。

玻璃盒测试套件通常比黑盒测试套件更容易构建。规范（包括本书中的许多规范）通常是不完整的，且相当粗糙，这使得估计黑盒测试套件对有趣输入空间的探索程度变得具有挑战性。相比之下，代码路径的概念是明确的，评估探索的彻底程度相对容易。实际上，有商业工具可用于客观地测量玻璃盒测试的完整性。

一个玻璃盒测试套件是路径完整的，如果它测试程序中的每一个潜在路径。这通常是无法实现的，因为它取决于每个循环执行的次数和每次递归的深度。例如，递归实现的阶乘对每个可能的输入遵循不同的路径（因为递归的层数不同）。

此外，即使是路径完整的测试套件也不能保证所有的 bug 都会被暴露。考虑：

def abs(x):
    """Assumes x is an int
       Returns x if x>=0 and –x otherwise"""
    if x < -1:
        return -x
    else:
        return x

规范建议有两种可能情况：x要么为负，要么不是。这表明输入集合{2, -2}足以探索规范中的所有路径。这个测试套件还有一个额外的优点，就是强迫程序遍历所有路径，因此它看起来像是一个完整的玻璃盒测试套件。唯一的问题是，这个测试套件不会暴露abs(-1)会返回-1的事实。

尽管玻璃盒测试存在局限性，但通常值得遵循一些经验法则：

• 针对所有if语句的两个分支都要进行测试。

• 确保每个except子句（见第九章）都被执行。

• 对于每个for循环，设置测试用例，其中

  • ○ 循环未被进入（例如，如果循环是迭代列表中的元素，请确保在空列表上进行测试）。

  • ○ 循环体被执行恰好一次。

  • ○ 循环体被执行多于一次。

• 对于每个while循环

  • ○ 查看与处理for循环时相同类型的情况。

  • ○ 包含对应于所有可能退出循环的测试用例。例如，对于一个以

  • while len(L) > 0 and not L[i] == e

  • 找到由于len(L)大于零而退出循环的情况，以及由于L[i] == e而退出循环的情况。

• 对于递归函数，包含导致函数在没有递归调用、恰好一次递归调用和多于一次递归调用时返回的测试用例。

8.1.3 进行测试

测试通常被认为分为两个阶段。应始终从单元测试开始。在这个阶段，测试人员构建并运行旨在确定单个代码单元（例如函数）是否正常工作的测试。接下来是集成测试，旨在确定单元组合在一起时是否正常工作。最后，功能测试用于检查程序整体是否按预期行为。实际上，测试人员在这些阶段之间循环，因为集成或功能测试中的失败会导致对单个单元进行更改。

功能测试几乎总是最具挑战性的阶段。整个程序的预期行为比每个部分的预期行为更难以表征。例如，表征文字处理器的预期行为要比表征计算文档中字符数的子系统的行为困难得多。规模问题也可能使功能测试变得困难。功能测试耗时数小时甚至数天并不罕见。

许多工业软件开发组织设有独立于实施软件的团队的软件质量保证（SQA）小组。SQA 小组的使命是确保软件在发布之前适合其预期目的。在某些组织中，开发小组负责单元测试，而质量保证小组负责集成和功能测试。

在工业界，测试过程通常高度自动化。测试人员⁵¹不会坐在终端上输入数据和检查输出。相反，他们使用测试驱动程序，这些驱动程序能够自主执行。

• 设置需要调用程序（或单元）进行测试的环境。

• 使用预定义或自动生成的输入序列调用程序（或单元）进行测试。

• 保存这些调用的结果。

• 检查测试结果的可接受性。

• 准备一份适当的报告。

在单元测试过程中，我们通常需要构建桩和驱动程序。驱动程序模拟使用被测单元的程序部分，而桩则模拟被测单元使用的程序部分。桩很有用，因为它们允许人们测试依赖于尚未存在的软件或有时甚至是硬件的单元。这使得程序员团队能够同时开发和测试系统的多个部分。

理想情况下，桩应该

• 检查调用者提供的环境和参数的合理性（用不当参数调用函数是一种常见错误）。

• 以与规范一致的方式修改参数和全局变量。

• 返回与规范一致的值。

构建足够的桩常常是一项挑战。如果桩所替代的单元旨在执行某些复杂任务，构建一个与规范一致的桩可能相当于编写桩所设计替代的程序。克服这个问题的一种方法是限制桩接受的参数集，并创建一个包含每种参数组合的返回值的表。

自动化测试过程的一个吸引力是它促进了回归测试。当程序员试图调试一个程序时，安装一个“修复”通常会破坏曾经正常工作的一些或多个功能。无论做出多小的改变，都应检查程序是否仍通过所有之前通过的测试。

8.2 调试

关于修复软件缺陷的过程为何被称为调试，有一个迷人的都市传说。图 8-2 中的照片是一份来自 1947 年 9 月的实验室记录，记录了哈佛大学 Mark II 艾肯继电器计算机组的工作。注意页面上贴着的蛾子和下面的短语“第一次发现的 bug”。

图 8-2 不是第一个 bug

有人声称，困在 Mark II 中的那只不幸的蛾子的发现导致了“调试”这一短语的使用。然而，措辞“第一次发现的真实案例”暗示这个短语的更不字面化的解释已经相当普遍。Mark II 项目的领导者格雷斯·穆雷·霍普明确表示，“bug”一词在二战期间已经被广泛用来描述电子系统的问题。而在此之前，霍金斯电力新教义这本 1896 年的电力手册中已包含条目：“‘bug’一词在有限的范围内用来指代电器连接或工作中的任何故障或问题。”在英语中，“bugbear”一词意为“导致似乎无谓或过度恐惧或焦虑的任何事物”。莎士比亚似乎把这个缩短为“bug”，当他让哈姆雷特抱怨“我生活中的 bug 和小鬼”时。

“bug”一词的使用有时会让人忽视一个基本事实：如果你编写了一个程序并且它有一个“bug”，那么是你犯了错。错误不会自然而然地出现在完美的程序中。如果你的程序有 bug，那是因为你把它放进去了。错误不会在程序中繁殖。如果你的程序有多个 bug，那是因为你犯了多个错误。

运行时错误可以沿两个维度进行分类：

• 明显→隐蔽：一个明显的 bug有明显的表现，例如程序崩溃或运行时间远长于应有的时间（可能永远）。一个隐蔽的 bug没有明显的表现。程序可能顺利运行到结束——只是提供了错误的答案。许多 bug 介于这两种极端之间，bug 是否明显可能取决于你多仔细地检查程序的行为。

• 持久性 → 间歇性：持久性错误是在相同输入下，每次运行程序时都会发生的错误。间歇性错误则只在某些情况下发生，即使程序在相同输入和看似相同条件下运行。当我们进入第十六章时，将探讨在随机性起作用的情况下建模的程序。这类程序中，间歇性错误是很常见的。

最好的错误是明显且持久的。开发人员不应抱有部署该程序的幻想。如果其他人傻到尝试使用它，他们会迅速意识到自己的愚蠢。也许程序会在崩溃之前做一些可怕的事情，例如删除文件，但至少用户会有理由感到担忧（甚至恐慌）。优秀的程序员会尽量以一种方式编写程序，使编程错误导致的缺陷既明显又持久。这通常被称为防御性编程。

进入不理想状态的下一步是明显但间歇性的错误。一个几乎总能计算出飞机正确位置的空中交通管制系统，远比一个总是犯明显错误的系统危险。人们可能会在虚幻的乐园中生活一段时间，甚至将有缺陷的程序部署，但迟早这个错误会显现出来。如果促使错误显现的条件容易重现，通常相对容易追踪和修复问题。如果导致错误的条件不明确，生活就会变得困难得多。

以隐蔽方式失败的程序往往非常危险。由于它们表面上并没有明显问题，人们使用并信任它们能正确执行任务。社会日益依赖软件进行超出人类能力范围的关键计算，甚至无法验证其正确性。因此，一个程序可能会在长时间内提供未被发现的错误答案。这类程序造成的损害是巨大的。⁵⁴ 评估抵押债券投资组合风险的程序若输出错误答案，可能会让银行（甚至整个社会）陷入麻烦。飞行管理计算机中的软件可能决定飞机是否能继续飞行。⁵⁵ 对于癌症患者来说，放射治疗机器若提供多或少的辐射，都可能是生与死的区别。偶尔发生隐蔽错误的程序，可能不会比总是出错的程序造成更少的破坏。隐蔽且间歇性出现的错误几乎总是最难发现和修复的。

8.2.1 学习调试

调试是一项学习技能。没有人能够凭直觉做到这一点。好消息是，它并不难学，而且是一项可转移的技能。用于调试软件的相同技能可以用于发现其他复杂系统中的问题，例如实验室实验或生病的人。

在过去的四十多年里，人们一直在构建称为调试器的工具，调试工具已经内置于所有流行的 Python IDE 中。（如果你还没试过，建议尝试 Spyder 中的调试工具。）这些工具可以提供帮助。但更重要的是你如何看待这个问题。许多经验丰富的程序员甚至不使用调试工具，而是依赖于print语句。

当测试表明程序表现出不理想的行为时，调试便开始了。调试是寻找该行为解释的过程。持续优秀调试的关键是在进行搜索时保持系统性。

首先，研究可用的数据。这包括测试结果和程序文本。研究所有测试结果。不仅要检查揭示问题存在的测试，还要检查那些似乎完美工作的测试。试图理解为什么一个测试有效而另一个无效常常会很有启发性。在查看程序文本时，要记住你并不完全理解它。如果你理解了，可能就不会有错误。

接下来，形成一个你认为与所有数据一致的假设。这个假设可以像“如果我将第 403 行从x < y改为x <= y，问题就会消失”那样狭窄，也可以像“我的程序不工作是因为我忘记了多个地方可能存在别名问题”那样广泛。

接下来，设计并运行一个可重复的实验，以可能驳斥这个假设。例如，你可以在每个循环前后放置打印语句。如果这些打印语句总是成对出现，那么循环导致非终止的假设就被驳斥了。在运行实验之前决定如何解释各种可能的结果。所有人都受到心理学家称之为确认偏误的影响——我们以一种强化我们想要相信的方式来解释信息。如果你在运行实验后才考虑结果应该是什么，你更可能落入一厢情愿的思维陷阱。

最后，记录你尝试过的实验。当你花了很多小时更改代码以试图追踪一个难以捉摸的错误时，很容易忘记你已经尝试过什么。如果你不小心，你可能会浪费太多时间反复尝试相同的实验（或者更可能是看似不同但会给你相同信息的实验）。记住，正如许多人所说，“疯狂就是不断重复相同的事情，却期待不同的结果。” ⁵⁶

8.2.2 设计实验

将调试视为一个搜索过程，每个实验都是试图缩小搜索空间的尝试。缩小搜索空间的一种方法是设计一个实验，用于判断代码的特定区域是否对在测试中发现的问题负责。另一种缩小搜索空间的方法是减少需要引发 bug 表现的测试数据量。

让我们看一个虚构的例子，看看你可能如何进行调试。想象一下，你在图 8-3 中编写了回文检查代码。

图 8-3 有 bug 的程序

现在，想象一下你对自己的编程技能充满信心，以至于将这段代码上传到网络上——没有经过测试。进一步假设你收到了一个电子邮件，上面写着：“我通过输入圣经中的 3,116,480 个字母测试了你的!!**!程序，你的程序打印了是。然而任何傻瓜都能看出圣经不是回文。修复它！（是你的程序，不是圣经。）”

你可以尝试在圣经上测试它。但开始时尝试在更小的东西上可能更明智。实际上，测试一个最小的非回文字符串是有意义的，例如，

>>> silly(2)
Enter element: a
Enter element: b

好消息是，它甚至未能通过这个简单测试，因此你不必输入数百万个字符。坏消息是，你不知道为什么它失败了。

在这种情况下，代码足够小，你可能可以盯着它找到 bug（或多个 bug）。不过，让我们假装它太大而无法做到这一点，开始系统地缩小搜索空间。

最好的方法通常是进行二分搜索。找到代码中大约一半的某个点，并设计一个实验，以便在该点之前判断是否存在可能与症状相关的问题。（当然，该点之后可能也有问题，但通常最好一次解决一个问题。）在选择这样一个点时，寻找一些容易检查的中间值，这些值能提供有用的信息。如果某个中间值不是你所期望的，那么很可能在代码的那个点之前就发生了问题。如果所有中间值看起来都正常，bug 可能出现在代码的后面。这个过程可以重复进行，直到你将问题所在的区域缩小到几行代码，或者如果你在测试一个大型系统，则缩小到几个单元。

查看 silly，中途点大约在 if is_pal(result) 行。显而易见的检查是 result 是否具有预期值 ['a', 'b']。我们通过在 silly 的 if 语句之前插入 print(result) 语句来检查这一点。当实验运行时，程序打印 ['b']，这表明事情已经出错。下一步是在循环中大约中途打印值 result。这很快揭示 result 从未超过一个元素，表明 result 的初始化需要移到 for 循环之外。

“修正后的” silly 代码是

def silly(n):
    """Assumes n is an int > 0
        Gets n inputs from user
        Prints 'Yes' if the sequence of inputs forms a palindrome;
            'No' otherwise"""
    result = []
    for i in range(n):
        elem = input('Enter element: ')
        result.append(elem)
    print(result)
    if is_pal(result):
        print('Yes')
    else:
        print('No')

让我们试试这个，看看 for 循环后 result 是否有正确的值。确实如此，但不幸的是程序仍然打印 Yes。现在，我们有理由相信第二个错误出现在 print 语句下方。因此，让我们查看 is_pal。插入这一行

`print(temp, x)` 

return 语句之前。当我们运行代码时，我们发现 temp 的值是预期的，但 x 不是。向上移动代码，我们在代码行 temp = x 后插入了一个 print 语句，发现 temp 和 x 的值都是 ['a', 'b']。快速检查代码后发现，在 is_pal 中我们写成了 temp.reverse 而不是 temp.reverse()——temp.reverse 的评估返回了列表的内置 reverse 方法，但并没有调用它。

我们再次运行测试，现在似乎 temp 和 x 的值都是 ['b', 'a']。我们已经将错误缩小到一行。看起来 temp.reverse() 意外地改变了 x 的值。一个别名错误出现了：temp 和 x 是同一个列表的名称，在列表被反转之前和之后都是如此。修复这个错误的一种方法是将 is_pal 中的第一个赋值语句替换为 temp = x[:]，这会创建 x 的一个副本。

修正后的 is_pal 版本是

def is_pal(x):
    """Assumes x is a list
        Returns True if the list is a palindrome; False otherwise"""
    temp = x[:]
    temp.reverse()
    return temp == x

8.2.3 当事情变得棘手时

约瑟夫·P·肯尼迪，美国总统约翰·F·肯尼迪的父亲，曾声称告诫他的孩子们：“当事情变得棘手时，强者开始行动。” ⁵⁷但他从未调试过一段软件。这个小节包含一些关于调试变得棘手时该怎么办的务实提示。

• 寻找常见问题。你是否在

  • ○ 以错误的顺序向函数传递参数？

  • ○ 拼写错误的名字，例如，在应该大写字母时打成小写字母？

  • ○ 未能重新初始化变量？

  • ○ 测试两个浮点值是否相等 (==)，而不是*似相等（记住，浮点运算与你在学校学的算术是不同的）？

  • ○ 在需要测试对象相等性时（例如，使用表达式 L1 == L2 比较两个列表）测试值相等性（例如，id(L1) == id(L2)）？

  • ○ 忘记某个内置函数有副作用？

  • ○ 忘记了将一个对 function 类型对象的引用转换为函数调用的 ()？

  • ○ 创建了一个无意的别名？

  • ○ 是否犯了你典型的其他错误？

• 停止问自己为什么程序没有按照你的想法运行。相反，问问自己为什么它会这样运行。 这个问题应该更容易回答，也可能是找出如何修复程序的第一步。

• 记住，错误可能不在你认为的地方。 如果在，你早就找到了。决定查看哪里的一个实用方法是问问错误不可能出现在哪里。正如福尔摩斯所说：“排除所有其他因素，剩下的那个必须是真相。” ⁵⁸

• 尝试向其他人解释这个问题。 我们都会产生盲点。仅仅尝试向某人解释问题，通常会让你看到自己遗漏的地方。你还可以尝试解释为什么这个错误不可能出现在某些地方。

• 不要相信你看到的一切。**⁵⁹ 特别是，不要相信文档。代码可能并没有按照注释所建议的那样运行。

• 停止调试，开始编写文档。 这将帮助你从不同的角度看待问题。

• 走开，明天再试。 这可能意味着修复这个错误的时间比坚持下去要晚，但你可能会花更少的时间去寻找它。也就是说，可以用延迟来换取效率。（学生们，这也是你们早点开始编程问题集工作的一个绝佳理由！）

8.2.4 当你找到“那个”错误时

当你认为在代码中发现了一个错误时，开始编码和测试修复的诱惑几乎不可抵挡。然而，通常更好的是暂停。记住，目标不是修复一个错误，而是快速有效地朝着无错误的程序迈进。

问问自己这个错误是否解释了所有观察到的症状，还是仅仅冰山一角。如果是后者，可能最好与其他更改一起处理这个错误。假设，例如，你发现这个错误是因为意外改变了一个列表。你可以局部规避这个问题，可能通过复制列表来实现。或者，你可以考虑用元组代替列表（因为元组是不可变的），也许可以消除代码中其他类似的错误。

在做任何更改之前，尝试理解提议的“修复”的影响。它会破坏其他内容吗？是否引入了过度复杂性？是否提供了整理代码其他部分的机会？

始终确保你可以回到当前位置。没有什么比意识到一系列更改让你离目标更远却没有办法回到起点更让人沮丧。磁盘空间通常是充足的。利用它来存储程序的旧版本。

最后，如果有许多未解释的错误，你可能需要考虑一下，逐个查找和修复错误是否是正确的方法。也许你更应该考虑更好的程序组织方式，或者可能是一个更简单的算法，这样更容易正确实现。

8.3 本章介绍的术语

• 测试

• 调试

• 测试套件

• 输入分区

• 玻璃盒测试

• 黑盒测试

• 路径完全测试

• 单元测试

• 集成测试

• 功能测试

• 软件质量保证（SQA）

• 测试驱动程序

• 测试存根

• 回归测试

• 错误

• 显性错误

• 隐蔽错误

• 持久性错误

• 间歇性错误

• 防御性编程

• 调试工具

• 确认偏误

• 二分搜索

第九章：异常和断言

“异常”通常定义为“不符合规范的事物”，因此有些稀有。在 Python 中，异常并不稀有。它们无处不在。标准 Python 库中的几乎每个模块都在使用它们，而 Python 本身在许多情况下也会引发它们。你已经见过一些异常。

打开一个 Python 终端并输入

test = [1,2,3]
test[3]

解释器会响应类似于以下内容的内容。

IndexError: list index out of range 

IndexError是 Python 在程序尝试访问超出可索引类型范围的元素时引发的异常类型。紧随IndexError的字符串提供了有关导致异常发生的额外信息。

Python 的大多数内置异常处理那些程序试图执行没有适当语义的语句的情况。（我们将在本章后面处理那些不涉及错误的特殊异常。）

那些尝试编写和运行 Python 程序的读者（我们希望你们都是）已经遇到过许多这样的异常。最常见的异常类型包括TypeError、IndexError、NameError和ValueError。

9.1 处理异常

到目前为止，我们将异常视为终止事件。当抛出异常时，程序终止（在这种情况下，崩溃可能是更合适的词），然后我们返回代码，试图找出出错的原因。当抛出导致程序终止的异常时，我们说发生了未处理的异常。

异常不一定会导致程序终止。引发的异常可以并且应该由程序处理。有时异常是因为程序中存在错误（例如访问不存在的变量），但许多情况下，异常是程序员可以并且应该预见的。程序可能尝试打开一个不存在的文件。如果一个交互式程序要求用户输入，用户可能会输入不适当的内容。

Python 提供了一个方便的机制，try-except，用于捕获和处理异常。一般形式是

try
   *code block*
except (*list of exception names*):
   *code block*
else:
   *code block*

如果你知道某行代码在执行时可能会引发异常，你应该处理该异常。在一段写得好的程序中，未处理的异常应该是个例外。

考虑一下这段代码。

success_failure_ratio = num_successes/num_failures
print('The success/failure ratio is', success_failure_ratio)

大多数情况下，这段代码将正常工作，但如果num_failures恰好为零，则会失败。尝试除以零将导致 Python 运行时系统引发ZeroDivisionError异常，而print语句将永远无法被执行。

最好写成如下内容

try:
    success_failure_ratio = num_successes/num_failures
    print('The success/failure ratio is', success_failure_ratio)
except ZeroDivisionError:
    print('No failures, so the success/failure ratio is undefined.')

进入try块后，解释器尝试评估表达式num_successes/num_failures。如果表达式评估成功，程序将表达式的值赋给变量success_failure_ratio，执行try块末尾的print语句，然后继续执行try-except块后面的代码。然而，如果在表达式评估过程中抛出ZeroDivisionError异常，控制将立即跳转到except块（跳过try块中的赋值和print语句），执行except块中的print语句，然后继续执行try-except块之后的代码。

手指练习： 实现一个满足以下规范的函数。使用try-except块。提示：在开始编码之前，你可能想在 shell 中输入类似1 + 'a'的内容，以查看抛出什么类型的异常。

def sum_digits(s):
    """Assumes s is a string
       Returns the sum of the decimal digits in s
          For example, if s is 'a2b3c' it returns 5"""

如果程序代码块可能引发多种异常，保留字except后面可以跟一个异常元组，例如，

except (ValueError, TypeError):

在这种情况下，如果在try块内抛出列出的任何异常，将进入except块。

另外，我们可以为每种异常编写一个单独的except块，这样程序可以根据抛出的异常选择相应的操作。如果程序员编写

except:

如果在try块内抛出任何类型的异常，将会进入except块。请参阅图 9-1 中的函数定义。

图 9-1 使用异常进行控制流

与try块相关联的有两个except块。如果在try块中抛出异常，Python 首先检查它是否为ZeroDivisionError。如果是，它将类型为float的特殊值nan附加到ratios中。（值nan表示“不是一个数字”。它没有字面意义，但可以通过将字符串'nan'或字符串'NaN'转换为类型float来表示。当nan作为类型为float的表达式的操作数时，该表达式的值也是nan。）如果异常是其他类型而不是ZeroDivisionError，则代码执行第二个except块，抛出带有关联字符串的ValueError异常。

原则上，第二个except块不应该被进入，因为调用get_ratios的代码应该遵循get_ratios规范中的假设。然而，由于检查这些假设所带来的计算负担微乎其微，因此进行防御性编程并检查它们可能是值得的。

以下代码演示了程序如何使用get_ratios。在行except ValueError as msg:中，msg绑定到与抛出的ValueError相关联的参数（在这种情况下是一个字符串）。当代码

try:
    print(get_ratios([1, 2, 7, 6], [1, 2, 0, 3]))
    print(get_ratios([], []))
    print(get_ratios([1, 2], [3]))
except ValueError as msg:
    print(msg)

执行后打印

[1.0, 1.0, nan, 2.0]
[]
get_ratios called with bad arguments

为了比较，图 9-2 包含了相同规范的实现，但没有使用try-except。 图 9-2 中的代码比图 9-1 中的代码更长且更难阅读，效率也更低。（图 9-2 中的代码可以通过消除局部变量vect1_elem和vect2_elem来缩短，但这样做将通过重复索引列表而引入更多的低效。）

图 9-2 没有 try-except 的控制流

让我们看另一个例子。考虑以下代码：

val = int(input('Enter an integer: '))
print('The square of the number you entered is', val**2)

如果用户乐意输入一个可以转换为整数的字符串，一切都会很好。但假设用户输入abc呢？执行这行代码将导致 Python 运行时系统抛出ValueError异常，而print语句将永远不会被执行。

程序员应该写的代码大致如下：

while True:
    val = input('Enter an integer: ')
    try:
        val = int(val)
        print('The square of the number you entered is', val**2)
        break #to exit the while loop
    except ValueError:
        print(val, 'is not an integer')

进入循环后，程序会要求用户输入一个整数。一旦用户输入了某个值，程序将执行try—except块。如果try块中的前两个语句都没有引发ValueError异常，将执行break语句并退出while循环。然而，如果执行try块中的代码引发了ValueError异常，控制权将立即转移到except块中的代码。因此，如果用户输入了一个不表示整数的字符串，程序将要求用户重试。无论用户输入什么文本，都不会导致未处理的异常。

这种改变的缺点是程序文本从两行增加到了八行。如果有很多地方要求用户输入整数，这可能会成为一个问题。当然，这个问题可以通过引入一个函数来解决：

def read_int():
    while True:
        val = input('Enter an integer: ')
        try:
            return(int(val)) #convert str to int before returning
        except ValueError:
            print(val, 'is not an integer')

更好的是，这个函数可以推广到请求任何类型的输入：

def read_val(val_type, request_msg, error_msg):
  while True:
      val = input(request_msg + ' ')
      try:
          return(val_type(val)) #convert str to val_type
      except ValueError:
          print(val, error_msg)

函数read_val是多态的，即它适用于多种不同类型的参数。这类函数在 Python 中很容易编写，因为类型是一等对象。我们现在可以使用以下代码请求一个整数：

`val = read_val(int, 'Enter an integer:', 'is not an integer')`

异常可能看起来不友好（毕竟，如果不处理，异常会导致程序崩溃），但考虑一下替代方案。当要求将字符串'abc'转换为int类型的对象时，类型转换int应该怎么做？它可以返回与编码字符串所用位对应的整数，但这与程序员的意图不太可能相关。或者，它可以返回特殊值None。如果这样做，程序员就需要插入代码来检查类型转换是否返回了None。如果程序员忘记了这个检查，程序执行时就有可能出现一些奇怪的错误。

使用异常时，程序员仍需包含处理异常的代码。然而，如果程序员忘记包含这样的代码且异常被引发，程序将立即停止。这是件好事。它提醒程序用户发生了一些麻烦的事情。（正如我们在第八章讨论的，显性错误远比隐性错误好。）此外，它为调试程序的人提供了明确的指示，说明哪里出了问题。

9.2 异常作为控制流机制

不要认为异常仅仅是错误的表现。它们是一个便捷的控制流机制，可以用来简化程序。

在许多编程语言中，处理错误的标准方法是让函数返回一个值（通常类似于 Python 的None），以指示出现了问题。每次函数调用都必须检查是否返回了该值。在 Python 中，通常在函数无法生成与其规格一致的结果时引发异常。

Python 中的**raise** 语句强制引发指定的异常。raise 语句的形式是：

`raise` *exceptionName*`(`*arguments*`)`

exceptionName 通常是内置异常之一，例如ValueError。但是，程序员可以通过创建内置类Exception的子类（见第十章）来定义新的异常。不同类型的异常可以有不同类型的参数，但大多数情况下，参数是一个字符串，用于描述引发异常的原因。

手指练习： 实现一个满足规格的函数。

def find_an_even(L):
    """Assumes L is a list of integers
       Returns the first even number in L
       Raises ValueError if L does not contain an even number"""

让我们看一个例子，图 9-3。函数get_grades要么返回一个值，要么引发一个与之关联的值的异常。如果调用open引发IOError，它将引发ValueError异常。它本可以忽略IOError，让调用get_grades的程序部分处理，但那会给调用代码提供更少的信息，关于出错的原因。调用get_grades的代码要么使用返回的值计算另一个值，要么处理异常并打印有用的错误信息。

图 9-3 获取成绩

9.3 断言

Python 的assert语句为程序员提供了一种简单的方法，以确认计算状态是否如预期。assert 语句可以有两种形式：

`assert` *Boolean expression*

py`or assert 布尔表达式, 参数 ```py When an assert statement is encountered, the Boolean expression is evaluated. If it evaluates to True, execution proceeds on its merry way. If it evaluates to False, an AssertionError exception is raised. Assertions are a useful defensive programming tool. They can be used to confirm that the arguments to a function are of appropriate types. They are also a useful debugging tool. They can be used, for example, to confirm that intermediate values have the expected values or that a function returns an acceptable value.```` ## 9.4 在第章中引入的术语 * 异常 * 引发异常 * 未处理异常 * 已处理异常 * try-except 构造 * 捕获（异常） * 多态函数 * 一流对象 * raise 语句 * 断言

第十章：类与面向对象编程

现在我们将注意力转向与在 Python 中编程相关的最后一个主要主题：使用类来围绕数据抽象组织程序。

类可以以多种不同的方式使用。在本书中，我们强调在面向对象编程的背景下使用它们。面向对象编程的关键在于将对象视为数据和操作这些数据的方法的集合。

面向对象编程的理念已有大约 50 年的历史，在过去的 30 年左右得到了广泛接受和实践。在 1970 年代中期，人们开始撰写文章解释这种编程方法的好处。大约在同一时间，编程语言 SmallTalk（在 Xerox PARC）和 CLU（在 MIT）为这些理念提供了语言支持。但直到 C++ 和 Java 的出现，面向对象编程才真正开始在实践中蓬勃发展。

在本书的大部分内容中，我们一直隐含地依赖于面向对象编程。在第 2.2.1 节中，我们说过：“对象是 Python 程序操作的核心。每个对象都有一个类型，定义了程序可以对该对象做的事情。”自第二章以来，我们依赖于内置类型，如 float 和 str 及其相关的方法。但正如编程语言的设计者只能内置一小部分有用的函数，他们也只能内置一小部分有用的类型。我们已经看过一种允许程序员定义新函数的机制；现在我们将看一种允许程序员定义新类型的机制。

10.1 抽象数据类型与类

抽象数据类型的概念相当简单。抽象数据类型是一组对象及其上的操作。这些被绑定在一起，以便程序员可以将一个对象从程序的一个部分传递到另一个部分，并在此过程中提供对对象的数据属性的访问，以及方便操作这些数据的操作。

这些操作的规范定义了抽象数据类型与程序其他部分之间的接口。接口定义了操作的行为——它们做什么，但不说明它们如何做到这一点。接口因此提供了一个抽象屏障，将程序的其余部分与提供类型抽象实现所涉及的数据结构、算法和代码隔离开来。

编程是以一种促进变化的方式来管理复杂性。有两种强大的机制可以实现这一点：分解和抽象。分解在程序中创建结构，而抽象则抑制细节。关键在于抑制适当的细节。这就是数据抽象能够发挥作用的地方。我们可以创建提供便利抽象的特定领域类型。理想情况下，这些类型捕捉在程序生命周期内相关的概念。如果我们在编程过程中设计出数月甚至数十年后仍然相关的类型，那么在维护该软件方面我们就有了很大的优势。

在本书中，我们一直在使用抽象数据类型（尽管没有这样称呼它们）。我们已经编写了使用整数、列表、浮点数、字符串和字典的程序，而没有考虑这些类型可能是如何实现的。用莫里哀的《布尔乔亚绅士》的话来说，“我发誓，有超过一百页我们使用了 ADT，而我们并不知道。”⁶⁰

在 Python 中，我们使用类实现数据抽象。每个类定义以保留字class开头，后面跟着类名和关于它如何与其他类相关的信息。

考虑以下微小（完全无用的）类定义。

class Toy(object):
    def __init__(self):
        self._elems = []
    def add(self, new_elems):
        """new_elems is a list"""
        self._elems += new_elems
    def size(self):
        return len(self._elems)

第一行表示Toy是object的子类。目前，忽略作为子类意味着什么。我们很快就会涉及到这一点。

类定义创建一个type类型的对象，并将一组称为属性的对象与该类对象关联。在这个例子中，与类相关的三个属性是__init__、add和size。每个属性都是function类型。因此，代码

print(type(Toy))
print(type(Toy.__init__), type(Toy.add), type(Toy.size))

打印

<class ‘type'>
<class 'function'> <class 'function'> <class 'function'>

正如我们将看到的，Python 有许多特殊的函数名称以两个下划线开始和结束。这些通常被称为魔法方法。⁶¹我们将要看的第一个是__init__。每当类被实例化时，都会调用在该类中定义的__init__函数。当执行以下代码行时

`s = Toy()`

被执行时，解释器将创建一个新的Toy类型的实例，然后调用Toy.__init__，将新创建的对象作为实际参数绑定到形式参数self。当调用Toy.__init__时，会创建列表对象_elems，它成为新创建的Toy类型实例的一部分。（该列表使用现在已熟悉的[]符号创建，实际上是list()的缩写。）列表_elems被称为Toy实例的数据属性。代码

`t1 = Toy() print(type(t1)) print(type(t1.add)) t2 = Toy() print(t1 is t2) #test for object identity`

打印

<class '__main__.Toy'>
<class 'method'>
False

请注意，t1.add是method类型，而Toy.add是function类型。由于t1.add是一个方法，我们可以使用点表示法调用它（和t1.size）。

类不应与该类的实例混淆，就像list类型的对象不应与list类型混淆一样。属性可以与类本身或类的实例关联：

• 类属性是在类定义中定义的；例如，Toy.size是类Toy的一个属性。当类被实例化时，比如通过语句t = Toy()，实例属性，比如t.size，会被创建。

• 虽然t.size最初绑定到类Toy中定义的size函数，但在计算过程中，这种绑定是可以改变的。例如，你可以（但绝对不应该！）通过执行t.size = 3来改变绑定。

• 当数据属性与类关联时，我们称它们为类变量。当它们与实例关联时，我们称它们为实例变量。例如，_elems是一个实例变量，因为对于每个Toy类的实例，_elems绑定到一个不同的列表。到目前为止，我们还没有看到类变量。我们将在图 10-4 中使用一个。

现在，考虑一下这段代码。

t1 = Toy()
t2 = Toy()
t1.add([3, 4])
t2.add([4])
print(t1.size() + t2.size())

因为每个Toy实例都是不同的对象，所以每个Toy类型的实例都会有不同的_elems属性。因此，代码输出3.。

初看起来，这段代码似乎存在不一致的地方。看起来每个方法调用时参数少了一。比如，add有两个正式参数，但我们似乎只用一个实际参数在调用它。这是使用点表示法调用与类实例相关联的方法的结果。与点前的表达式相关联的对象会隐式地作为第一个参数传递给方法。在本书中，我们遵循使用self作为这个实际参数绑定的正式参数名称的惯例。Python 程序员几乎普遍遵循这一惯例，我们强烈建议你也这样做。

另一个常见的惯例是以一个下划线开始数据属性的名称。正如我们在 10.3 节中详细讨论的那样，我们使用前导的_来表示该属性是类的私有属性，即不应在类外部直接访问。

现在，让我们来看一个更有趣的例子。图 10-1 包含一个类定义，它提供了一个名为Int_set的整数集合抽象的简单实现。（考虑到 Python 有内置的set类型，这个实现既不必要又不必要地复杂。不过，它在教学上是有用的。）

图 10-1 类Int_set

请注意，类定义顶部的文档字符串（用"""括起来的注释）描述的是类提供的抽象，而不是类的实现信息。相比之下，文档字符串下方的注释包含实现信息。这些信息面向可能想修改实现或构建该类子类的程序员，而不是希望使用该抽象的程序员。

如我们所见，与类实例相关的方法可以使用点符号调用。例如，代码，

s = Int_set()
s.insert(3)
print(s.member(3))

创建一个新的Int_set实例，将整数 3 插入该Int_set，然后打印True。

数据抽象实现了表示独立性。将抽象类型的实现视为具有多个组件：

• 该类型方法的实现

• 一起编码该类型值的数据结构

• 关于方法实现如何使用数据结构的约定；一个关键约定由表示不变性捕捉

表示不变性定义了数据属性的哪些值对应于类实例的有效表示。Int_set的表示不变性是vals不包含重复值。__init__的实现负责建立该不变性（空列表时成立），其他方法负责维护该不变性。这就是为什么insert仅在self.vals中不存在e时才会添加它。

remove的实现利用了在进入remove时满足表示不变性的假设。它仅调用一次list.remove，因为表示不变性保证self.vals中最多只有一个e的出现。

类中定义的最后一个方法__str__是另一种特殊的__方法。当程序通过调用str将该类的实例转换为字符串时，将调用类的__str__方法。因此，当使用print命令时，打印对象的__str__函数将被调用。例如，代码

s = Int_set()
s.insert(3)
s.insert(4)
print(str(s))
print('The value of s is', s)

将打印

{3,4}
The value of s is {3,4}

（如果没有定义__str__方法，执行print(s)将打印类似于<__main__.Int_set object at 0x1663510>的内容。）

手指练习： 向Int_set类添加一个满足以下规范的方法。

    def union(self, other):
        """other is an Int_set
           mutates self so that it contains exactly the elemnts in self
           plus the elements in other."""

10.1.1 魔法方法与可哈希类型

Python 设计目标之一是允许程序员使用类定义新的类型，使其使用与 Python 内置类型一样简单。使用魔法方法为内置函数如str和len提供类特定的定义在实现这一目标中发挥了重要作用。

魔法方法还可以用于为中缀运算符如==和+提供类特定的定义。可用于中缀运算符的方法名称是

你可以将任何实现与这些操作符关联。如果你愿意，可以将+实现为减法，将<实现为指数运算，等等。然而，我们建议你抵制这种想象力的机会，保持与这些操作符的传统含义一致的实现。

回到我们的玩具示例，考虑图 10-2 中的代码。

图 10-2 使用魔法方法

当运行图 10-2 中的代码时，它会打印

The value of t3 is [1, 2, 3, 4]
The length of t3 is 4
The value A is associated with the key t1 in d.

我们可以将Toy的实例用作字典的键，因为我们为该类定义了__hash__函数。如果我们定义了__eq__函数但没有定义__hash__函数，当我们尝试使用t1和t2作为键创建字典时，代码将生成错误消息unhashable type: ‘Toy'。提供用户定义的__hash__时，应该确保对象的哈希值在该对象的生命周期内保持不变。

所有未显式定义__eq__的用户定义类的实例在==中使用对象标识，并且是可哈希的。如果没有提供__hash__方法，则对象的哈希值来自对象的标识（见第 5.3 节）。

手指练习：用一种允许Int_set的客户端使用+操作符表示集合并集的方法替换你添加到Int_set中的union方法。

10.1.2 使用抽象数据类型设计程序

抽象数据类型非常重要。它们导致了对组织大型程序的新思维方式。当我们思考世界时，我们依赖于抽象。在金融界，人们谈论股票和债券。在生物界，人们谈论蛋白质和残基。当试图理解这些概念时，我们会在脑海中将相关数据和特征汇集成一个知识包。例如，我们认为债券具有利率、到期日和价格等数据属性。我们还认为债券具有“设定价格”和“计算到期收益率”等操作。抽象数据类型使我们能够将这种组织方式融入程序设计中。

数据抽象鼓励程序设计者关注数据对象的核心，而不是函数。将程序更多地视为类型的集合而不是函数的集合，会导致根本不同的组织原则。除此之外，它鼓励我们将编程视为组合相对较大块的过程，因为数据抽象通常涵盖比单个函数更多的功能。这反过来使我们认为编程的本质是一个不是写个别代码行，而是组合抽象的过程。

可重用抽象的可用性不仅减少了开发时间，而且通常导致更可靠的程序，因为成熟的软件通常比新软件更可靠。多年来，常用的程序库只有统计或科学库。然而，今天可用的程序库范围广泛（尤其是针对 Python），通常基于丰富的数据抽象集，正如我们在本书后面将看到的那样。

10.1.3 使用类跟踪学生和教职工

作为类的示例使用，想象你正在设计一个程序，以帮助跟踪大学的所有学生和教职工。确实可以在不使用数据抽象的情况下编写这样的程序。每个学生将有一个姓氏、名字、家庭地址、年级、一些成绩等。这些数据可以通过列表和字典的组合来存储。跟踪教职工需要一些类似的数据结构和一些不同的数据结构，例如，用于跟踪薪资历史的数据结构。

在急于设计一堆数据结构之前，让我们考虑一些可能有用的抽象。是否存在一个覆盖学生、教授和工作人员共同属性的抽象？有人会争辩说，他们都是人。图 10-3 包含一个类，它结合了人类的两个共同属性（姓名和生日）。它使用了标准的 Python 库模块datetime，该模块提供了许多方便的方法来创建和处理日期。

图 10-3 类Person

以下代码使用了Person和datetime。

me = Person('Michael Guttag')
him = Person('Barack Hussein Obama')
her = Person('Madonna')
print(him.get_last_name())
him.set_birthday(datetime.date(1961, 8, 4))
her.set_birthday(datetime.date(1958, 8, 16))
print(him.get_name(), 'is', him.get_age(), ‘days old')

请注意，每当实例化Person时，都需要向__init__函数提供一个参数。一般来说，实例化一个类时，我们需要查看该类的__init__函数的规范，以了解需要提供哪些参数以及这些参数应该具备什么属性。

执行上述代码会创建三个类Person的实例。我们可以使用与这些实例相关联的方法访问有关它们的信息。例如，him.get_last_name()返回'Obama'。表达式him._last_name也会返回'Obama'；然而，由于本章后面讨论的原因，直接访问实例变量的表达式被认为是不良的写法，应当避免。同样，尽管实现中包含一个具有该值的属性，但对于Person抽象的用户来说，没有合适的方法提取一个人的生日。（当然，可以很容易地为该类添加一个get_birthday方法。）不过，有一种方法可以提取依赖于个人生日的信息，如上述代码中的最后一个print语句所示。

类Person为另一个特殊命名方法__lt__提供了特定于Person的定义。该方法重载了<运算符。每当<运算符的第一个参数为Person类型时，方法Person__lt__会被调用。类Person中的__lt__方法是使用类型str的二元<运算符实现的。表达式self._name < other._name是self._name.__lt__(other._name)的简写。由于self._name是str类型，因此这个__lt__方法与类型str相关联。

除了提供使用<的中缀表达式书写的语法便利外，这种重载还自动访问任何使用__lt__定义的多态方法。内置方法sort就是这样一个方法。因此，例如，如果p_list是由Person类型元素组成的列表，则调用p_list.sort()将使用类Person中定义的__lt__方法对该列表进行排序。因此，代码

pList = [me, him, her]
for p in pList:
    print(p)
pList.sort()
for p in pList:
    print(p)

将打印

Michael Guttag
Barack Hussein Obama
Madonna
Michael Guttag
Madonna
Barack Hussein Obama

10.2 继承

许多类型与其他类型有共同的属性。例如，类型list和str各自都有len函数，其意义相同。继承提供了一种方便的机制，用于构建相关抽象的分组。它允许程序员创建一个类型层次结构，在这个结构中，每个类型从其上层类型继承属性。

类object位于层次结构的顶部。这是合理的，因为在 Python 中，运行时存在的所有内容都是对象。由于Person继承了对象的所有属性，程序可以将变量绑定到Person，将Person添加到列表等。

图 10-4 中的类MIT_person继承自其父类Person的属性，包括Person从其父类object继承的所有属性。在面向对象编程的术语中，MIT_person是Person的子类，因此继承了其超类的属性。除了继承的属性外，子类还可以：

• 添加新属性。例如，子类MIT_person添加了类变量 _next_id_num、实例变量 _id_num以及方法get_id_num。

• 覆盖，即替换超类的属性。例如，MIT_person覆盖了__init__和__lt__。当一个方法被覆盖时，执行的方法版本取决于用于调用该方法的对象。如果对象的类型是子类，则使用在子类中定义的版本。如果对象的类型是超类，则使用超类中的版本。

方法MIT_person.__init__首先使用super().__init__(name)调用其超类（Person）的__init__函数。这初始化了继承的实例变量self._name。然后它初始化self._id_num，这是MIT_person的实例拥有但Person的实例没有的实例变量。

实例变量self._id_num使用一个属于类MIT_person的类 变量_next_id_num进行初始化，而不是类的实例。当创建MIT_person的实例时，并不会创建一个新的next_id_num实例。这允许__init__确保每个MIT_person的实例都有一个唯一的 _id_num。

图 10-4 类MIT_person

考虑这段代码

p1 = MIT_person('Barbara Beaver')
print(str(p1) + '\'s id number is ' + str(p1.get_id_num()))

第一行创建了一个新的MIT_person。第二行则更复杂。当它尝试评估表达式str(p1)时，运行时系统首先检查类MIT_person是否有与之关联的__str__方法。由于没有，它接着检查MIT_person的直接超类Person是否有__str__方法。确实存在，因此使用该方法。当运行时系统尝试评估表达式p1.get_id_num()时，它首先检查类MIT_person是否有与之关联的get_id_num方法。确实存在，因此它调用该方法并打印

Barbara Beaver's id number is 0

（回想一下，在字符串中，字符“\”是一个转义字符，用于指示下一个字符应以特殊方式处理。在字符串中

`'\'s id number is '`

“\”表示撇号是字符串的一部分，而不是终止字符串的分隔符。）

现在考虑这段代码

p1 = MIT_person('Mark Guttag')
p2 = MIT_person('Billy Bob Beaver')
p3 = MIT_person('Billy Bob Beaver')
p4 = Person('Billy Bob Beaver')

我们创建了四个虚拟人物，其中三个名为比利·鲍勃·河狸。两个比利·鲍勃是类型为MIT_person，而一个仅是Person。如果我们执行以下代码行

print('p1 < p2 =', p1 < p2)
print('p3 < p2 =', p3 < p2)
print('p4 < p1 =', p4 < p1)

解释器将打印

p1 < p2 = True
p3 < p2 = False
p4 < p1 = True

由于p1、p2和p3都是MIT_person类型，解释器在评估前两个比较时将使用在MIT_person类中定义的__lt__方法，因此排序将基于识别号。在第三个比较中，<运算符应用于不同类型的操作数。由于表达式的第一个参数用于确定调用哪个__lt__方法，因此p4 < p1是p4.__lt__(p1)的简写。因此，解释器使用与p4类型相关的__lt__方法Person，并按名称对“人”进行排序。

如果我们尝试

print('p1 < p4 =', p1 < p4)

运行时系统将调用与p1类型相关联的__lt__运算符，即在MIT_person类中定义的那个。这将导致异常。

AttributeError: 'Person' object has no attribute '_id_num'

因为p4绑定的对象没有属性 _id_num。

练习：实现一个符合规范的Person子类。

class Politician(Person):
    """ A politician is a person who can belong to a political party"""  
    def __init__(self, name, party = None):
        """name and party are strings"""
    def get_party(self):
        """returns the party to which self belongs"""
    def might_agree(self, other):
        """returns True if self and other belong to the same part
             or at least one of then does not belong to a party"""

10.2.1 多层继承

图 10-5 为类层次结构增加了另几层继承。

图 10-5 两种类型的学生

添加UG似乎是合乎逻辑的，因为我们希望将每位本科生与一个毕业年份（或预期毕业年份）关联起来。但Student和Grad类有什么情况呢？通过使用 Python 保留字**pass**作为主体，我们表明该类除了从其超类继承的属性外没有其他属性。为什么会有人想创建一个没有新属性的类呢？

通过引入类Grad，我们获得了创建两种类型学生的能力，并使用它们的类型来区分一种对象与另一种对象。例如，代码

p5 = Grad('Buzz Aldrin')
p6 = UG('Billy Beaver', 1984)
print(p5, 'is a graduate student is', type(p5) == Grad)
print(p5, 'is an undergraduate student is', type(p5) == UG)

将打印

Buzz Aldrin is a graduate student is True
Buzz Aldrin is an undergraduate student is False

中间类型Student的实用性更为微妙。考虑回到class MIT_person并添加该方法。

def is_student(self):
    return isinstance(self, Student)

函数isinstance是 Python 内置的。isinstance的第一个参数可以是任何对象，但第二个参数必须是type类型的对象或一个type类型对象的元组。只有当第一个参数是第二个参数的实例时（或者，如果第二个参数是元组，则是元组中某种类型的实例），函数才会返回True。例如，isinstance([1,2], list)的值为True。

回到我们的示例，代码

print(p5, 'is a student is', p5.is_student())
print(p6, 'is a student is', p6.is_student())
print(p3, 'is a student is', p3.is_student())

打印

Buzz Aldrin is a student is True
Billy Beaver is a student is True
Billy Bob Beaver is a student is False

请注意，isinstance(p6, Student)的含义与type(p6) == Student的含义截然不同。p6绑定的对象的类型是UG，而不是Student，但由于UG是Student的子类，p6绑定的对象是Student类的一个实例（同时也是MIT_person和Person的实例）。

由于只有两种类型的学生，我们可以将is_student实现为，

def is_student(self):
    return type(self) == Grad or type(self) == UG

然而，如果后续添加了一种新类型的学生，就有必要回过头来编辑实现is_student的代码。通过引入中间类Student并使用isinstance，我们避免了这个问题。例如，如果我们添加了

class Transfer_student(Student):
    def __init__(self, name, from_school):
        MIT_person.__init__(self, name)
        self._from_school = from_school
    def get_old_school(self):
        return self._from_school

不需要对is_student进行更改。

在程序的创建和后期维护过程中，回过头来添加新类或旧类的新属性并不少见。好的程序员设计他们的程序，以尽量减少在进行此操作时可能需要更改的代码量。

手指练习：以下表达式的值是多少？

isinstance('ab', str) == isinstance(str, str)

10.2.2 替换原则

当使用子类化来定义类型层次结构时，子类应该被视为扩展其超类的行为。我们通过添加新属性或重写从超类继承的属性来实现。例如，TransferStudent通过引入前学校来扩展Student。

有时，子类会重写超类的方法，但这必须谨慎进行。特别是，超类的重要行为必须被每个子类支持。如果客户端代码在使用超类实例时正常工作，那么在替换为子类实例时也应正常工作（因此称为替换原则）。例如，应该能够编写使用Student规范的客户端代码，并使其在TransferStudent上正常工作。⁶²

反之，没有理由期望为TransferStudent编写的代码能够适用于任意类型的Student。

10.3 封装与信息隐藏

只要我们在处理学生，没必要让他们经历上课和获得成绩的痛苦那就太可惜了。

图 10-6 包含一个可以用来跟踪一组学生成绩的类。类Grades的实例是使用列表和字典实现的。列表跟踪班级中的学生，而字典将学生的身份证明号码映射到成绩列表。

图 10-6 类Grades

请注意，get_grades返回与学生关联的成绩列表的副本，而get_students返回学生列表的副本。通过简单返回实例变量本身，可以避免复制列表的计算成本。然而，这样做可能会导致问题。考虑代码

course = Grades()
course.add_student(Grad('Bernie'))
all_students = course.get_students()
all_students.append(Grad('Liz'))

如果get_students返回self._students，那么代码的最后一行将会有（可能是意外的）副作用，改变course中的学生集合。

实例变量_is_sorted用于跟踪自上次添加学生以来学生列表是否已排序。这使得get_students的实现可以避免对已排序列表进行排序。

图 10-7 包含一个使用类Grades为一些修读课程six_hundred的学生生成成绩报告的函数。

图 10-7 生成成绩报告。

运行时，图中的代码打印。

Jane Doe's mean grade is 75.0
Pierce Addison's mean grade is 75.0
David Henry has no grades
Billy Buckner's mean grade is 50.0
Bucky F. Dent's mean grade is 87.5

面向对象编程的核心有两个重要概念。第一个是封装的概念。我们指的是将数据属性和操作这些属性的方法捆绑在一起。例如，如果我们写。

Rafael = MIT_person('Rafael Reif')

我们可以使用点符号访问诸如 Rafael 的名字和身份证号等属性。

第二个重要概念是信息隐藏。这是模块化的关键之一。如果使用类的程序部分（即类的客户端）仅依赖于类中方法的规范，那么实现该类的程序员就可以自由地更改类的实现（例如，提高效率），而不必担心该更改会破坏使用该类的代码。

一些编程语言（例如 Java 和 C++）提供强制信息隐藏的机制。程序员可以将类的属性设为私有，以便类的客户端只能通过对象的方法访问数据。Python 3 使用命名约定使得属性在类外不可见。当属性的名称以__（双下划线）开头但不以__结尾时，该属性在类外不可见。请参考图 10-8 中的类。

图 10-8 类中的信息隐藏。

当我们运行代码时。

test = info_hiding()
print(test.visible)
print(test.__also_visible__)
print(test.__invisible)

它打印。

Look at me
Look at me too 

然后引发异常。

AttributeError: 'info_hiding' object has no attribute '__invisible'

代码。

test = info_hiding()
test.print_invisible()
test.__print_invisible__()
test.__print_invisible()

打印。

Don't look at me directly
Don't look at me directly

然后引发异常。

AttributeError: 'info_hiding' object has no attribute '__print_invisible'

以及代码。

class Sub_class(info_hiding):
    def new_print_invisible(self):
        print(self.__invisible)       
test_sub = Sub_class()
test_sub.new_print_invisible()

打印。

 AttributeError: ‘Sub_class' object has no attribute '_Sub_class__invisible'

请注意，当子类尝试使用其超类的隐藏属性时，会发生AttributeError。这使得使用__进行信息隐藏有些繁琐。

由于这可能很繁琐，许多 Python 程序员并不利用__机制来隐藏属性——我们在本书中也是如此。因此，例如，Person的客户端可以写表达式Rafael._last_name而不是Rafael.get_last_name()。我们通过在属性前放置单个_来劝阻这种不良行为，以表明我们希望客户端不要直接访问它。

我们避免直接访问数据属性，因为依赖于不属于规范的一部分的内容对客户端代码是危险的，因此可能会发生变化。例如，如果Person的实现被更改为在请求时提取姓氏，而不是将其存储在实例变量中，那么直接访问_last_name的客户端代码将不再有效。

Python 不仅允许程序从类定义之外读取实例和类变量，还允许程序写入这些变量。因此，例如，代码Rafael._birthday = '8/21/50'是完全合法的。如果稍后在计算中调用Rafael.get_age，将会导致运行时类型错误。甚至可以在类定义之外创建实例变量。例如，如果赋值语句

`me.age = Rafael.get_id_num()`

在类定义之外发生。

尽管这种相对弱的静态语义检查是 Python 的一项缺陷，但这并不是致命的缺陷。一个有纪律的程序员可以简单地遵循一个合理的规则，即不直接从定义它们的类之外访问数据属性，就像我们在本书中所做的那样。

10.3.1 生成器

信息隐藏的一个被感知的风险是，阻止客户端程序直接访问关键数据结构会导致不可接受的效率损失。在数据抽象的早期，许多人担心引入多余的函数或方法调用的成本。现代编译技术使这个担忧变得无关紧要。一个更严重的问题是，客户端程序将被迫使用低效的算法。

考虑在图 10-7 中实现的grade_report。调用course.get_students会创建并返回一个大小为n的列表，其中n是学生的数量。这对单个班级的成绩册来说可能不是问题，但想象一下，要跟踪 170 万名参加 SAT 考试的高中生的成绩。当列表已经存在时，创建这样大小的新列表是一种显著的低效。一种解决方案是放弃抽象，允许grade_report直接访问实例变量course.students，但这将违反信息隐藏。幸运的是，还有更好的解决方案。

图 10-9 中的代码用一种我们尚未见过的语句替换了Grades类中的get_students函数：yield语句。

任何包含yield语句的函数定义都会以特殊的方式处理。yield的存在告诉 Python 系统该函数是一个生成器。生成器通常与for语句一起使用，如

`for s in course.get_students():`

在图 10-7 中。

图 10-9 get_students的新版本

在使用生成器的for循环的第一次迭代开始时，生成器被调用并运行，直到第一次执行yield语句，此时返回yield语句中表达式的值。在下一次迭代中，生成器立即在yield后恢复执行，所有局部变量绑定到yield语句执行时绑定的对象，再次运行直到执行yield语句。它会继续这样做，直到没有代码可执行或执行return语句，此时循环退出。⁶³

图 10-9 中的get_students版本允许程序员使用for循环以与内置类型如list相同的方式迭代Grades类型对象中的学生。例如，代码

book = Grades()
book.add_student(Grad('Julie'))
book.add_student(Grad('Lisa'))
for s in book.get_students():
    print(s)

打印

Julie
Lisa

因此，图 10-7 中的循环以

`for s in course.get_students():`

不需要修改以利用包含新实现的get_students的Grades类版本。（当然，依赖于get_students返回列表的大多数代码将不再有效。）相同的for循环可以迭代get_students提供的值，无论get_students是返回一个值的列表还是一次生成一个值。一次生成一个值将更有效，因为不会创建包含学生的新列表。

指尖练习： 向Grades添加一个满足规范的生成器

def get_students_above(self, grade):
    """Return the students a mean grade > g one at a time"""

10.4 扩展示例

2008 年秋季，美国房地产价格崩溃帮助引发了一场国际经济危机。其中一个原因是，太多房主承担了最终带来意想不到后果的抵押贷款。⁶⁴

一开始，抵押贷款相对简单。买家从银行借款，并在抵押贷款的整个生命周期内每月支付固定金额，通常为 15 到 30 年。在这段时间结束时，银行收回了初始贷款（本金）加上利息，房主就“完全拥有”了房子。

到二十世纪末，抵押贷款变得更加复杂。人们可以通过在接受抵押贷款时向贷款人支付“点数”来获得更低的利率。一个点是贷款价值的1%的现金支付。人们可以选择在一段时间内仅支付“利息”的抵押贷款。也就是说，在贷款开始的几个月内，借款人仅支付累计的利息，而不支付本金。其他贷款涉及多种利率。通常，最初的利率（称为“诱饵利率”）较低，随后随着时间的推移而上升。这些贷款通常是浮动利率的——在初始期限后要支付的利率将根据某种旨在反映贷款人在批发信贷市场借款成本的指数而变化。

原则上，为消费者提供多种选择是一件好事。然而，不负责任的贷款提供者并不总是小心地充分解释各种选择的潜在长期影响，某些借款人做出了证明后果严重的选择。

让我们构建一个程序，检查三种抵押贷款的成本：

• 一种没有点数的固定利率抵押贷款

• 固定利率抵押贷款和点数

• 一种初始诱饵利率，随后在持续期间为更高利率的抵押贷款

本次练习的目的是提供一些有关一组相关类增量开发的经验，而不是让你成为抵押贷款专家。

我们将结构化我们的代码，以包含一个Mortgage类及其对应于上述三种抵押贷款类型的子类。图 10-10 包含抽象类Mortgage。该类包含每个子类共享的方法，但不打算直接实例化。也就是说，不会创建类型为Mortgage的对象。

图形顶部的find_payment函数计算需要在贷款到期时偿还贷款所需的固定月供，包括利息。它使用一个众所周知的封闭形式表达式来实现这一点。这个表达式并不难推导，但查找它要容易得多，也更可能是正确的，而不是现场推导出来的。

然而，请记住，并非你在网络上（甚至教科书中）发现的所有信息都是正确的。当你的代码包含你查找的公式时，请确保：

• 你已从可信来源获取公式。我们查看了多个可信来源，它们都包含等效的公式。

• 你完全理解公式中所有变量的含义。

• 你将你的实现与来自可信来源的示例进行测试。在实现此功能后，我们通过将我们的结果与网络上可用计算器提供的结果进行比较来进行测试。

图 10-10 Mortgage基类

观察 __init__，我们看到所有 Mortgage 实例将具有与初始贷款金额、月利率、贷款期限（以月为单位）、每月初已支付的付款列表（该列表以 0 开头，因为在第一个月初尚未支付任何款项）、每月初未偿贷款余额的列表、每月需支付的金额（使用函数 find_payment 返回的值初始化）以及抵押贷款描述（初始值为 None）相对应的实例变量。每个 Mortgage 子类的 __init__ 操作预计会首先调用 Mortgage.__init__，然后将 self._legend 初始化为该子类的适当描述。

方法 make_payment 用于记录抵押贷款支付。每次支付的一部分覆盖了未偿贷款余额的利息，剩余部分用于减少贷款余额。这就是 make_payment 更新 self.paid 和 self.outstanding 的原因。

方法 get_total_paid 使用内置的 Python 函数 sum，该函数返回一系列数字的总和。如果序列中包含非数字，则会引发异常。

图 10-11 包含实现三种类型抵押贷款的类。类 Fixed 和 Fixed_with_pts 重写 __init__ 并从 Mortgage 继承其他三种方法。类 Two_rate 将抵押贷款视为两个不同利率贷款的串联。（由于 self.paid 初始化为包含一个元素的列表，因此它包含的元素比已支付的款项多一个。这就是方法 make_payment 将 len(self.paid) 与 self.teaser_months + 1 进行比较的原因。）

图 10-11 还包含一个计算并打印每种抵押贷款总成本的函数，基于一组示例参数。它首先创建每种类型的一份抵押贷款。然后，对每一份抵押贷款在给定的年份内进行每月支付。最后，打印每笔贷款的支付总额。

我们现在终于准备好比较不同的抵押贷款了：

compare_mortgages(amt=200000, years=30, fixed_rate=0.035,
                  pts = 2, pts_rate=0.03, var_rate1=0.03,
                  var_rate2=0.05, var_months=60)

注意，在调用 compare_mortgages 时，我们使用了关键字参数而非位置参数。这样做是因为 compare_mortgages 有大量相同类型的形式参数，使用关键字参数可以更容易地确保我们为每个形式参数提供了预期的实际值。

当代码运行时，它会打印

Fixed, 3.5%
 Total payments = $323,312
Fixed, 3.0%, 2 points
 Total payments = $307,555
3.0% for 60 months, then 5.0%
 Total payments = $362,435

图 10-11 抵押贷款子类

初看结果似乎相当明确。可变利率贷款对借款人（而非贷款人）来说是个坏主意，而带点的固定利率贷款则是成本最低的。然而，需要注意的是，总成本并不是评估抵押贷款的唯一标准。例如，预计未来收入会更高的借款人可能愿意在后期支付更多，以减轻初期还款的负担。

这表明，与其看一个单一的数字，不如观察随时间变化的付款情况。这反过来又表明，我们的程序应该生成旨在展示抵押贷款随时间变化的图表。我们将在第 13.2 节中进行讨论。

10.5 章节中引入的术语

• 面向对象编程

• 抽象数据类型

• 接口

• 抽象屏障

• 分解

• 抽象

• 类

• 类定义

• 方法属性

• 类属性

• 类实例

• 属性引用

• __ 方法

• 魔法（双下划线）方法

• 数据属性

• 类变量

• 实例变量

• 类定义

• 表示不变式

• 继承

• 子类

• 超类

• 方法重写

• isinstance

• 替代原则

• 封装

• 信息隐藏

• 私有

• 生成器

• 抽象类

第十一章：对算法复杂性的简单介绍

设计和实现程序时最重要的是，它应该产生可依赖的结果。我们希望我们的银行余额能够正确计算。我们希望汽车中的燃油喷射器能够注入适量的燃料。我们更希望飞机和操作系统都不会崩溃。

有时性能是正确性的一个重要方面。这对于需要实时运行的程序最为明显。一个警告飞机潜在障碍物的程序需要在遇到障碍物之前发出警告。性能也会影响许多非实时程序的实用性。在评估数据库系统的实用性时，每分钟完成的事务数量是一个重要指标。用户关心在手机上启动应用程序所需的时间。生物学家关心它们的系统发育推断计算需要多长时间。

编写高效程序并不容易。最简单的解决方案往往不是最有效的。计算上高效的算法通常采用微妙的技巧，这可能使它们难以理解。因此，程序员往往增加程序的概念复杂性以降低其计算复杂性。为了以合理的方式做到这一点，我们需要了解如何估算程序的计算复杂性。这是本章的主题。

11.1 思考计算复杂性

如何回答“以下函数运行需要多长时间？”这个问题？

def f(i):
   """Assumes i is an int and i >= 0"""
   answer = 1
   while i >= 1:
      answer *= i
      i -= 1
   return answer

我们可以在某些输入上运行程序并计时。但这并不会提供特别有用的信息，因为结果会依赖于

• 运行程序的计算机的速度

• 在那台机器上 Python 实现的效率

• 输入的值

我们通过使用更抽象的时间度量来解决前两个问题。我们不是以微秒来衡量时间，而是通过程序执行的基本步骤数量来衡量时间。

为了简单起见，我们将使用随机访问机器作为我们的计算模型。在随机访问机器中，步骤是依次执行的，一次一个。⁶⁶ 一个步骤是一个固定时间内执行的操作，比如将变量绑定到对象、进行比较、执行算术操作或访问内存中的对象。

现在我们有了一种更抽象的方式来思考时间的意义，我们转向输入值的依赖性问题。我们通过不再将时间复杂性表达为单一数字，而是与输入的大小相关联来解决这个问题。这使我们能够通过讨论每个算法的运行时间如何随输入大小的变化而变化，从而比较两种算法的效率。

当然，算法的实际运行时间不仅取决于输入的大小，还取决于它们的值。考虑线性搜索算法的实现。

def linear_search(L, x):
   for e in L:
      if e == x:
         return True
   return False

假设L是一个包含一百万个元素的列表，考虑调用linear_search(L, 3)。如果L中的第一个元素是3，linear_search几乎会立即返回True。另一方面，如果3不在L中，linear_search必须检查所有一百万个元素才能返回False。

一般来说，有三种广泛的情况需要考虑：

• 最佳情况运行时间是算法在输入尽可能有利时的运行时间。也就是说，最佳情况运行时间是给定大小的所有可能输入中的最小运行时间。对于linear_search，最佳情况运行时间与L的大小无关。

• 同样，最坏情况运行时间是给定大小的所有可能输入中的最大运行时间。对于linear_search，最坏情况运行时间与L的大小成线性关系。

• 与最佳情况和最坏情况运行时间的定义类比，*均情况（也称为期望情况）运行时间是给定大小的所有可能输入的*均运行时间。或者，如果人们对输入值的分布有一些先验信息（例如，90%的时间x在L中），可以考虑这些信息。

人们通常关注最坏情况。所有工程师都有一个共同信条，墨菲定律：如果某件事可能出错，它就一定会出错。最坏情况提供了运行时间的上限。在对计算所需时间有限制时，这一点至关重要。仅仅知道“在大多数情况下”航空交通控制系统会在碰撞发生前发出警告是不够的。

让我们看看阶乘函数的迭代实现的最坏情况运行时间：

def fact(n):
   """Assumes n is a positive int
      Returns n!"""
   answer = 1
   while n > 1:
      answer *=  n
      n -= 1
   return answer

运行此程序所需的步骤数大约是2（1步用于初始赋值语句，1步用于return） + 5n（计算while中的测试需要1步，在while循环中的第一个赋值语句需要2步，循环中的第二个赋值语句需要2步）。所以，例如，如果n是1000，函数大约会执行5002步。

很明显，随着n增大，担心5n与5n+2之间的差异有些无谓。因此，当我们推理运行时间时，通常会忽略加性常数。乘法常数则更为复杂。我们是否需要关心计算需要1000步还是5000步？乘法因素可能很重要。搜索引擎响应查询所需的时间是0.5秒还是2.5秒，可能会影响用户是使用该搜索引擎还是转向竞争对手。

另一方面，在比较两个不同算法时，即使乘法常数也往往是无关紧要的。回想一下，在第三章中，我们查看了两种算法：穷举枚举和二分搜索，用于寻找浮点数*方根的*似值。基于这些算法的函数在图 11-1 和图 11-2 中显示。

图 11-1 使用穷举枚举来*似*方根

图 11-2 使用二分搜索来*似*方根

我们看到，穷举枚举在处理许多x和epsilon值组合时是如此缓慢，以至于不切实际。例如，评估square_root_exhaustive(100, 0.0001)大约需要十亿次while循环迭代。相比之下，评估square_root_bi(100, 0.0001)大约只需 20 次稍微复杂的while循环迭代。当迭代次数差异如此之大时，循环中的指令数量其实并不重要。也就是说，乘法常数是无关紧要的。

11.2 渐进符号

我们使用一种称为渐进符号的东西，提供了一种正式的方式来讨论算法运行时间与其输入大小之间的关系。其根本动机是，几乎任何算法在小输入上运行时都是足够高效的。我们通常需要担心的是算法在非常大输入上运行时的效率。作为“非常大”的代理，渐进符号描述了当输入大小趋向于无穷大时算法的复杂度。

例如，考虑图 11-3 中的代码。

图 11-3 渐进复杂度

如果我们假设每行代码执行一次需要一个单位的时间，则该函数的运行时间可以描述为1000 + x + 2x²。常数1000对应于第一个循环执行的次数。项x对应于第二个循环执行的次数。最后，项2x²对应于在嵌套for循环中执行两个语句所花费的时间。因此，调用f(10)将打印

Number of additions so far 1000
Number of additions so far 1010
Number of additions so far 1210

而调用f(1000)将打印

Number of additions so far 1000
Number of additions so far 2000
Number of additions so far 2002000

对于小的x值，常数项占主导地位。如果x是10，则超过80%的步骤由第一个循环完成。另一方面，如果x是1000，前两个循环仅占约0.05%的步骤。当x为1,000,000时，第一个循环大约占总时间的0.00000005%，第二个循环约占0.00005%。总共2,000,000,000,000的2,000,001,001,000步骤在内部for循环的主体中。

显然，通过只考虑内层循环，即二次项，我们可以获得对这段代码在非常大输入下运行时间的有意义的概念。我们是否在乎这个循环需要2x²步而不是x²步？如果你的计算机每秒执行大约 1 亿步，评估f将需要大约5.5小时。如果我们能将复杂度降低到x²步，将只需大约2.25小时。在这两种情况下，结论是一样的：我们可能应该寻找更高效的算法。

这种分析引导我们在描述算法的渐*复杂度时使用以下经验法则：

• 如果运行时间是多个项的总和，保留增长率最大的项，去掉其他项。

• 如果剩余项是一个乘积，则去掉任何常数。

最常用的渐*符号被称为“大 O”符号。大 O 符号用于给出函数的渐*增长的上界（通常称为增长阶）。例如，公式f(x) ∈ O(x²)意味着函数f的增长速度不快于二次多项式x²，从渐*意义上看。

许多计算机科学家会滥用大 O 符号，像这样表述：“f(x)的复杂度是 O(x²)。”他们的意思是在最坏情况下，f的运行步骤不超过O(x²)。一个函数“在O(x²)”与“是O(x²)”之间的区别是微妙但重要的。说f(x) ∈ O(x²)并不排除f的最坏情况下运行时间明显小于O(x²)。为避免这种混淆，我们在描述某个上界和下界的渐*最坏情况下运行时间时，会使用大Θ（θ）。这称为紧界。

指尖练习：以下每个函数的渐*复杂度是什么？

 def g(L, e):
    """L a list of ints, e is an int"""
    for i in range(100):
        for e1 in L:
            if e1 == e:
                return True
    return False
def h(L, e):
    """L a list of ints, e is an int"""
    for i in range(e):
        for e1 in L:
            if e1 == e:
                return True
    return False

11.3 一些重要的复杂度类

大 O（和θ）的最常见实例如下所示。在每种情况下，n 是输入大小的度量。

• O(1)表示常数运行时间。

• O(log n)表示对数运行时间。

• O(n)表示线性运行时间。

• O(n log n)表示对数线性运行时间。

• O(n^k)表示多项式运行时间。注意 k 是一个常数。

• O(c^n)表示指数运行时间。这里常数是基于输入大小的幂。

11.3.1 常数复杂度

这表明渐进复杂度与输入的大小无关。这个类别中有很少有趣的程序，但所有程序都有一些片段（例如，计算 Python 列表的长度或乘两个浮点数），适合这个类别。常数运行时间并不意味着代码中没有循环或递归调用，但它确实意味着迭代或递归调用的次数与输入的大小无关。

11.3.2 对数复杂度

这样的函数具有复杂度，随着至少一个输入的对数而增长。二分查找，例如，在被搜索列表的长度上是对数级的。（我们将在第十二章中讨论二分查找并分析其复杂度。）顺便提一下，我们不关心对数的底数，因为使用一个底数和另一个底数之间的差异仅仅是一个常数乘法因子。例如，O(log[2](x)) = O(log[2](10)*log[10](x))。有许多有趣的函数具有对数复杂度。考虑一下

def int_to_str(i):
   """Assumes i is a nonnegative int
      Returns a decimal string representation of i"""
   digits = '0123456789'
   if i == 0:
      return '0'
   result = ''
   while i > 0:
      result = digits[i%10] + result
      i = i//10
   return result

由于这段代码中没有函数或方法调用，我们知道我们只需查看循环以确定复杂度类别。只有一个循环，因此我们需要做的就是描述迭代次数。这归结为在得到0的结果之前，我们可以使用//（向下取整除法）将i除以10的次数。因此，int_to_str的复杂度是O(log(i))。更确切地说，它是 θ(log(i))，因为 log(i) 是一个紧密的界限。

那么复杂度如何呢

def add_digits(n):
   """Assumes n is a nonnegative int
      Returns the sum of the digits in n"""
   string_rep = int_to_str(n)
   val = 0
   for c in string_rep:
       val += int(c)
   return val

使用int_to_str将n转换为字符串的复杂度是 θ(log(n))，并且int_to_str返回长度为log(n)的字符串。for循环将执行 θ(len(string_rep)) 次，即 θ(log(n)) 次。综合来看，假设表示数字的字符可以在常数时间内转换为整数，程序的运行时间将与 θ(log(n)) + θ(log(n)) 成正比，这使得它的复杂度是 θ(log(n))。

11.3.3 线性复杂度

许多处理列表或其他类型序列的算法是线性的，因为它们以一个常数（大于0）的次数访问序列的每个元素。

举个例子，

def add_digits(s):
   """Assumes s is a string of digits
      Returns the sum of the digits in s"""
   val = 0
   for c in string_rep:
       val += int(c)
   return val

这个函数在s的长度上是线性的，即 θ(len(s))。

当然，一个程序不需要有循环也可以具有线性复杂度。考虑一下

def factorial(x):
   """Assumes that x is a positive int
      Returns x!"""
   if x == 1:
      return 1
   else:
      return x*factorial(x-1)

这段代码中没有循环，因此为了分析复杂度，我们需要弄清楚进行多少次递归调用。调用序列就是

`factorial(x)`, `factorial(x-1)`, `factorial(x-2), … , factorial(1)`

这个序列的长度，因此函数的复杂度，是 θ(x)*。

到目前为止，我们只关注了代码的时间复杂度。这对于使用恒定空间的算法是可以的，但这个阶乘实现并不具备这一特性。如我们在第四章讨论的，每次递归调用factorial都会分配一个新的堆栈帧，并且该帧在调用返回之前会占用内存。在递归的最大深度，代码将分配x个堆栈帧，因此空间复杂度为O(x)。

空间复杂度的影响比时间复杂度更难以察觉。程序完成所需的一分钟或两分钟对用户来说非常明显，但它使用一兆字节还是两兆字节的内存则大多对用户是不可见的。这就是为什么人们通常更关注时间复杂度而不是空间复杂度的原因。例外情况发生在程序需要的空间超过运行它的机器的快速内存时。

11.3.4 对数线性复杂度

这比我们迄今为止看到的复杂度类稍微复杂一些。它涉及两个项的乘积，每个项都依赖于输入的大小。这是一个重要的类别，因为许多实际算法是对数线性的。最常用的对数线性算法可能是归并排序，其复杂度为θ(n log(n))，其中n是待排序列表的长度。我们将在第十二章中查看该算法并分析其复杂度。

11.3.5 多项式复杂度

最常用的多项式算法是二次算法，即它们的复杂度随着输入大小的*方而增长。例如，考虑在图 11-4 中实现的子集测试函数。

图 11-4 子集测试的实现

每次到达内层循环时，它将执行θ(len(L2))次。函数is_subset将执行外层循环θ(len(L1))次，因此内层循环将达到θ(len(L1)*len(L2))。

现在考虑图 11-5 中的函数intersect。构建可能包含重复项的列表的代码部分的运行时间显然是θ(len(L1)*len(L2))。乍一看，构建无重复列表的代码部分似乎是线性的，但实际上并非如此。

图 11-5 列表交集的实现

评估表达式e not in result可能涉及查看result中的每个元素，因此是θ(len(result))；因此，实现的第二部分的复杂度为θ(len(tmp)len(result))。然而，由于result和tmp的长度受限于L1和L2中较小者的长度，并且我们忽略了加法项，intersect的复杂度为θ(len(L1)len(L2))。

11.3.6 指数复杂性

正如我们将在本书后面看到的，许多重要问题本质上是指数级的，即完全解决它们可能需要与输入大小成指数关系的时间。这是令人遗憾的，因为编写一个在合理概率上需要指数时间运行的程序往往得不偿失。考虑一下图 11-6 中的代码。

图 11-6 生成幂集

函数gen_powerset(L)返回一个列表的列表，包含L的所有可能组合。例如，如果L是['x', 'y']，那么L的幂集将是一个包含列表[]、['x']、['y']和['x', 'y']的列表。

这个算法有些微妙。考虑一个包含n个元素的列表。我们可以用一个包含n个0和1的字符串来表示元素的任何组合，其中1表示元素的存在，0表示其不存在。包含没有项目的组合用全是0的字符串表示，包含所有项目的组合用全是1的字符串表示，仅包含第一个和最后一个元素的组合用100…001表示，等等。

生成长度为n的列表L的所有子列表可以如下进行：

• 生成所有n位的二进制数。这些数字从0到2^n - 1。

• 对于每个2^n 的二进制数b，通过选择L中索引与b中的1对应的元素来生成一个列表。例如，如果L是['x', 'y', 'z']，而b是101，则生成列表['x', 'z']。

尝试在包含字母表前 10 个字母的列表上运行gen_powerset。它会很快完成，并生成一个包含 1024 个元素的列表。接下来，尝试在前 20 个字母的列表上运行gen_powerset。这将需要一些时间，并返回一个大约有一百万个元素的列表。如果你在所有 26 个字母的列表上运行gen_powerset，你可能会厌倦等待它完成，除非你的计算机因尝试构建一个包含数千万个元素的列表而耗尽内存。甚至不要考虑在包含所有大写和小写字母的列表上运行gen_powerset。算法的第 1 步生成的二进制数是θ(2^(len(L)))，因此算法在 len(L)中是指数级的。

这是否意味着我们不能使用计算来解决指数级困难的问题？绝对不是。这意味着我们必须找到提供这些问题的*似解或在某些实例上找到精确解的算法。但这是后面章节的主题。

11.3.7 复杂性类的比较

本节中的图表旨在传达算法处于这些复杂性类之一或另一类的含义。

图 11-7 左侧的图表比较了常数时间算法与对数算法的增长。注意，输入的大小必须达到约 30,000，两者才会相交，即使常数非常小（15）。当输入大小为 100,000 时，对数算法所需的时间仍然相当小。其道理是，对数算法几乎与常数时间算法一样优秀。

图 11-7 右侧的图表展示了对数算法与线性算法之间的显著差异。虽然我们需要观察较大输入才能理解常数时间算法与对数时间算法之间的差异，但对数时间算法与线性时间算法之间的差异即使在小输入上也很明显。对数算法和线性算法相对性能的显著差异并不意味着线性算法不好。实际上，线性算法在很多情况下效率足够可接受。

图 11-7 常数、对数和线性增长

图 11-8 左侧的图表显示 O(n) 和 O(n log(n)) 之间存在显著差异。考虑到 log(n) 的增长非常缓慢，这可能看起来令人惊讶，但请记住，这是一个乘法因子。还要记住，在许多实际情况中，O(n log(n)) 是足够快速且有用的。另一方面，正如图 11-8 右侧的图所示，存在许多情况下，二次增长的速度是不可接受的。

图 11-8 线性、对数线性和二次增长

图 11-9 中的图表讨论了指数复杂度。在图 11-9 左侧的图中，y 轴左侧的数字从 0 到 6。然而，左上角的标记 1e29 意味着 y 轴上的每个刻度都应乘以 10²⁹。因此，绘制的 y 值范围从 0 到大约 6.6*10²⁹。在图 11-9 左侧的图中，二次增长的曲线几乎不可见。这是因为指数函数增长得如此迅速，以至于与最高点的 y 值（决定 y 轴的刻度）相比，指数曲线上早期点的 y 值（以及二次曲线上所有点）几乎与 0 无法区分。

图 11-9 右侧的图表通过在 y 轴上使用对数尺度解决了这个问题。人们很容易看到，指数算法对于除了最小输入之外的所有情况都是不切实际的。

注意，在对数尺度上绘制时，指数曲线呈现为直线。我们将在后面的章节中对此进行更深入的探讨。

图 11-9 二次和指数增长

11.4 本章引入的术语

• 概念复杂度

• 计算复杂度

• 随机访问机

• 计算步骤

• 最佳情况复杂度

• 最坏情况复杂度

• *均情况复杂度

• 期望情况复杂度

• 上界

• 渐进记号

• 大 O 记号

• 增长阶

• 大θ记号

• 下界

• 紧界

• 常数时间

• 对数时间

• 线性时间

• 对数线性时间

• 多项式时间

• 二次时间

• 指数时间

第十二章：一些简单的算法和数据结构

尽管我们在本书中花了相当多的页面讨论效率，但目标并不是让你成为设计高效程序的专家。还有许多专门讨论这一主题的长书（甚至一些不错的长书）。在第十一章中，我们介绍了一些复杂性分析的基本概念。在这一章中，我们利用这些概念来考察几个经典算法的复杂性。本章的目标是帮助你培养一些关于如何处理效率问题的一般直觉。当你完成本章时，你应该理解为什么有些程序瞬间完成，为什么有些需要整夜运行，以及为什么有些在你的一生中都无法完成。

本书中我们首次探讨的算法是基于穷举法的。我们认为现代计算机如此快速，以至于采用巧妙的算法往往是浪费时间。编写简单且显然正确的代码通常是正确的做法。

我们接着研究了一些问题（例如，寻找多项式根的*似值），在这些问题中，搜索空间太大，无法通过穷举法进行实际处理。这使我们考虑了更高效的算法，如二分法和牛顿-拉夫森法。关键在于，效率的关键是一个好的算法，而不是巧妙的编码技巧。

在科学（物理、生物和社会科学）中，程序员通常首先快速编码一个简单的算法，以测试关于数据集的假设的合理性，然后在少量数据上运行。如果这产生了令人鼓舞的结果，那么就开始了在大数据集上运行（或许是反复运行）可实施方案的艰苦工作。这种实施需要基于高效的算法。

高效的算法很难发明。成功的职业计算机科学家可能在整个职业生涯中只发明一个算法——如果他们幸运的话。我们大多数人从未发明过新算法。相反，我们学习将面临的复杂问题简化为之前解决过的问题。

更具体地说，我们

• 理解问题的内在复杂性。

• 考虑如何将这个问题分解为子问题。

• 将这些子问题与其他已经存在高效算法的问题关联起来。

本章包含一些示例，旨在让你对算法设计有一些直观的理解。书中还有许多其他算法。

请记住，最有效的算法并不总是首选算法。以最有效的方式完成所有事情的程序往往会让人难以理解。通常，从最直接的方式解决手头的问题是一个好策略，记录以找到任何计算瓶颈，然后寻找改善程序中导致瓶颈的部分的计算复杂性的方法。

12.1 搜索算法

搜索算法是一种在项目集合中查找具有特定属性的单个项目或一组项目的方法。我们将项目集合称为搜索空间。搜索空间可以是一些具体的东西，如一组电子病历，也可以是一些抽象的东西，如所有整数的集合。许多实际发生的问题都可以表述为搜索问题。

本书中早期提出的许多算法可以视为搜索算法。在第三章中，我们将寻找多项式根的*似值表述为一个搜索问题，并考察了三种算法——穷举枚举、二分搜索和牛顿-拉夫森法——用于搜索可能答案的空间。

在本节中，我们将研究两种搜索列表的算法。每种算法都符合规范。

def search(L, e):
    """Assumes L is a list.
       Returns True if e is in L and False otherwise"""

机智的读者可能会想，这是否与 Python 表达式e in L在语义上等价。答案是肯定的，是的。如果你不关心发现e是否在L中的效率，你应该简单地写出该表达式。

12.1.1 线性搜索和使用间接访问元素

Python 使用以下算法来确定元素是否在列表中：

for i in range(len(L)):
    if L[i] == e:
        return True
return False

如果元素e不在列表中，算法将执行θ(len(L))次测试，即复杂度在L的长度上至多为线性。为什么说“至多”线性？只有在循环内部的每个操作都可以在常数时间内完成时，它才是线性的。这引出了一个问题：Python 是否能在常数时间内检索列表的第i^{(th)个元素。由于我们的计算模型假设获取地址内容是常数时间操作，问题就变成了我们是否能在常数时间内计算列表第`i`}(th)个元素的地址。

让我们首先考虑每个列表元素都是整数的简单情况。这意味着列表中的每个元素大小相同，例如，占用四个内存单元（四个 8 位字节⁶⁹）。假设列表元素连续存储，列表第i^(th)个元素在内存中的地址为start + 4*i，其中start是列表起始地址。因此，我们可以假设 Python 能够在常数时间内计算出整数列表第i^(th)个元素的地址。

当然，我们知道 Python 列表可以包含除int之外的其他类型的对象，而且同一个列表可以包含多种类型和大小的对象。你可能会认为这会带来问题，但事实并非如此。

在 Python 中，列表由一个长度（列表中对象的数量）和一系列固定大小的指针⁷⁰表示对象。图 12-1 说明了这些指针的使用。

图 12-1 实现列表

被阴影区域表示的列表包含四个元素。最左边的阴影框包含一个指向整数的指针，指示列表的长度。其他阴影框中的每一个都包含一个指向列表中对象的指针。

如果长度字段占用四个内存单元，而每个指针（地址）占用四个内存单元，则列表的i^(th)元素的地址存储在地址start + 4 + 4*i中。同样，这个地址可以在常数时间内找到，然后可以使用该地址存储的值来访问i^(th)元素。这个访问也是一个常数时间的操作。

这个例子说明了计算中使用的最重要的实现技术之一：间接寻址。⁷¹一般来说，间接寻址涉及先访问包含所寻物体引用的其他内容，然后再访问所需物体。每次我们使用变量引用与该变量绑定的对象时，都会发生这种情况。当我们使用变量访问列表，然后通过列表中存储的引用访问另一个对象时，我们通过两个级别的间接寻址。⁷²

12.1.2 二分搜索和利用假设

回到实现search(L, e)的问题，θ(len(L))是我们能做的最好的吗？是的，如果我们对列表中元素的值和它们的存储顺序没有任何了解。在最坏的情况下，我们必须查看L中的每个元素，以确定L是否包含e。

但假设我们对元素存储的顺序有所了解，例如，假设我们知道我们有一个按升序存储的整数列表。我们可以改变实现，使得搜索在遇到一个大于要搜索的数字时停止，如图 12-2 所示。

图 12-2 有序列表的线性搜索

这将改善*均运行时间。然而，这不会改变算法的最坏情况复杂度，因为在最坏情况下，每个L中的元素都要被检查。

然而，我们可以通过使用一种类似于第三章中用于找到浮点数*方根*似值的二分搜索算法的二分查找算法，显著改善最坏情况下的复杂性。在那里，我们依赖于浮点数之间固有的全序关系。在这里，我们依赖于列表已排序的假设。

这个想法很简单：

1. 1. 选择一个索引i，大致将列表L分为两半。

2. 2. 询问L[i] == e。

3. 3. 如果没有，询问L[i]是否大于或小于e。

4. 4. 根据答案，搜索L的左半部分或右半部分以查找e。

鉴于该算法的结构，二分查找最直接的实现使用递归，这并不令人惊讶，如图 12-3 所示。

图 12-3 中的外部函数search(L, e)具有与图 12-2 中定义的函数相同的参数和规范。规范表明实现可以假定L是按升序排序的。确保这一假设成立的责任在于search的调用者。如果假设不成立，实现没有义务表现良好。它可能会工作，但也可能崩溃或返回错误的答案。是否应该修改search以检查假设是否成立？这可能消除错误来源，但会违背使用二分查找的目的，因为检查假设本身将耗时O(len(L))。

图 12-3 递归二分查找

像search这样的函数通常被称为包装函数。这个函数为客户端代码提供了一个良好的接口，但本质上是一个不进行复杂计算的通过函数。相反，它使用适当的参数调用辅助函数bSearch。这引出了一个问题：为什么不消除search，让客户端直接调用bin_search呢？原因是参数low和high与搜索列表中元素的抽象无关。它们是实现细节，应当对调用search的程序员隐藏。

现在让我们分析bin_search的复杂性。我们在上一节中展示了列表访问是常量时间。因此，可以看出，除了递归调用之外，bSearch的每个实例都是θ(1)。因此，bin_search的复杂性仅依赖于递归调用的次数。

如果这是一本关于算法的书，我们将深入分析一个称为递归关系的内容。但因为这不是，我们将采取一个不那么正式的方法，从“我们如何知道程序终止？”这个问题开始。回想一下在第三章中，我们对while循环问了同样的问题。我们通过提供循环的递减函数来回答了这个问题。这里我们也做同样的事情。在这个上下文中，递减函数具有以下性质：

• 它将正式参数绑定的值映射到一个非负整数。

• 当其值为0时，递归终止。

• 对于每个递归调用，递减函数的值小于调用该函数实例时的递减函数的值。

bin_search的递减函数是high–low。search中的if语句确保第一次调用bSearch时，该递减函数的值至少为0（递减函数性质 1）。

当进入bin_search时，如果high–low恰好为0，则该函数不进行递归调用—直接返回值L[low] == e（满足递减函数性质 2）。

bin_search函数包含两个递归调用。一个调用使用的参数覆盖mid左侧的所有元素，另一个调用使用的参数覆盖mid右侧的所有元素。在这两种情况下，high–low的值都减半（满足递减函数性质 3）。

我们现在明白了为什么递归会终止。下一个问题是，在high–low == 0之前，high–low的值可以被减半多少次？回想一下，log[y](x)是将y自身相乘多少次才能达到x。相反，如果将x除以y log[y](x)次，结果是1。这意味着high–low最多可以通过向下取整的除法被减半log[2](``high–low``)次，直到达到0。

最后，我们可以回答这个问题，二分查找的算法复杂度是什么？由于当search调用bSearch时，high–low的值等于len(L)-1，因此search的复杂度是θ(log(len(``L``)))。⁷³

练习题： 为什么代码在第二个递归调用中使用mid+1而不是mid？

12.2 排序算法

我们刚刚看到，如果我们知道一个列表是排序好的，我们可以利用这一信息大大减少搜索该列表所需的时间。这是否意味着当被要求搜索一个列表时，我们应该先对其进行排序，然后再进行搜索？

让θ(sortComplexity(L))成为对排序列表复杂度的紧密界限。因为我们知道可以在θ(len(L))时间内搜索一个无序列表，因此，是否应该先排序再搜索的问题归结为，sortComplexity(L) + log(len(L))是否小于len(L)？可悲的是，答案是否定的。要排序一个列表，至少必须查看列表中的每个元素一次，因此不可能在次线性时间内对列表进行排序。

这是否意味着二分搜索是一个没有实际意义的智力好奇？幸运的是，答案是否定的。假设我们期望多次搜索同一列表。一次性对列表进行排序的开销可能是值得的，然后在多次搜索中摊销排序的成本。如果我们期望搜索列表k次，相关的问题变为，sortComplexity(L) + klog(len(L))是否小于klen(L)？

随着k变得较大，排序列表所需的时间变得越来越不相关。k需要多大取决于排序列表所需的时间。例如，如果排序在列表大小上是指数级的，k必须相当大。

幸运的是，排序可以相当高效地完成。例如，大多数 Python 实现中标准的排序实现大约在O(n*log(n))时间内运行，其中n是列表的长度。实际上，您很少需要实现自己的排序函数。在大多数情况下，正确的做法是使用 Python 的内置sort方法（L.sort()对列表L进行排序）或其内置函数sorted（sorted(L)返回一个与L具有相同元素的列表，但不会修改L）。我们在此呈现排序算法，主要是为了提供一些思考算法设计和复杂性分析的练习。

我们从一个简单但低效的算法开始，即选择排序。选择排序，图 12-4，通过保持循环不变量来工作，给定将列表划分为前缀（L[0:i]）和后缀（L[i+1:len(L)]），前缀是排序的，并且前缀中的没有任何元素大于后缀中的最小元素。

我们使用归纳法推理循环不变量。

• 基础情况：在第一次迭代开始时，前缀为空，即后缀是整个列表。因此，不变量（显然）成立。

• 归纳步骤：在算法的每一步中，我们将一个元素从后缀移动到前缀。我们通过将后缀中的最小元素附加到前缀的末尾来实现这一点。由于在移动元素之前不变量成立，我们知道在附加元素后，前缀仍然是排序的。我们还知道，由于我们移除了后缀中的最小元素，前缀中的没有任何元素大于后缀中的最小元素。

• 终止：当退出循环时，前缀包括整个列表，而后缀为空。因此，整个列表现在按升序排序。

图 12-4 选择排序

很难想象有比这更简单或更明显正确的排序算法。不幸的是，它的效率相当低下。⁷⁴ 内部循环的复杂度是θ(len(L))。外部循环的复杂度也是θ(len(L))。因此，整个函数的复杂度是θ(len(L)²)。即，它在L的长度上是二次的。⁷⁵

12.2.1 归并排序

幸运的是，我们可以使用分治 算法来比二次时间表现得更好。基本思想是组合原问题的简单实例的解决方案。一般来说，分治算法的特点是

• 一个阈值输入大小，低于此大小的问题不进行细分。

• 将一个实例分割成的子实例的大小和数量。

• 用于组合子解决方案的算法。

阈值有时称为递归基。对于项目 2，通常考虑初始问题大小与子实例大小的比率。在我们到目前为止看到的大多数例子中，比率为2。

归并排序是一个典型的分治算法。它于 1945 年由约翰·冯·诺依曼发明，至今仍广泛使用。像许多分治算法一样，它最容易以递归方式描述：

1. 1. 如果列表长度为0或1，则已排序。

2. 2. 如果列表有多个元素，则将列表拆分为两个列表，并使用归并排序对每个列表进行排序。

3. 3. 合并结果。

冯·诺依曼的关键观察是，可以高效地将两个已排序的列表合并为一个已排序的列表。这个想法是查看每个列表的第一个元素，并将较小的一个移动到结果列表的末尾。当其中一个列表为空时，只需将另一个列表中剩余的项目复制过来。例如，考虑合并两个列表L_1 = [1,5,12,18,19,20]和L_2 = [2,3,4,17]：

合并过程的复杂度是什么？它涉及两个常数时间操作，比较元素的值和从一个列表复制元素到另一个列表。比较的数量是θ(len(L))，其中L是两个列表中较长的一个。复制操作的数量是θ(len(L1) + len(L2))，因为每个元素正好复制一次。（复制一个元素的时间取决于元素的大小。然而，这不会影响排序的增长顺序，作为列表中元素数量的函数。）因此，合并两个已排序的列表在列表长度上是线性的。

图 12-5 包含了合并排序算法的实现。

图 12-5 合并排序

注意我们将比较操作符作为merge_sort函数的参数，并编写了一个 lambda 表达式来提供默认值。因此，例如，代码

L = [2,1,4,5,3]
print(merge_sort(L), merge_sort(L, lambda x, y: x > y))

打印

[1, 2, 3, 4, 5] [5, 4, 3, 2, 1]

让我们分析一下merge_sort的复杂度。我们已经知道merge的时间复杂度是θ(len(L))。在每一层递归中，要合并的元素总数是len(L)。因此，merge_sort的时间复杂度是θ(len(``L``))乘以递归层数。由于merge_sort每次将列表分成两半，我们知道递归层数是θ(log(len(``L``)))。因此，merge_sort的时间复杂度是θ(n*log(n))，其中n是len(L)。⁷⁶

这比选择排序的θ(len(``L``)²)好得多。例如，如果L有10,000个元素，len(L)²是100百万，但len(L)*log[2](len(L))大约是130,000`。

这种时间复杂度的改进是有代价的。选择排序是就地排序算法的一个例子。因为它通过交换列表中的元素位置来工作，所以只使用了常量数量的额外存储（在我们的实现中是一个元素）。相比之下，合并排序算法涉及对列表的复制。这意味着它的空间复杂度是θ(len(``L``))。这对于大型列表来说可能是一个问题。⁷⁷

假设我们想对以名字和姓氏书写的名字列表进行排序，例如，列表['Chris Terman', ‘Tom Brady', 'Eric Grimson', 'Gisele Bundchen']。图 12-6 定义了两个排序函数，然后用这两个函数以两种不同方式对列表进行排序。每个函数使用了str类型的split方法。

图 12-6 对名字列表进行排序

当运行图 12-6 中的代码时，它打印

Sorted by last name = ['Tom Brady', 'Gisele Bundchen', 'Eric Grimson']
Sorted by first name = ['Eric Grimson', 'Gisele Bundchen', ‘Tom Brady']

手指练习：使用merge_sort对整数元组列表进行排序。排序顺序应由元组中整数的总和决定。例如，(5, 2)应在(1, 8)之前，并在(1, 2, 3)之后。

12.2.2 Python 中的排序

大多数 Python 实现中使用的排序算法称为timsort。⁷⁸ 关键思想是利用许多数据集中数据已经部分排序的事实。Timsort 的最坏情况性能与归并排序相同，但*均性能明显更好。

如前所述，Python 方法list.sort将列表作为第一个参数并修改该列表。相比之下，Python 函数sorted将可迭代对象（例如列表或视图）作为第一个参数并返回一个新的排序列表。例如，代码

L = [3,5,2]
D = {'a':12, 'c':5, 'b':'dog'}
print(sorted(L))
print(L)
L.sort()
print(L)
print(sorted(D))
D.sort()

将打印

[2, 3, 5]
[3, 5, 2]
[2, 3, 5]
['a', 'b', 'c']
AttributeError: ‘dict' object has no attribute ‘sort'

注意，当sorted函数应用于字典时，它返回字典键的排序列表。相比之下，当对字典应用sort方法时，会引发异常，因为没有dict.sort方法。

list.sort方法和sorted函数可以有两个额外参数。key参数在我们实现的归并排序中与compare的作用相同：它提供要使用的比较函数。reverse参数指定列表是相对于比较函数按升序还是降序排序。例如，代码

L = [[1,2,3], (3,2,1,0), 'abc']
print(sorted(L, key = len, reverse = True))

按长度反向顺序对L的元素进行排序并打印

`[(3, 2, 1, 0), [1, 2, 3], 'abc']`

list.sort方法和sorted函数都提供稳定排序。这意味着如果两个元素在排序中根据比较（在这个例子中是len）是相等的，它们在原始列表（或其他可迭代对象）中的相对顺序会在最终列表中保留。（由于在dict中没有键可以出现多次，应用于dict时sorted是否稳定的问题无关紧要。）

指尖练习：merge_sort是稳定排序吗？

12.3 哈希表

如果我们将归并排序与二分搜索结合起来，就有了一种很好的方式来搜索列表。我们使用归并排序在θ(nlog(n)) 时间内预处理列表，然后用二分搜索测试元素是否在列表中，这样的时间复杂度是θlog(n))。如果我们搜索列表k次，总体时间复杂度是θ(nlog(n) + k*log(n))。

这很好，但我们仍然可以问，当我们愿意进行一些预处理时，是否对搜索来说对数是我们能做到的最佳？

当我们在第五章介绍类型dict时，我们提到字典使用一种称为哈希的技术，以几乎与字典大小无关的时间进行查找。哈希表的基本思想很简单。我们将键转换为整数，然后使用该整数在列表中进行索引，这可以在常数时间内完成。原则上，任何类型的值都可以轻松转换为整数。毕竟，我们知道每个对象的内部表示是一系列位，任何位序列都可以视为表示一个整数。例如，字符串'abc'的内部表示是位序列011000010110001001100011，可以视为十进制整数6,382,179的表示。当然，如果我们想将字符串的内部表示用作列表的索引，列表将不得不相当长。

那么，当键已经是整数时呢？暂时想象一下，我们正在实现一个字典，所有键都是美国社会安全号码，九位整数。如果我们用包含10⁹个元素的列表来表示字典，并使用社会安全号码作为索引，我们可以以常数时间进行查找。当然，如果字典只包含一万（10⁴）人的条目，这将浪费很多空间。

这使我们进入哈希函数的话题。哈希函数将大量输入空间（例如，所有自然数）映射到较小的输出空间（例如，介于0和5000之间的自然数）。哈希函数可以用来将大量键转换为较小的整数索引空间。

由于可能输出的空间小于可能输入的空间，哈希函数是一种多对一映射，即多个不同的输入可能映射到相同的输出。当两个输入映射到相同的输出时，这被称为碰撞——我们将很快回到这个话题。一个好的哈希函数产生均匀分布；即范围内的每个输出都是同样可能的，从而最小化碰撞的概率。

图 12-7 使用了一个简单的哈希函数（回忆一下i%j返回整数i除以整数j的余数）来实现一个以整数为键的字典。

基本思想是通过一组哈希****桶表示Int_dict类的实例，其中每个桶是实现为元组的键/值对的列表。通过将每个桶作为列表，我们通过将所有哈希到同一桶的值存储在列表中来处理碰撞。

哈希表的工作原理如下：实例变量buckets被初始化为一个包含num_buckets个空列表的列表。要存储或查找具有键key的条目，我们使用哈希函数%将key转换为整数，并使用该整数索引到buckets中以找到与key关联的哈希桶。然后我们在线性搜索该桶（记住，它是一个列表），以查看是否有与键key的条目。如果我们正在查找并且有该键的条目，我们就简单地返回存储的值。如果没有该键的条目，我们返回None。如果要存储一个值，我们首先检查哈希桶中是否已经存在该键的条目。如果是，我们用一个新的元组替换该条目；否则我们将新的条目追加到桶中。

处理碰撞还有许多其他方法，有些比使用列表高效得多。但这可能是最简单的机制，如果哈希表相对于存储的元素数量足够大，并且哈希函数提供了足够好的均匀分布*似，这种方法效果很好。

图 12-7 使用哈希实现字典

请注意，__str__方法产生的字典表示与添加元素的顺序无关，而是按键的哈希值的顺序排列。

以下代码首先构造一个包含 17 个桶和 20 个条目的Int_dict。条目的值是整数0到19。键是随机选择的，使用random.choice从范围0到10⁵ - 1的整数中选择。（我们在第十六章和第十七章讨论random模块。）然后代码使用类中定义的__str__方法打印Int_dict。

import random
D = Int_dict(17)
for i in range(20):
    #choose a random int in the range 0 to 10**5 - 1
    key = random.choice(range(10**5))
    D.add_entry(key, i)
print('The value of the Int_dict is:')
print(D)

当我们运行这段代码时，它打印了⁷⁹

The value of the Int_dict is:
{99740:6,61898:8,15455:4,99913:18,276:19,63944:13,79618:17,51093:15,8271:2,3715:14,74606:1,33432:3,58915:7,12302:12,56723:16,27519:11,64937:5,85405:9,49756:10,17611:0}

以下代码通过迭代D.buckets打印各个哈希桶。（这严重违反了信息隐藏，但在教学上是有用的。）

print('The buckets are:')
for hash_bucket in D.buckets: #violates abstraction barrier
    print('  ', hash_bucket)

当我们运行这段代码时，它打印了

The buckets are:
   []
   [(99740, 6), (61898, 8)]
   [(15455, 4)]
   []
   [(99913, 18), (276, 19)]
   []
   []
   [(63944, 13), (79618, 17)]
   [(51093, 15)]
   [(8271, 2), (3715, 14)]
   [(74606, 1), (33432, 3), (58915, 7)]
   [(12302, 12), (56723, 16)]
   []
   [(27519, 11)]
   [(64937, 5), (85405, 9), (49756, 10)]
   []
   [(17611, 0)]

当我们违反抽象边界并查看Int_dict的表示时，我们看到一些哈希桶是空的。其他桶则包含一个或多个条目——这取决于发生的碰撞数量。

get_value的复杂度是什么？如果没有碰撞，它将是常数时间，因为每个哈希桶的长度将是 0 或 1。但当然，可能会发生碰撞。如果所有内容都哈希到同一个桶，它将在字典中的条目数量上是线性的，因为代码将在该哈希桶上执行线性搜索。通过使哈希表足够大，我们可以减少碰撞的数量，从而将复杂度视为常数时间。也就是说，我们可以用空间换取时间。但是，这种权衡是什么？要回答这个问题，我们需要使用一点概率，所以我们将答案推迟到第十七章。

12.4 在章节中介绍的术语

• 搜索算法

• 搜索空间

• 指针

• 间接寻址

• 二分查找

• 包装函数

• *摊复杂度

• 选择排序

• 循环不变式

• 分治算法

• 递归基

• 归并排序

• 原地排序

• 快速排序

• TimSort

• 稳定排序

• 哈希表

• 哈希函数

• 多对一映射

• 冲突

• 均匀分布

• 哈希桶

第十三章：绘图及类的更多信息

通常，文本是传达信息的最佳方式，但有时有一句中国谚语非常真实：“图片的意义可以表达*万字”。然而，大多数程序依赖文本输出与用户交流。为什么？因为在许多编程语言中，呈现视觉数据太难。幸运的是，在 Python 中这很简单。

13.1 使用 Matplotlib 绘图

Matplotlib是一个 Python 库模块，提供类似于 MATLAB 的绘图功能，“MATLAB 是一个用于算法开发、数据可视化、数据分析和数值计算的高级技术计算语言和交互式环境。” ⁸⁰ 在本书后面我们将看看其他提供 MATLAB 类似功能的 Python 库。在这一章中，我们专注于一些简单的数据绘图方式。关于 Matplotlib 绘图功能的完整用户指南可以在网站上找到。

`[plt.sourceforge.net/users/index.html](http://plt.sourceforge.net/users/index.html)`

我们不会在这里尝试提供用户指南或完整的教程。相反，在这一章中，我们仅提供几个示例图并解释生成这些图的代码。我们将在后面的章节中介绍许多其他绘图功能。

让我们从一个简单的例子开始，使用plt.plot生成一个单一的图表。执行

import matplotlib.pyplot as plt
plt.plot([1,2,3,4], [1,7,3,5]) #draw on current figure

将产生一个类似但不完全相同于图 13-1 的图表。你的图表可能会有一条彩色线。⁸¹ 此外，如果你使用大多数 Matplotlib 安装的默认参数设置运行此代码，线条的粗细可能不会像图 13-1 中的线条那么粗。我们使用了非标准的默认值来设置线宽和字体大小，以便图形在黑白打印时效果更佳。我们将在本节后面讨论如何做到这一点。

图表在你的显示器上出现的位置取决于你使用的 Python 环境。在用于生成本书本版的 Spyder 版本中，默认情况下，它出现在被称为“图表窗格”的地方。

图 13-1 一个简单的图表

生成多个图形并将其写入文件是可能的。这些文件可以有你喜欢的任何名称。默认情况下，它们都将具有.png的文件扩展名，但你可以使用关键字参数format将其更改为其他格式（例如，.jpg）。

代码

`plt.figure(1)                  #create figure 1 plt.plot([1,2,3,4], [1,2,3,4]) #draw on figure 1 plt.figure(2)                  #create figure 2 plt.plot([1,4,2,3], [5,6,7,8]) #draw on figure 2 plt.savefig('Figure-Addie')    #save figure 2 plt.figure(1)                  #go back to working on figure 1 plt.plot([5,6,10,3])           #draw again on figure 1 plt.savefig('Figure-Jane')     #save figure 1`

生成并保存到名为Figure-Jane.png和Figure-Addie.png的文件中的两个图表，见图 13-2。

图 13-2 Figure-Jane.png（左）和 Figure-Addie.png（右）的内容

请注意，最后一次调用plt.plot仅传递了一个参数。该参数提供了y值。对应的x值默认为range(len([5, 6, 10, 3]))所生成的序列，这就是它们在此情况下从0到3的原因。

Matplotlib 有一个 当前图形 的概念。执行 plt.figure(x) 将当前图形设置为编号为 x 的图形。后续执行的绘图函数调用隐式引用该图形，直到再次调用 plt.figure。这解释了为什么写入文件 Figure-Addie.png 的图形是第二个创建的图形。

让我们看另一个例子。 图 13-3 左侧的代码生成了 图 13-4 左侧的图。

图 13-3 生成复合增长图

图 13-4 复合增长图

如果我们查看代码，可以推断出这是一个展示初始投资 $10,000 在每年复合利率 5% 下增长的图。然而，仅仅通过查看图形本身无法轻易推断出来。这是一个不好的地方。所有图形都应该有信息丰富的标题，所有轴都应该标记。如果我们在代码末尾添加 图 13-3 右侧的行，我们就能得到 图 13-4 右侧的图形。

对于每个绘制的曲线，有一个可选参数是格式字符串，指示图形的颜色和线型。格式字符串的字母和符号源于 MATLAB，并由一个颜色指示符后跟一个可选的线型指示符组成。默认格式字符串是 'b-'，表示生成一条实心蓝线。要用黑色圆圈绘制本金增长，将调用 plt.plot(values) 替换为 plt.plot(values, 'ko')，这会生成 图 13-5 中的图形。有关颜色和线型指示符的完整列表，请参见

[`plt.org/api/pyplot_api.html#plt.pyplot.plot`](http://plt.org/api/pyplot_api.html#plt.pyplot.plot)

图 13-5 另一幅复合增长图

也可以更改绘图中使用的字体大小和线宽。这可以通过在单个函数调用中使用关键字参数来完成。例如，代码

principal = 10000 #initial investment
interestRate = 0.05
years = 20
values = []
for i in range(years + 1):
    values.append(principal)
    principal += principal*interestRate
plt.plot(values, '-k', linewidth = 30)
plt.title('5% Growth, Compounded Annually',
            fontsize = 'xx-large')
plt.xlabel('Years of Compounding', fontsize = 'x-small')
plt.ylabel('Value of Principal ($)')

生成的图形在 图 13-6 中看起来故意奇怪。

图 13-6 奇怪的图形

也可以更改默认值，这些值被称为“rc 设置”。（名称“rc”源于 Unix 中用于运行时配置文件的 .rc 文件扩展名。）这些值存储在一个字典样式的变量中，可以通过名称 plt.rcParams 访问。因此，例如，你可以通过执行代码将默认线宽设置为 6 个点⁸²。

`plt.rcParams['lines.linewidth'] = 6`.

rcParams 设置的数量非常庞大。完整列表可以在这里找到

[`plt.org/users/customizing.html`](http://plt.org/users/customizing.html)

如果你不想担心自定义单个参数，可以使用预定义的样式表。相关描述可以在这里找到

`[`plt.org/users/style_sheets.html#style-sheets`](http://plt.org/users/style_sheets.html#style-sheets)`

本书中大多数剩余示例使用的值是通过以下代码设置的

#set line width
plt.rcParams['lines.linewidth'] = 4
#set font size for titles 
plt.rcParams['axes.titlesize'] = 20
#set font size for labels on axes
plt.rcParams['axes.labelsize'] = 20
#set size of numbers on x-axis
plt.rcParams['xtick.labelsize'] = 16
#set size of numbers on y-axis
plt.rcParams['ytick.labelsize'] = 16
#set size of ticks on x-axis
plt.rcParams['xtick.major.size'] = 7
#set size of ticks on y-axis
plt.rcParams['ytick.major.size'] = 7
#set size of markers, e.g., circles representing points
plt.rcParams['lines.markersize'] = 10
#set number of times marker is shown when displaying legend
plt.rcParams['legend.numpoints'] = 1 
#Set size of type in legend
plt.rcParams['legend.fontsize'] = 14

如果你在彩色显示器上查看图表，就很少有理由更改默认设置。我们定制了设置，以便在将图表缩小以适应页面并转换为灰度时，更容易阅读图表。

13.2 绘制抵押贷款，扩展示例

在第十章中，我们通过一个抵押贷款的层次结构来说明子类化的使用。我们通过观察“我们的程序应该生成旨在显示抵押贷款随时间变化的图表”来结束这一章。图 13-7 通过添加方便生成这些图表的方法来增强类 Mortgage。（图 10-10 中的函数 find_payment 在第 10.4 节中讨论。）

图 13-7 类 Mortgage 及其绘图方法

类 Mortgage 中的非*凡方法是 plot_tot_paid 和 plot_net。方法 plot_tot_paid 绘制已支付款项的累计总额。方法 plot_net 绘制通过减去偿还部分贷款所获得的权益而得到的抵押贷款总成本的*似值。⁸³

在函数 plot_net 中，表达式 np.array(self.outstanding) 执行类型转换。到目前为止，我们一直使用 list 类型的参数调用 Matplotlib 的绘图函数。在后台，Matplotlib 已将这些列表转换为另一种类型 **array**，这是 numpy 模块的一部分。导入 import numpy as np 和调用 np.array 使这一点明确。

**Numpy** 是一个提供科学计算工具的 Python 模块。除了提供多维数组外，它还提供各种数学功能。本书后面会有更多关于 numpy 的内容。

有许多方便的方式来操作数组，这些方法在列表中并不容易实现。特别是，可以使用数组和算术运算符形成表达式。在 numpy 中创建数组有多种方式，但最常见的方法是先创建一个列表，然后转换它。考虑以下代码

`import numpy as np`
`a1 = np.array([1, 2, 4]) print('a1 =', a1) a2 = a1*2 print('a2 =', a2) print('a1 + 3 =', a1 + 3) print('3 - a1 =', 3 - a1) print('a1 - a2 =', a1 - a2) print('a1*a2 =', a1*a2)`

表达式 a1*2 将 a1 的每个元素乘以常数 2。表达式 a1 + 3 将整数 3 加到 a1 的每个元素上。表达式 a1 ‑ a2 从 a1 的相应元素中减去 a2 的每个元素（如果数组长度不同，会发生错误）。表达式 a1*a2 将 a1 的每个元素与 a2 的相应元素相乘。当上述代码运行时，它打印

a1 = [1 2 4]
a2 = [2 4 8]
a1 + 3 = [4 5 7]
3 - a1 = [ 2  1 -1]
a1 - a2 = [-1 -2 -4]
a1*a2 = [ 2  8 32]

图 13-8 重复了图 10-11 中 Mortgage 的三个子类。每个子类都有一个独特的 __init__ 方法，覆盖了 Mortgage 中的 __init__ 方法。子类 Two_rate 也覆盖了 Mortgage 的 make_payment 方法。

图 13-8 Mortgage的子类

图 13-9 和图 13-10 包含可以用于生成旨在提供有关不同类型抵押贷款洞见的图表的函数。

函数compare_mortgages，图 13-9，创建不同类型抵押贷款的列表，并模拟对每种贷款进行一系列付款。然后调用plot_mortgages，图 13-10，以生成图表。

图 13-9 比较抵押贷款

图 13-10 生成抵押贷款图表

图 13-10 中的函数plot_mortgages使用Mortgage中的绘图方法生成包含三种不同类型抵押贷款信息的图表。plot_mortgages中的循环使用索引i从列表morts和styles中选择元素，以确保在图形中以一致的方式表示不同类型的抵押贷款。例如，由于morts中的第三个元素是可变利率抵押贷款，styles中的第三个元素是'k:'，因此可变利率抵押贷款总是使用黑色虚线绘制。局部函数label_plot用于为每个图表生成适当的标题和轴标签。plt.figure的调用确保标题和标签与相应的图表相关联。

调用

`compare_mortgages(amt=200000, years=30, fixed_rate=0.07,                  pts = 3.25, pts_rate=0.05, var_rate1=0.045,                  var_rate2=0.095, var_months=48)`

生成的图表（图 13-11 到 13-13）比较三种类型的抵押贷款。

图 13-11 中显示的图表是通过调用plot_payments生成的，它简单地将每种抵押贷款的每期付款与时间进行绘制。包含图例的框出现的位置是由于在调用plt.legend时提供给关键字参数loc的值。当loc绑定到'best'时，位置会自动选择。该图表清楚地显示了每月付款如何随时间变化（或不变化），但对每种抵押贷款的相对成本没有太多启示。

图 13-11 不同类型抵押贷款的每月付款

图 13-12 中的图表是通过调用plot_tot_pd生成的。它通过绘制每月开始时已产生的累计成本来比较每种抵押贷款的成本。

图 13-12 不同类型抵押贷款的时间成本

图 13-13 中的图表显示了剩余债务（左侧）和持有抵押贷款的总净成本（右侧）。

图 13-13 不同类型抵押贷款的剩余余额和净成本

13.3 传染病的交互式图表

当我对这本书进行最后润色时，我正在家中遵循与限制 Covid-19 疾病传播相关的“社交距离”限制。像许多呼吸道病毒一样，SARS-CoV-2 病毒主要通过人与人之间的接触传播。社交距离旨在减少人类之间的接触，从而限制由病毒引起的疾病传播。

图 13-14 包含对传染病发生率随时间变化的简单模拟。参数fixed是一个字典，定义了与感染传播相关的关键变量的初始值。参数variable是一个字典，定义了与社交距离相关的变量。稍后我们将展示如何在交互式图中改变variable的值。

图 13-14 传染病传播的模拟

在书的后面部分，我们详细讨论了模拟模型。然而，在这里，我们关注的是交互式绘图，模拟的目的是为我们提供一些有趣的绘图内容。如果你不理解模拟的细节，那也没关系。

图 13-15 包含一个生成静态图的函数，该图显示了每一天的感染人数。它还包含一个文本框，显示感染总人数。以txt_box = plt.text开头的语句指示 Python 在由plt.text的前两个参数指定的位置开始绘制由第三个参数指定的文本。表达式plt.xlim()[1]/2将文本的左边缘放置在 x 轴左端（该图的 0）和 x 轴右端之间的中间位置。表达式plt.ylim()[1]/1.25将文本放置在 y 轴底部（该图的 0）到 y 轴顶部之间的 80%处。

图 13-15 绘制感染历史的函数

图 13-16 使用图 13-14 和图 13-15 中的函数生成一个图图 13-17，显示感染人数——假设没有社交距离。fixed中的值并不基于特定的疾病。然而，假设一个人*均每天与 50 人“接触”可能会让人感到惊讶。不过，请记住，这个数字包括间接接触，例如，与感染者乘坐同一辆公交车或接触可能被感染者留下病原体的物体。

图 13-16 用一组参数生成图

图 13-17 感染人数的静态图

图表显示当前感染人数的快速上升，随后迅速下降至零当前感染的稳定状态。这种快速增长发生是因为每个感染者会感染多个其他人，因此能够传播感染的人数呈指数增长。没有新感染的稳定状态是因为人口已经达到了群体免疫。当一个足够大比例的人口对一种疾病免疫时（假设从这种疾病中恢复的人不会再感染），就会有长时间没有人感染该疾病，这最终导致没有人再能传播它。⁸⁴ 如果我们想探索不同参数设置的影响，可以在fixed中改变一些变量的值，并生成另一个图表。然而，这是一种相当繁琐的方式来探索“如果……会怎样”的情境。相反，让我们生成一个包含滑块⁸⁵的图形，可以用来动态改变与社交距离相关的关键参数：reduced_contacts_per_day、red_start和red_end。

图形将有四个独立的组件：主图和每个字典variable元素的一个滑块。我们首先通过指定图形的整体尺寸（宽 12 英寸，高 8.5 英寸）、位置（以与文本框相同的方式指定）和每个组件的尺寸（相对于整个图形的大小）来描述图形的布局。我们还为每个组件绑定一个名称，以便后续引用。

fig = plt.figure(figsize=(12, 8.5))
infections_ax = plt.axes([0.12, 0.2, 0.8, 0.65])
contacts_ax = plt.axes([0.25, 0.09, 0.65, 0.03])
start_ax = plt.axes([0.25, 0.06, 0.65, 0.03])
end_ax = plt.axes([0.25, 0.03, 0.65, 0.03]

接下来的代码行定义了三个滑块，每个滑块对应我们想要变化的一个值。首先，我们导入一个包含Slider类的模块。

from Matplotlib.widgets import Slider

接下来，我们创建三个滑块，将每个滑块绑定到一个变量上。

contacts_slider = Slider(
                      contacts_ax,  # axes object containing the slider
                      ‘reduced\ncontacts/day',  # name of slider
                      0,   # minimal value of the parameter
                      50,  # maximal value of the parameter
                      50)  # initial value of the parameter)
contacts_slider.label.set_fontsize(12)
start_day_slider = Slider(start_ax, ‘start reduction', 1, 30, 20)
start_day_slider.label.set_fontsize(12)
end_day_slider = Slider(end_ax, 'end reduction', 30, 400, 200)
end_day_slider.label.set_fontsize(12)

接下来，我们提供一个函数update，该函数根据滑块的当前值更新图表。

def update(fixed, infection_plot, txt_box,
           contacts_slider, start_day_slider, end_day_slider):
    variable = {'red_daily_contacts': contacts_slider.val,
                ‘red_start': start_day_slider.val,
                ‘red_end': end_day_slider.val}
    I, total_infections = simulation(fixed, variable)
    infection_plot.set_ydata(I)   # new y-coordinates for plot
    txt_box.set_text(f'Total Infections =  {total_infections:,.0f}')

接下来，我们需要指示 Python 在滑块的值发生变化时调用update。这有点棘手。Slider类包含一个方法on_changed，它接受一个类型为function的参数，该参数在滑块变化时被调用。这个函数始终只接受一个参数，即表示滑块当前值的数字。然而，在我们的情况下，每次滑块改变时，我们希望使用所有三个滑块的值和字典fixed中的值运行模拟。

我们通过引入一个新的函数来解决这个问题，该函数是on_changed的合适参数。函数slider_update接受所需的数字参数，但并不使用它。相反，定义slider_update的 lambda 表达式捕获了与fixed、infection_plot、txt_box和三个滑块绑定的对象。然后，它使用这些参数调用update。

slider_update = lambda _: update(fixed, infection_plot, txt_box,
                                 contacts_slider, start_day_slider,
                                 end_day_slider)
contacts_slider.on_changed(slider_update)
start_day_slider.on_changed(slider_update)
end_day_slider.on_changed(slider_update)

最后，我们绘制感染曲线，并在与infections_ax绑定的图形部分更新文本框。

infections, total_infections = simulation(fixed, variable)
plt.axes(infections_ax)
infection_plot, txt_box = plot_infections(infections,
                                          total_infections, fixed)

当运行此代码时，它会生成图 13-18 中的图形。⁸⁶

图 13-18 初始滑块值的交互式图

现在，我们可以轻松实验许多滑块值的组合，其中一个组合如图 13-19 所示。

图 13-19 滑块值改变后的交互式图

图 13-19 显示，如果在 20 天后将接触次数减少到*均每天 25 次，并保持这个水* 40 周，则总感染人数会减少。更重要的是，感染的峰值数量（因此对医疗系统的最大负担）会显著降低。这通常被称为扁*化曲线。

13.4 章节中引入的术语

• 图形

• Matplotlib

• 图

• 当前图形

• rcParams

• 数组

• numpy

• 交互式图

• 文本框

• 群体免疫

• 滑块

• 扁*化曲线

第十四章：背包和图优化问题

优化问题的概念提供了一种结构化的方式来思考解决许多计算问题。每当你开始解决一个涉及寻找最大、最小、最多、最少、最快、最便宜等的问题时，很可能可以将该问题映射到一个经典的优化问题上，而这个问题有已知的计算解决方案。

一般来说，优化问题有两个部分：

• 一个需要最大化或最小化的目标函数。例如，波士顿和伊斯坦布尔之间的机票费用。

• 一组必须遵循的约束条件（可能为空）。例如，旅行时间的上限。

在本章中，我们引入了优化问题的概念并给出了一些例子。我们还提供了一些解决这些问题的简单算法。在第十五章中，我们讨论了一种有效解决重要类别优化问题的方法。

本章要点包括：

• 许多重要的问题可以用一种简单的方式表述，自然引导到计算解决方案。

• 将一个看似新颖的问题简化为一个已知问题的实例，可以让你利用现有的解决方案。

• 背包问题和图问题是可以将其他问题简化为的类别。

• 穷举枚举算法提供了一种简单但通常在计算上不可行的方式来寻找最佳解决方案。

• 贪婪算法通常是寻找一个相当不错但不总是最佳的优化问题解决方案的实用方法。

和往常一样，我们将用一些 Python 代码和编程技巧补充计算思维的材料。

14.1 背包问题

作为一个小偷并不容易。除了显而易见的问题（确保家中空无一人、撬锁、规避警报、处理伦理困境等），小偷还必须决定偷什么。问题在于，大多数家庭的有价值物品超出一般小偷能携带的数量。一个可怜的小偷该怎么办？他（或她）需要找到提供最大价值的物品集合，同时不超过他的携带能力。

假设，例如，一个小偷有一个最多能装20磅战利品的背包⁸⁷，他闯入一所房子，发现图 14-1 中的物品。显然，他无法将所有物品放入背包，因此他需要决定带走什么，留下什么。

图 14-1 物品表

14.1.1 贪婪算法

找到这个问题的*似解的最简单方法是使用贪心算法。小偷会先选择最好的物品，然后是下一个最好的，持续进行直到他达到极限。当然，在这样做之前，小偷必须决定什么是“最好”。最好的物品是最有价值的，最轻的，还是可能是价值与重量比最高的物品？如果他选择最高价值，他将只拿走电脑，可以以$200变卖。如果他选择最低重量，他将依次拿走书、花瓶、收音机和画作，总价值为$170。最后，如果他决定最好的意味着价值与重量比最高，他将首先拿走花瓶和时钟。这将留下三个价值与重量比为10的物品，但其中只有书能放进背包。拿走书后，他将拿走仍能放进去的剩余物品，即收音机。他的战利品总价值将为$255。

尽管按密度贪心（价值与重量比）恰好为这个数据集提供了最佳结果，但没有保证贪心按密度算法总能找到比按重量或价值贪心算法更好的解决方案。更一般来说，任何通过贪心算法找到的这类背包问题的解决方案都不一定是最优的。⁸⁸我们稍后会更详细地讨论这个问题。

接下来三幅图中的代码实现了这三种贪心算法。在图 14-2 中，我们定义了类Item。每个Item都有一个name、value和weight属性。我们还定义了三个可以绑定到我们实现的greedy的参数key_function的函数；见图 14-3。

图 14-2 类Item

图 14-3 贪心算法的实现

通过引入参数key_function，我们使得greedy不再依赖于考虑列表元素的顺序。所需的只是key_function定义了items中元素的排序。然后，我们使用这个排序生成一个包含与items相同元素的排序列表。我们使用内置的 Python 函数sorted来实现这一点。（我们使用sorted而不是sort，因为我们希望生成一个新列表，而不是改变传入函数的列表。）我们使用reverse参数来表示我们希望列表从最大（根据key_function）排序到最小。

greedy的算法效率如何？需要考虑两件事：内置函数sorted的时间复杂度，以及在greedy主体中for循环的执行次数。循环的迭代次数受限于items中的元素数量，即为θ(n)，其中n是items的长度。然而，Python 内置排序函数的最坏情况时间大致为θ(n log n)，其中n是待排序列表的长度。⁸⁹因此，greedy 的运行时间为θ(n log n)。

图 14-4 中的代码构建了一项列表，然后使用不同的排序方式测试函数greedy。

图 14-4 使用贪心算法选择项目

当执行test_greedys()时，它会打印

Use greedy by value to fill knapsack of size 20
Total value of items taken is 200.0
    <computer, 200, 20>
Use greedy by weight to fill knapsack of size 20
Total value of items taken is 170.0
    <book, 10, 1>
    <vase, 50, 2>
    <radio, 20, 4>
    <painting, 90, 9>
Use greedy by density to fill knapsack of size 20
Total value of items taken is 255.0
    <vase, 50, 2>
    <clock, 175, 10>
    <book, 10, 1>
    <radio, 20, 4>

14.1.2  0/1 背包问题的最优解决方案

假设我们决定*似解不够好，即我们希望这个问题的最佳可能解决方案。这样的解决方案称为最优，这并不奇怪，因为我们正在解决一个优化问题。恰好，我们的盗贼面临的问题是经典优化问题的一个实例，称为0/1 背包问题。0/1 背包问题可以形式化如下：

• 每个项目由一对表示，<*value, weight*>。

• 背包可以容纳总重量不超过w的项目。

• 长度为 n 的向量 I 表示可用项目的集合。向量的每个元素都是一个项目。

• 长度为 n 的向量 V 用于指示每个项目是否被盗贼拿走。如果 V[i] = 1，则项目 I[i]被拿走。如果 V[i] = 0，则项目 I[i]未被拿走。

• 找到一个最大化的 V

  受限于以下约束条件

  

让我们看看如果尝试以直接方式实现此问题的公式会发生什么：

1. 1. 列举所有可能的项目组合。也就是说，生成项目集的所有子集。⁹⁰这称为幂集，已在第十一章讨论过。

2. 2. 移除所有重量超过允许重量的组合。

3. 3. 从剩余组合中选择一个价值最大的组合。

这种方法肯定能找到一个最佳答案。然而，如果原始项目集很大，运行将需要很长时间，因为正如我们在第 11.3.6 节看到的，子集的数量随着项目数量的增加而迅速增长。

图 14-5 包含了这种暴力解决 0/1 背包问题的直接实现。它使用了在图 14-2、图 14-3、图 14-4 中定义的类和函数，以及在图 11-6 中定义的函数gen_powerset。

图 14-5 暴力求解 0/1 背包问题的最优解

这个实现的复杂度是θ(n2^{n`)`，其中`n`是`items`的长度。函数`gen_powerset`返回一个包含`Item`的列表的列表。这个列表的长度为`2`}n，其中最长的列表的长度为n。因此，choose_best中的外部循环将执行θ*(2^n)次，内部循环的执行次数由n限制。

许多小的优化可以应用于加速这个程序。例如，gen_powerset可以有如下头部

def `gen_powerset`(`item`s, con`str`aint, get_val, get_weight)

并且只返回那些符合重量约束的组合。或者，choose_best可以在超过重量约束时立即退出内部循环。虽然这些类型的优化通常是值得做的，但它们并没有解决根本问题。choose_best的复杂度仍然是θ(n*2^n)，因此当items很大时，choose_best仍然会运行很长时间。

从理论上讲，这个问题是绝望的。0/1 背包问题在物品数量上本质上是指数级的。然而，从实践的角度来看，这个问题远非绝望，正如我们将在 15.2 节中讨论的那样。

当运行test_best时，它会打印

Total value of items taken is 275.0
<clock, 175, 10>
<painting, 90, 9>
<book, 10, 1>

注意，这个解决方案找到了总价值高于贪心算法找到的任何解决方案的物品组合。贪心算法的本质是在每一步做出最佳（由某种标准定义的）局部选择。它做出了一个局部最优的选择。然而，正如这个例子所示，一系列局部最优的决策并不总是会导致一个全局最优的解决方案。

尽管贪心算法并不总是找到最佳解决方案，但它们在实践中经常被使用。通常情况下，它们比保证找到最优解的算法更容易实现且更高效。正如伊万·博斯基曾经说过的：“我认为贪婪是健康的。你可以贪婪，但仍然对自己感觉良好。” ⁹¹

对于一个称为分数（或连续）背包问题的背包问题变体，贪心算法可以保证找到一个最优解。由于这个变体中的物品可以无限分割，因此总是选择尽可能多的具有最高剩余价值与重量比的物品是有意义的。假设，例如，我们的窃贼在房子里只发现了三样有价值的东西：一袋金粉、一袋银粉和一袋葡萄干。在这种情况下，贪婪密度算法将始终找到最优解。

14.2 图优化问题

让我们考虑另一种优化问题。假设你有一份美国各城市之间所有航空航班价格的清单。假设对于所有城市 A, B, 和 C，从 A 经 B 飞往 C 的费用是从 A 飞往 B 的费用加上从 B 飞往 C 的费用。你可能会想问的几个问题是：

• 两个城市之间的最少停留次数是多少？

• 两个城市之间的最低机票价格是多少？

• 在不超过两次停留的情况下，两个城市之间的最低机票价格是多少？

• 访问某些城市集合的最低费用是什么？

所有这些问题（以及其他许多问题）都可以很容易地形式化为图问题。

图⁹²是由称为 节点（或 顶点）的对象构成的一组对象，这些对象通过一组 边（或 弧）连接。如果边是单向的，则该图称为 有向图 或 有向图。在有向图中，如果存在一条从 n1 到 n2 的边，我们称 n1 为 源节点 或 父节点，而 n2 为 目标节点 或 子节点。

如果存在一系列边 < e[0], … , e[n] >，使得 e[0] 的起点是 n1，e[n] 的终点是 n2，并且在序列中所有边 e[1] 到 e[n] 的起点是 e[i]* 的终点 e[i][−1]，那么称图中包含 路径 从 n1 到 n2。一个从节点到自身的路径称为 循环。包含循环的图称为 有向图，而不包含循环的图称为 无向图。

图通常用于表示各部分之间存在有趣关系的情况。图在数学中首次被记录的使用是在 1735 年，当时瑞士数学家莱昂哈德·欧拉使用了后来被称为 图论 的方法来制定和解决 柯尼斯堡桥问题。

柯尼斯堡，当时是东普鲁士的首都，建于两条河流的交汇处，河流中有多个岛屿。岛屿通过七座桥相互连接，并与大陆相连，如 图 14-6 左侧的地图所示。出于某种原因，市民们对是否能进行一次恰好经过每座桥一次的散步这个问题产生了浓厚的兴趣。

图 14-6 左侧是柯尼斯堡的桥，右侧是欧拉简化后的地图

欧拉的伟大见解在于，通过将每个独立的陆地块视为一个点（想想“节点”），每座桥视为连接这两个点的线（想想“边”），可以大大简化问题。镇的地图可以用右侧的无向图表示，如图 14-6 所示。欧拉推理，如果一次走遍每条边，走的过程中每个节点（即在行走过程中被进入和退出的任何岛屿）必须由偶数条边连接。由于这个图中的节点没有偶数条边，欧拉得出结论，不可能每座桥恰好走一次。

比起柯尼斯堡桥问题，甚至比欧拉定理（它将欧拉对柯尼斯堡桥问题的解决方案进行了推广）更有趣的是，使用图论来帮助理解问题的整个想法。

例如，仅需要对欧拉使用的那种图形进行一个小的扩展，就可以建模一个国家的高速公路系统。如果图（或有向图）中的每条边都有一个权重，则称之为加权图。使用加权图，高速公路系统可以表示为一个图，其中城市由节点表示，连接它们的高速公路作为边，每条边标记为两个节点之间的距离。更一般来说，我们可以通过加权有向图表示任何道路地图（包括单行街道的地图）。

同样，万维网的结构可以表示为一个有向图，其中节点是网页，只有在页面A上有指向页面B的链接时，节点A到节点B之间才会有一条边。流量模式可以通过为每条边添加一个权重来建模，以指示使用频率。

图形还有许多不太明显的用途。生物学家使用图来建模从蛋白质相互作用到基因表达网络的各种现象。物理学家使用图来描述相变。流行病学家使用图来建模疾病轨迹，等等。

图 14-7 包含实现与节点、加权边和边对应的抽象类型的类。

图 14-7 节点和边

拥有一个节点类可能看起来有些多余。毕竟，Node类中的任何方法都没有执行任何有趣的计算。我们引入这个类只是为了给我们灵活性，以便在某些时刻决定引入一个具有附加属性的Node子类。

图 14-8 包含Digraph和Graph类的实现。

图 14-8 类Graph和Digraph

一个重要的决定是用于表示Digraph的数据结构选择。一个常见的表示方式是n × n 邻接矩阵，其中n是图中节点的数量。矩阵的每个单元格包含关于连接节点对<*i*, *j*>的边的信息（例如，权重）。如果边是无权的，则只有在存在从i到j的边时，每个条目为True。

另一种常见的表示方式是邻接表，我们在这里使用。类Digraph有两个实例变量。变量nodes是一个包含Digraph中节点名称的 Python 列表。节点的连通性使用实现为字典的邻接表表示。变量edges是一个字典，将Digraph中的每个Node映射到该Node的子节点列表。

类Graph是Digraph的子类。它继承了Digraph的所有方法，除了重写的add_edge方法。（这并不是实现Graph的最节省空间的方式，因为它每条边存储了两次，一次用于Digraph的每个方向。但它的优点在于简单。）

你可能想停下来思考一下，为什么Graph是Digraph的子类，而不是反过来。在我们观察的许多子类化示例中，子类为超类添加了属性。例如，类Weighted_edge向类Edge添加了一个weight属性。

在这里，Digraph和Graph具有相同的属性。唯一的区别是add_edge方法的实现。任一类都可以通过继承另一类的方法轻松实现，但选择哪个作为超类并不是任意的。在第十章中，我们强调了遵循替代原则的重要性：如果客户端代码使用超类的实例正常工作，那么当用子类的实例替代超类的实例时，它也应正常工作。

确实，如果客户端代码使用Digraph的实例工作正常，那么如果用Graph的实例替代Digraph的实例，它也会正常工作。反之则不然。有许多算法适用于图（通过利用边的对称性），而这些算法在有向图上并不适用。

14.2.1 一些经典的图论问题

使用图论来制定问题的一个好处是，有众所周知的算法可以解决许多图上的优化问题。一些最著名的图优化问题包括：

• 最短路径。对于某一对节点n1 和n2，找到边的最短序列<*s[n], d[n]*>（源节点和目标节点），使得

  • ○ 第一条边中的源节点是n1。

  • ○ 最后一条边的目标节点是n2。

  • ○ 对于序列中的所有边e1 和e2，如果e2 在序列中跟随e1，则e2 的源节点是e1 的目标节点。

• 最短加权路径。这类似于最短路径，但我们不是选择连接两个节点的最短边序列，而是定义某个函数来计算序列中边的权重（例如，它们的总和），并最小化该值。这就是谷歌和苹果地图在计算两个点之间的驾驶路线时所解决的那种问题。

• 最小割。给定图中两个节点集，割是一组边，去除这些边会消除从一个集合中的每个节点到另一个集合中每个节点的所有路径。

• 最大团。团是一组节点，集合中的每对节点之间都有一条边。⁹³ 最大团是图中最大规模的团。最小割是去除这些边后能实现这一点的最小边集。

14.2.2 最短路径：深度优先搜索和广度优先搜索

社交网络由个体和个体之间的关系组成。这些通常被建模为图，其中个体为节点，边为关系。如果关系是对称的，边是无向的；如果关系是非对称的，边是有向的。一些社交网络建模多种类型的关系，在这种情况下，边上的标签指示关系的类型。

在 1990 年，剧作家约翰·古埃尔写了《六度分隔》。该剧的可疑前提是“这个星球上的每个人仅被其他六个人隔开。”他的意思是，如果我们利用“认识”的关系建立一个包含地球上每个人的社交网络，那么任何两个个体之间的最短路径至多会经过六个其他节点。

一个较少假设性的问题是，使用 Facebook 上“朋友”关系的两个人之间的距离。例如，你可能想知道你是否有一个朋友，他有一个朋友，而那个朋友是嘎嘎女士的朋友。让我们考虑设计一个程序来回答这样的问题。

朋友关系（至少在 Facebook 上）是对称的，例如，如果萨姆是安德烈亚的朋友，安德烈亚也是萨姆的朋友。因此，我们将使用类型为 Graph 的社交网络来实现。然后我们可以将寻找你与嘎嘎女士之间最短连接的问题定义为：

• 让 *G* 表示朋友关系的图。

• 对于 *G*，寻找最短节点序列，[你，…，嘎嘎女士]，使得

• 如果 n[i] 和 n[i][+1] 是序列中的连续节点，则在 G 中有一条边连接 n[i] 和 n[i][+1]。

图 14-9 包含一个递归函数，该函数找到 Digraph 中两个节点 start 和 end 之间的最短路径。由于 Graph 是 Digraph 的子类，因此它适用于我们的 Facebook 问题。

图 14-9 深度优先搜索最短路径算法

DFS实现的算法是递归深度优先搜索（DFS）算法的一个示例。一般来说，深度优先搜索算法通过选择起始节点的一个子节点开始。然后它选择该节点的一个子节点，依此类推，越来越深入，直到它达到目标节点或一个没有子节点的节点。然后搜索回溯，返回到最*的尚未访问的有子节点的节点。当所有路径都被探索完毕时，它选择从起点到目标的最短路径（假设存在这样一条路径）。

该代码比我们刚刚描述的算法更复杂，因为它必须处理图中包含循环的可能性。它还避免探索比已找到的最短路径更长的路径。

• 函数shortest_path以path == []（表示当前探索的路径为空）和shortest == None（表示尚未找到从start到end的路径）调用DFS。

• DFS开始时选择start的一个子节点。然后它选择该节点的一个子节点，依此类推，直到到达节点end或一个没有未访问子节点的节点。

  • ○ 检查if node not in path防止程序陷入循环。

  • ○ 检查if shortest == None or len(path) < len(shortest)用于决定继续搜索该路径是否可能产生比当前找到的最佳路径更短的路径。

  • ○ 如果是这样，DFS被递归调用。如果它找到一条到end的路径，其长度不超过目前为止找到的最佳路径，则更新shortest。

  • ○ 当path中的最后一个节点没有子节点可供访问时，程序回溯到之前访问过的节点，并访问该节点的下一个子节点。

• 当从start到end的所有可能的最短路径都被探索后，函数返回。

图 14-10 包含一些代码，该代码运行图 14-9 中的代码。图 14-10 中的函数test_SP首先构建一个有向图，如图中所示，然后在节点 0 和节点 5 之间搜索最短路径。

图 14-10 测试深度优先搜索代码

当执行时，test_SP生成的输出是

Current DFS path: 0
Current DFS path: 0->1
Current DFS path: 0->1->2
Current DFS path: 0->1->2->3
Current DFS path: 0->1->2->3->4
Current DFS path: 0->1->2->3->5
Current DFS path: 0->1->2->4
Current DFS path: 0->2
Current DFS path: 0->2->3
Current DFS path: 0->2->3->4
Current DFS path: 0->2->3->5
Current DFS path: 0->2->3->1
Current DFS path: 0->2->4
Shortest path found by DFS: 0->2->3->5

请注意，在探索路径0->1->2->3->4后，它回退到节点3并探索路径0->1->2->3->5。在将其保存为迄今为止的最短成功路径后，它回退到节点2并探索路径0->1->2->4。当到达该路径的尽头（节点4）时，它回退到节点0并调查从0到2的边开始的路径。依此类推。

在图 14-9 中实现的 DFS 算法找到边数最少的路径。如果边具有权重，它不一定找到最小化边权重和的路径。不过，它可以很容易地修改以实现此目的。

手指练习： 修改深度优先搜索算法以找到使权重总和最小的路径。假设所有权重都是正整数。

当然，除了深度优先搜索之外，还有其他遍历图的方法。另一种常见的方法是广度优先搜索（BFS）。广度优先遍历首先访问起始节点的所有子节点。如果其中没有一个是结束节点，则访问每个子节点的所有子节点，依此类推。与通常递归实现的深度优先搜索不同，广度优先搜索通常是迭代实现的。BFS 同时探索多条路径，每次迭代为每条路径添加一个节点。由于它以长度递增的顺序生成路径，第一次找到以目标节点为最后节点的路径保证边数最少。

图 14-11 包含使用广度优先搜索在有向图中找到最短路径的代码。变量path_queue用于存储当前正在探索的所有路径。每次迭代开始时，从path_queue中移除一条路径并将其分配给tmp_path。如果tmp_path的最后一个节点是end，则tmp_path是最短路径并被返回。否则，创建一组新路径，每条路径通过添加其子节点扩展tmp_path。这些新路径随后被添加到path_queue中。

图 14-11 广度优先搜索最短路径算法

当这些线

sp = BFS(g, nodes[0], nodes[5])
print('Shortest path found by BFS:', print_path(sp))

添加到test_SP末尾并执行函数时，它会打印附加行

Current BFS path: 0
Current BFS path: 0->1
Current BFS path: 0->2
Current BFS path: 0->1->2
Current BFS path: 0->2->3
Current BFS path: 0->2->4
Current BFS path: 0->1->2->3
Current BFS path: 0->1->2->4
Current BFS path: 0->2->3->4
Current BFS path: 0->2->3->5
Shortest path found by BFS: 0->2->3->5

令人安心的是，每个算法找到的路径长度相同。在这种情况下，它们找到的是相同的路径。然而，如果图中存在多条最短路径，DFS 和 BFS 不一定找到相同的最短路径。

如上所述，广度优先搜索是一种方便的搜索路径的方式，因为第一次找到的路径保证是最少边数的路径。

手指练习： 考虑一个带权边的有向图。BFS 找到的第一条路径是否保证能够最小化边的权重总和？

14.3 本章引入的术语

• 优化问题

• 目标函数

• 约束集

• 背包问题

• 贪心算法

• 最优解

• 0/1 背包问题

• 局部最优

• 全局最优

• 连续背包问题

• 图

• 节点（顶点）

• 边（弧）

• 有向图（digraph）

• 源（父）节点

• 目标（子）节点

• 路径

• 循环

• 有环图

• 无环图

• 图论

• 带权图

• 邻接矩阵

• 邻接表

• 最短路径

• 最短带权路径

• 最小割

• 最大团

• 深度优先搜索（DFS）

• 回溯法

• 广度优先搜索（BFS）