练习 18：性能测量
译者：飞龙
自豪地采用谷歌翻译
在本练习中，你将学习使用多种工具来分析你创建的数据结构和算法的性能。为了使这个介绍专注并且简洁，我们将查看练习 16 中的sorted.py算法的性能，然后在视频中，我会分析我们迄今为止所做的所有数据结构的性能。
性能分析和调优是我最喜欢的计算机编程活动之一。在看电视的时候，我是那个手里拿着一团缠着的绳子的人，并且只打算把它解开，直到它很好并且有序。我喜欢探究复杂的奥秘，代码性能是最复杂的奥秘之一。有一些很好的并且实用的工具，用于分析代码的性能，使之比调试更好。
编码时不要试图实现性能改进，除非它们是显而易见的。我更喜欢使我的代码的初始版本保持极其简单和朴素，以便我可以确保它正常工作。然后，一旦它运行良好，但也许很慢，我启动我的分析工具，并开始寻找方法使其更快，而不降低稳定性。最后一部分是关键，因为许多程序员觉得如果能使代码更快，那么可以降低代码的稳定性和安全性。
工具
在本练习中，我们将介绍许多有用的 Python 工具，以及一些改进任何代码性能的一般策略。我们将使用的工具有：
在继续之前，请确保安装任何需要安装的软件。然后获取sorted.py和test_sorting.py文件的副本，以便我们可以将这些工具应用到这些算法中。
timeit
timeit模块不是非常有用。它所做的就是接受字符串形式的 Python 代码，并使用一些时间运行它。你不能传递函数引用，.py文件或除字符串之外的任何内容。我们可以在test_sorting.py的结尾，测试test_bubble_sort函数需要多长时间：
if __name__ == '__main__':
import timeit
print(timeit.timeit("test_bubble_sort()", setup="from __main__ import test_bubble_sort"))
它也不会产生有用的测量或任何信息，为什么某些东西可能很慢。我们需要一种方式来衡量代码运行的时间长短，这样做太笨重了，无法使用。
cProfile和profile
接下来的两个工具，对于测量代码的性能来说更为有用。我建议使用cProfile来分析代码的运行时间，并且当你在分析中需要更多的灵活性时，保存profile。为了对你的测试运行cProfile，请更改test_sorting.py文件的末尾，来简单地运行测试函数：
if __name__ == '__main__':
test_bubble_sort()
test_merge_sort()
并将max_numbers更改为大约 800，或足够大的数字，以便你可以测量效果。一旦你完成了，然后在你的代码上运行cProfile：
$ python -m cProfile -s cumtime test_sorting.py | grep sorting.py
我使用了| grep sorted.py，只是将输出缩小到我关心的文件，但删除该部分命令可以查看完整的输出。我在相当快的电脑上获得的 800 个数字的结果是：
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 0.145 0.145 test_sorting.py:1(<module>)
1 0.000 0.000 0.128 0.128 test_sorting.py:25(test_bubble_sort)
1 0.125 0.125 0.125 0.125 sorting.py:6(bubble_sort)
1 0.000 0.000 0.009 0.009 sorting.py:1(<module>)
1 0.000 0.000 0.008 0.008 test_sorting.py:33(test_merge_sort)
2 0.001 0.000 0.006 0.003 test_sorting.py:7(random_list)
1 0.000 0.000 0.005 0.005 sorting.py:37(merge_sort)
1599/1 0.001 0.000 0.005 0.005 sorting.py:47(merge_node)
7500/799 0.004 0.000 0.004 0.000 sorting.py:72(merge)
799 0.001 0.000 0.001 0.000 sorting.py:27(count)
2 0.000 0.000 0.000 0.000 test_sorting.py:14(is_sorted)
我在顶部添加了标题，以便你看到输出表示什么。每个标题的意思是：
ncalls
该函数的调用次数
tottime
总执行时间
percall
函数每个调用的总时间
cumtime
函数的累计时间
percall
每个调用的累计时间
filename:lineno(function)
名称、行号和涉及到的函数
那些标题名称也可以使用-s参数来获取。然后，我们可以对此输出进行快速分析：
bubble_sort被调用一次，但merge_node被调用了 1599 次，并且merge甚至调用了 7500 次。这是因为merge_node和merge是递归的，所以对一个有 800 个元素的随机列表排序时，他们会产生大量的调用。
即使bubble_sort不像merge或merge_node一样被频繁调用，它也是很慢的。这符合两种算法的性能预期。归并排序的最坏情况是O(nlogn)，但是对于冒泡排序，它是O(n^2)。如果你有 800 个元素，那么800 * log(800)约为 5347，而800^2是 640000！这些数字不一定会转化为这些算法运行的精确秒数，但它们确实会转化为相对比较。
count函数被调用 799 次，这最有可能是巨大的浪费。我们实现的DoubleLinkedList并不追踪元素的数量，而是必须在每一次你想知道数量的时候遍历这个列表。我们在这里的count函数中使用相同的方法，并且导致了整个列表中的 800 个元素的 799 次遍历。将max_numbers更改为 600 或 500 在这里查看规律。注意在我们的实现中，count是否运行了n-1次？这意味着我们遍历了几乎所有 800 个元素。
现在让我们查看，dllist.py如何影响其性能：
同样，我已经添加了标题，以便你可以看到发生了什么。在这种情况下，你可以看到，与merge，merge_node和count函数相比，dllist.py函数不会影响性能。这是很重要的，因为大多数程序员将运行优化DoubleLinkedList数据结构，但在merge_sort实现中可以获得更大的收益，并且完全可以避免使用bubble_sort。始终以最小的努力获得最大的改进。
性能分析
分析性能只是一件事情，找出什么较慢，然后试图确定为什么它较慢。它类似于调试，除了你最好不要改变代码的行为。完成后，代码的工作方式应该完全一样，仅仅是更快执行。有时修复性能也会发现错误，但是当你尝试加速时，最好不要尝试完全重新设计。一次只做一件事。
在开始分析性能之前，另一件重要的事情是，软件所需的一些指标。通常快即是好，但没有目标，你最终会提出一些完全不必要的解决方案。如果你的系统以 50 个请求/秒执行，并且你真的只需要 100 个请求/秒，那么没有必要使用 Haskell 完全重写它，来获得 200 的性能。这个过程完全关于，“节省最多的钱，并且付出最少的努力”，并且你需要某种测量作为目标。
你可以从运营人员那里获得大部分测量结果，并且应该有很好的图表，显示了 CPU 使用情况，请求/秒，帧速率，任何他们或客户认为重要的东西。然后，你可以与他们一起设计测试，证明一些缓慢的东西需要定位，以便你可以改进代码来达到所需的目标。你可以从系统中榨取更多的性能，从而节省资金。你可以尝试并得出结论，这只是一个需要更多 CPU 资源的难题。有了一个作为目标的指标，你会明白什么时候放弃，或已经做得足够了。
你可以用于分析的最简单过程是这样：
- 在代码上运行性能分析器，就像我在这里使用测试所做的一样。你得到的信息越多越好。有关免费的其他工具，请参阅深入学习部分。向人们询问一些工具，它们用于分析系统的速度。
- 识别最慢和最小的代码段。不要编写一个巨大的函数，并尝试分析它。很多时候这些函数很慢，因为它们使用了一大堆其他很慢的函数。首先找到最慢和最小的函数，你最有可能得到最大的收益，并付出最少的努力。
- 审查这些缓慢的代码，和任何他们接触的代码，寻找代码缓慢的可能原因。循环内有循环吗？调用函数太频繁吗？在调查诸如缓存之类的复杂技术之前，寻找可以改变的简单事物。
- 一旦你列出了所有最慢和最小的函数，以及简单的更改，使它们更快并寻找规律。你能在其它你看不到的地方做这件事吗？
- 最后，如果没有简单更改你可以更改的小函数，可以寻求可能的较大改进。也许真的是完全重写的时候了吗？不要这样做，直到你至少尝试了简单的修复。
- 列出你尝试的所有东西，以及你所完成的所有性能增益。如果你不这样做，那么你会不断地回到你已经处理过的函数上，并浪费精力。
在这个过程中，“最慢和最小”的概念是变化的。你修复了十几个 10 行的函数并使其更快，这意味着现在你可以查看最慢的 100 行的函数。一旦你让 100 行的函数运行得更快，你可以查看正在运行的更大的一组函数，并提出使其加速的策略。
最后，加速的最好办法是完全不做。如果你正在对相同条件进行多重检查，请找到避免多次检查的方法。如果你反复计算数据库中的同一列，请执行一次。如果你在密集的循环中调用函数，但数据不怎么改变，请缓存它或者事先计算出来。在许多情况下，你可以通过简单地事先计算一些东西，并一次性存储它们，来用空间换时间。
在下一个练习中，我们将会使用这个过程，来改进这些算法的性能。
挑战练习
此练习的挑战是，将我对bubble_sort和merge_sort所做的所有操作，都应用到目前为止所创建的所有数据结构和算法。我不期望你改进他们，但只是在开发测试来显示性能问题时，记下笔记并分析性能。抵制现在修改任何东西的诱惑，因为我们将在练习 19 中提高性能。
研究性学习
- 到目前为止，对所有代码运行这些分析工具，并分析性能。
- 将结果与算法和数据结构的理论结果进行比较。
破坏它
尝试编写使数据结构崩溃的病态测试。你可能需要为他们提供大量数据，但使用性能分析的信息来确保正确。
深入学习
- 查看
line_profiler，它是另一个性能测量工具。它的优点是，你只能衡量你关心的函数，但缺点是你必须更改源代码。 -
pyprof2calltree和KCacheGrind是更先进的工具，但老实说只能在 Linux 上工作。在视频中，我演示在 Linux 下使用它们。
