私信发送成功
Watch Star Fork

龙哥盟飞龙 / lmpythw-zh

克隆/下载
一键复制 编辑 原始数据 按行查看 历史
ex19.md 7.03 KB wizardforcel 提交于 2017-08-09 15:07 . fix ex19

练习 19:改善性能

原文:Exercise 19: Improving Performance

译者:飞龙

协议:CC BY-NC-SA 4.0

自豪地采用谷歌翻译

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

  • 循环内的循环的重复计算可以避免。冒泡排序是经典案例,这就是我教它的原因。,一旦你看到,冒泡排序与其他方法相比有多糟糕,你将开始认识到这是一个需要避免的常见模式。
  • 重复计算一些没有实际变化的东西,或者在更改过程中可以计算一次。在sorted.py和其他数据结构中的count()函数是一个很好的例子。你可以在函数内跟踪数据结构的大小。每次添加时,你可以增加它,并且每次删除时,减少它。每次都不需要遍历整个列表。你还可以使用这个预先计算的计数,通过检查count == 0来改进其他功能的逻辑。
  • 使用错误的数据结构。在字典中,我使用DoubleLinkedList来演示这个问题。字典需要随机访问元素,至少是桶的列表中的元素。使用DoubleLinkedListDoubleLinkedList意味着每次你想访问第 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,因为每个人都相信“专业密码学家”创建了代码。原来,即使是所谓的专业密码学家也可以写出糟糕的代码。使新的算法正确需要特殊技能,并且我认为 -- 使用定理证明工具来验证正确性。除非你有这样的背景,创造新的算法和数据结构可能会产生危险。这包括加密算法和加密网络协议。只要你掌握实现技能,实现其他人已经证明的算法完全正常,运行良好。但是不要在没有一些帮助的情况下制作自己的头发数据结构。实现其他人已经证明的算法完全没问题,并且是个好的练习。但是不要在没有一些帮助的情况下制作自己的粗制滥造的数据结构。

评论 ( 0 )

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

4_float_left_people 4_float_left_close