练习 19：改善性能

原文：Exercise 19: Improving Performance

译者：飞龙

协议：CC BY-NC-SA 4.0

自豪地采用谷歌翻译

这几乎完全是视频练习，其中我演示了如何改进你至今为止编写的代码的性能，但首先你应该尝试它。你已经分析了 练习 18 的代码的速度有多慢，所以现在是时候实现你的一些想法。修复简单的性能问题时，我会给你一个简单的列表来寻找和修改：

• 循环内的循环的重复计算可以避免。冒泡排序是经典案例，这就是我教它的原因。，一旦你看到，冒泡排序与其他方法相比有多糟糕，你将开始认识到这是一个需要避免的常见模式。
• 重复计算一些没有实际变化的东西，或者在更改过程中可以计算一次。在sorted.py和其他数据结构中的count()函数是一个很好的例子。你可以在函数内跟踪数据结构的大小。每次添加时，你可以增加它，并且每次删除时，减少它。每次都不需要遍历整个列表。你还可以使用这个预先计算的计数，通过检查count == 0来改进其他功能的逻辑。
• 使用错误的数据结构。在字典中，我使用DoubleLinkedList来演示这个问题。字典需要随机访问元素，至少是桶的列表中的元素。使用DoubleLinkedList的DoubleLinkedList意味着每次你想访问第 n 个元素，你必须遍历所有元素直到 n。用 Python 列表替换它将大大提高性能。这是一个练习，使用现有代码从更简单的数据结构中构建数据结构，因此不一定是实现最好的 Python Dictionary（它已经有一个了）的练习。
• 对数据结构使用错误的算法。冒泡排序显然是错误的算法（不要再使用了），但要记住归并排序和快速排序是否更好，这可能取决于数据结构。归并排序对于这些类型的链接数据结构来说是非常好的，但对于 Python list之类的数组却不是很好。快速排序对于list更好，但在链接的数据结构上不是很好。
• 不在最佳的地方优化常见的操作。在DoubleLinkedList中，你将经常从桶的开头开始，并在槽中搜索一个值。在当前的代码中，这些槽进来时，你简单地添加它们，这可能是随机的也可能不是。如果你采取了一个规则，在插入时排序这些列表，那么寻找元素会更容易和更快捷。当槽的值大于你要查找的值时，你可以停止，因为你知道它是有序的。这样做使得插入速度更慢，但使几乎每一个其它操作变快，因此要为练习选择正确的设计。如果你需要执行大量的插入，那么这不是很机智。但是，如果你的分析显示，你需要执行很少的插入，但是很多的访问，这是个加速的不错方式。
• 手写代码，而不是使用现有的代码。我们正在做练习来学习数据结构，但在现实世界中，你不会这样做。Python 已经有很好的数据结构，内置在语言中并进行了优化。你应该首先使用这些，如果性能分析表明你自己的数据结构会更快，那么编写自己的数据结构。即使这样，你应该查找一个现有的数据结构，其他人使其能工作，而不是手写自己的东西。在这个练习中，写一些测试，将你的Dictionary和 Python 内置类型list比较，看看你可能有多少优势。
• 在不太擅长的语言中使用递归。简单地说，merge_sort代码可以通过给它一个比 Python 堆栈更大的列表，来使其崩溃。尝试给它一些丧心病狂的东西，例如 3000 个元素的列表，然后慢慢地减少元素数量，直到找到导致 Python 耗尽堆栈的极限值。Python 不执行某些递归优化，所以没有特别考虑的递归会像这样失败。在这种情况下，重写merge_sort来使用循环会更好（但要困难得多）。

在练习 18 的分析过程中，你应该有了一些很大的收获。现在你的任务是尝试实现它们，以及提升代码的性能。

挑战练习

尝试使用你的分析和上述建议性改进的描述，来系统地提升代码的性能。“系统地”的含义是，使用锁定步骤控制的方法来完成，使用数据来确认你已经改进了一些东西。这是你在此练习中遵循的流程：

• 选择你的第一个，最小、最慢的代码，并确保有一个测试来告诉你它有多慢。确保你有一系列的度量，让你了解其速度。如果可以的话，绘制出来。
• 尝试提升速度，然后重新运行测试。继续尝试压榨这段代码的所有的性能。
• 如果你尝试更改代码，并且不会改进任何事情，那么你可以确定你做错了，并且撤销该更改并尝试其他操作。这很重要，因为你正在验证假设，所以如果你在其中留下无用的代码更改，可能会改变你可以修复的，其他函数的性能。撤销更改并尝试不同的方法，或转向另一段代码。
• 重新测量其他最小最慢的代码片段，看看它们是否已更改。你的修复可能已修复了其他代码，因此重新确认你认为自己知道的东西。
• 一旦你完成了你确认的一切，再次运行你的测量，并选择新的代码段来尝试改进。
• 从第 1 步开始保持测试（他们应该是自动测试），因为你需要避免退步。如果你看到一个函数的修改，导致其他函数变慢，那么要么修复它，要么简单地撤销修改，并尝试一些新的方法。

深入学习

你应该研究 Tim Sort 的原始邮件，最后研究由 EU FP7 ENVISAGE 研究人员在 2015 年发现的错误。原始电子邮件于 2002 年发送，随后实现。这个 bug 发现了 13 年了。当你去实现自己的算法想法时，记住这一点。即使大型项目的顶尖开发人员也会在它们的算法中遗留 bug，它们很长时间都没有发现。另一个例子是 OpenSSL 项目，它几十年来一直存在 bug，因为每个人都相信“专业密码学家”创建了代码。原来，即使是所谓的专业密码学家也可以写出糟糕的代码。使新的算法正确需要特殊技能，并且我认为 -- 使用定理证明工具来验证正确性。除非你有这样的背景，创造新的算法和数据结构可能会产生危险。这包括加密算法和加密网络协议。只要你掌握实现技能，实现其他人已经证明的算法完全正常，运行良好。但是不要在没有一些帮助的情况下制作自己的头发数据结构。实现其他人已经证明的算法完全没问题，并且是个好的练习。但是不要在没有一些帮助的情况下制作自己的粗制滥造的数据结构。