私信发送成功
Watch Star Fork

龙哥盟飞龙 / lmpythw-zh

克隆/下载
一键复制 编辑 原始数据 按行查看 历史
ex18.md 11.01 KB wizardforcel 提交于 2017-08-08 11:49 . ex18

练习 18:性能测量

原文:Exercise 18: Measuring Performance

译者:飞龙

协议:CC BY-NC-SA 4.0

自豪地采用谷歌翻译

在本练习中,你将学习使用多种工具来分析你创建的数据结构和算法的性能。为了使这个介绍专注并且简洁,我们将查看练习 16 中的sorted.py算法的性能,然后在视频中,我会分析我们迄今为止所做的所有数据结构的性能。

性能分析和调优是我最喜欢的计算机编程活动之一。在看电视的时候,我是那个手里拿着一团缠着的绳子的人,并且只打算把它解开,直到它很好并且有序。我喜欢探究复杂的奥秘,代码性能是最复杂的奥秘之一。有一些很好的并且实用的工具,用于分析代码的性能,使之比调试更好。

编码时不要试图实现性能改进,除非它们是显而易见的。我更喜欢使我的代码的初始版本保持极其简单和朴素,以便我可以确保它正常工作。然后,一旦它运行良好,但也许很慢,我启动我的分析工具,并开始寻找方法使其更快,而不降低稳定性。最后一部分是关键,因为许多程序员觉得如果能使代码更快,那么可以降低代码的稳定性和安全性。

工具

在本练习中,我们将介绍许多有用的 Python 工具,以及一些改进任何代码性能的一般策略。我们将使用的工具有:

在继续之前,请确保安装任何需要安装的软件。然后获取sorted.pytest_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"))

它也不会产生有用的测量或任何信息,为什么某些东西可能很慢。我们需要一种方式来衡量代码运行的时间长短,这样做太笨重了,无法使用。

cProfileprofile

接下来的两个工具,对于测量代码的性能来说更为有用。我建议使用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_nodemerge是递归的,所以对一个有 800 个元素的随机列表排序时,他们会产生大量的调用。

即使bubble_sort不像mergemerge_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如何影响其性能:

同样,我已经添加了标题,以便你可以看到发生了什么。在这种情况下,你可以看到,与mergemerge_nodecount函数相比,dllist.py函数不会影响性能。这是很重要的,因为大多数程序员将运行优化DoubleLinkedList数据结构,但在merge_sort实现中可以获得更大的收益,并且完全可以避免使用bubble_sort。始终以最小的努力获得最大的改进。

性能分析

分析性能只是一件事情,找出什么较慢,然后试图确定为什么它较慢。它类似于调试,除了你最好不要改变代码的行为。完成后,代码的工作方式应该完全一样,仅仅是更快执行。有时修复性能也会发现错误,但是当你尝试加速时,最好不要尝试完全重新设计。一次只做一件事。

在开始分析性能之前,另一件重要的事情是,软件所需的一些指标。通常快即是好,但没有目标,你最终会提出一些完全不必要的解决方案。如果你的系统以 50 个请求/秒执行,并且你真的只需要 100 个请求/秒,那么没有必要使用 Haskell 完全重写它,来获得 200 的性能。这个过程完全关于,“节省最多的钱,并且付出最少的努力”,并且你需要某种测量作为目标。

你可以从运营人员那里获得大部分测量结果,并且应该有很好的图表,显示了 CPU 使用情况,请求/秒,帧速率,任何他们或客户认为重要的东西。然后,你可以与他们一起设计测试,证明一些缓慢的东西需要定位,以便你可以改进代码来达到所需的目标。你可以从系统中榨取更多的性能,从而节省资金。你可以尝试并得出结论,这只是一个需要更多 CPU 资源的难题。有了一个作为目标的指标,你会明白什么时候放弃,或已经做得足够了。

你可以用于分析的最简单过程是这样:

  • 在代码上运行性能分析器,就像我在这里使用测试所做的一样。你得到的信息越多越好。有关免费的其他工具,请参阅深入学习部分。向人们询问一些工具,它们用于分析系统的速度。
  • 识别最慢和最小的代码段。不要编写一个巨大的函数,并尝试分析它。很多时候这些函数很慢,因为它们使用了一大堆其他很慢的函数。首先找到最慢和最小的函数,你最有可能得到最大的收益,并付出最少的努力。
  • 审查这些缓慢的代码,和任何他们接触的代码,寻找代码缓慢的可能原因。循环内有循环吗?调用函数太频繁吗?在调查诸如缓存之类的复杂技术之前,寻找可以改变的简单事物。
  • 一旦你列出了所有最慢和最小的函数,以及简单的更改,使它们更快并寻找规律。你能在其它你看不到的地方做这件事吗?
  • 最后,如果没有简单更改你可以更改的小函数,可以寻求可能的较大改进。也许真的是完全重写的时候了吗?不要这样做,直到你至少尝试了简单的修复。
  • 列出你尝试的所有东西,以及你所完成的所有性能增益。如果你不这样做,那么你会不断地回到你已经处理过的函数上,并浪费精力。

在这个过程中,“最慢和最小”的概念是变化的。你修复了十几个 10 行的函数并使其更快,这意味着现在你可以查看最慢的 100 行的函数。一旦你让 100 行的函数运行得更快,你可以查看正在运行的更大的一组函数,并提出使其加速的策略。

最后,加速的最好办法是完全不做。如果你正在对相同条件进行多重检查,请找到避免多次检查的方法。如果你反复计算数据库中的同一列,请执行一次。如果你在密集的循环中调用函数,但数据不怎么改变,请缓存它或者事先计算出来。在许多情况下,你可以通过简单地事先计算一些东西,并一次性存储它们,来用空间换时间。

在下一个练习中,我们将会使用这个过程,来改进这些算法的性能。

挑战练习

此练习的挑战是,将我对bubble_sortmerge_sort所做的所有操作,都应用到目前为止所创建的所有数据结构和算法。我不期望你改进他们,但只是在开发测试来显示性能问题时,记下笔记并分析性能。抵制现在修改任何东西的诱惑,因为我们将在练习 19 中提高性能。

研究性学习

  • 到目前为止,对所有代码运行这些分析工具,并分析性能。
  • 将结果与算法和数据结构的理论结果进行比较。

破坏它

尝试编写使数据结构崩溃的病态测试。你可能需要为他们提供大量数据,但使用性能分析的信息来确保正确。

深入学习

  • 查看line_profiler,它是另一个性能测量工具。它的优点是,你只能衡量你关心的函数,但缺点是你必须更改源代码。
  • pyprof2calltreeKCacheGrind是更先进的工具,但老实说只能在 Linux 上工作。在视频中,我演示在 Linux 下使用它们。

评论 ( 0 )

你可以在登录后,对此项目发表评论

4_float_left_people 4_float_left_close