作者：多格里奥（Fernando Doglio）
出版社：人民邮电出版社
格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT
Python性能分析与优化试读：
前言
Packt出版社的朋友们让我产生了写作本书的想法。他们希望有人可以深入探讨Python高性能这个错综复杂的问题，介绍与之相关的所有话题，包括代码性能分析、现有的性能分析工具（比如性能分析器和其他性能增强技术），甚至包括标准Python实现的其他版本。
因此，欢迎你阅读本书。在本书中，我们将介绍与程序性能优化有关的一切。与性能优化这个主题相关的知识并不是阅读本书的必要前提（当然了解也没有坏处），但是关于Python编程语言的知识是必需的，尤其是对于一些专门优化Python代码的章节而言。
我们首先将会介绍什么是性能分析，性能分析如何在项目开发周期中发挥作用，以及通过在项目中进行性能分析实践能够取得的效果。紧接着将介绍分析性能所需的核心工具（性能分析器和可视化性能分析器）。然后会讨论一系列性能优化技术，最后一章会介绍一个具有实际意义的优化示例。本书内容
第1章，性能分析基础，为没有关注过性能分析艺术的人们介绍相关的基础知识。
第2章，性能分析器，介绍如何使用贯穿全书的核心分析工具。
第3章，可视化——利用GUI理解性能分析数据，介绍如何使用KCacheGrind/pyprof2calltree和RunSnakeRun工具，并且通过不同的可视化技术帮助开发者理解cProfile的输出结果。
第4章，优化每一个细节，介绍性能优化的基本过程和一系列值得推荐的好习惯，每个Python开发者在尝试其他优化手段之前都应该优先采用这些做法。
第5章，多线程与多进程，介绍多线程和多进程，并论述二者的使用方法和适用场景。
第6章，常用的优化方法，介绍如何安装和使用Cython和PyPy，优化代码性能。
第7章，用Numba、Parakeet和pandas实现极速数据处理，介绍针对处理数据的Python脚本的性能优化工具。这些专用工具（Numba、Parakeet和pandas）可以提升数据处理效率。
第8章，付诸实践，提供一个性能分析的实际示例，探索性能瓶颈，并通过书中介绍过的工具和技术消除瓶颈。总之，我们将会利用每项技术对比结果。本书需要的工具
在运行本书中的代码之前，你的操作系统中必须安装以下工具：● Python 2.7● line_profiler 1.0b2● KCacheGrind 0.7.4● RunSnakeRun 2.0.4● Numba 0.17● 最新版本的Parakeet● pandas 0.15.2目标读者
由于本书涵盖了Python代码性能分析和优化的方方面面，所以不同水平的Python开发者都能从中受益。
唯一的要求是读者要具备Python编程语言的一些基础知识。排版约定
本书中用不同的文本样式来区分不同种类的信息。下面给出了这些文本样式的示例及其含义。
正文中的代码和用户输入会这样显示：“我们可以打印/收集PROFILER函数里我们觉得有意义的内容。”
代码块示例如下：import sysdef profiler(frame, event, arg): print 'PROFILER: %r %r' % (event, arg)sys.setprofile(profiler)
当我们希望你注意代码块中的某些部分时，相关的行或者文字会被加粗：Traceback (most recent call last): File "cprof-test1.py", line 7, in
命令行输入或输出将会这样表示：$ sudo apt-get install python-dev libxml2-dev libxslt-dev
新术语和重点词汇均采用楷体字表示。 这个图标表示警告或需要特别注意的内容。 这个图标表示提示或者技巧。读者反馈
我们非常欢迎读者的反馈。如果你对本书有些想法，有什么喜欢或是不喜欢的，请反馈给我们。这将有助于我们开发出能够充分满足读者需求的图书。
一般的反馈，请发送电子邮件至feedback@packtpub.com，并在邮件主题中注明书名。
如果你在某个领域有专长，并有意编写一本书或是贡献一份力量，请参考我们的作者指南，地址为http://www.packtpub.com/authors。客户支持
你现在已经是Packt引以为傲的读者了，为了能让你的购买物有所值，我们还为你准备了以下内容。下载示例代码
你可以用你的账户从http://www.packtpub.com下载所有已购买Packt图书的示例代码文件。如果你从其他地方购买本书，可以访问http://www.packtpub.com/support并注册，我们将通过电子邮件把文件发送给你。下载本书的彩色图像
我们也提供了本书的PDF文件，里面包含了本书的截屏和流程图等彩色图片。彩色图片将能帮助你更好地理解输出的变化。你可以通过https://www.packtpub.com/sites/default/files/downloads/9300OS_GraphicBundle.pdf下载。勘误
虽然我们已尽力确保本书内容正确，但出错仍旧在所难免。如果你在我们的书中发现错误，不管是文本还是代码，希望能告知我们，我们不胜感激。这样做，你可以使其他读者免受挫败，帮助我们改进本书的后续版本。如果你发现任何错误，请访问http://www.packtpub.com/submit-errata提交，选择你的书，点击勘误表提交表单的链接，并输入详细说明。勘误一经核实，你的提交将被接受，此勘误将上传到本公司网站或添加到现有勘误表。从http://www.packtpub.com/support选择书名就可以查看现有的勘误表。侵权行为
版权材料在互联网上的盗版是所有媒体都要面对的问题。Packt非常重视保护版权和许可证。如果你发现我们的作品在互联网上被非法复制，不管以什么形式，都请立即为我们提供位置地址或网站名称，以便我们可以寻求补救。
请把可疑盗版材料的链接发到copyright@packtpub.com。
非常感谢你帮助我们保护作者，以及保护我们给你带来有价值内容的能力。问题
如果你对本书内容存有疑问，不管是哪个方面，都可以通过questions@packtpub.com联系我们，我们将尽最大努力来解决。电子书
扫描如下二维码，即可获得本书电子版。致谢
我想感谢我挚爱的妻子忍受我花这么长时间来写这本书，如果没有她的支持，我不可能完成这本书。我也想感谢我的两个儿子，没有他们，这本书就不会提前数月完成。
最后，我想感谢所有审稿人和编辑们。他们帮助我使本书成形，并且达到了较高的质量水平。第1章性能分析基础
就像在12秒内跑完100米障碍跑的人在婴儿时期需要先学爬一样，程序员在精通性能分析（profiling）之前需要先了解一些基础知识。因此，在我们探索Python程序的性能优化与分析技术之前，需要对相关的基础知识有一个清晰的认识。
只要你掌握了这些基础知识，就可以进一步学习具体的工具和技术。因此，这一章将介绍所有你平时羞于开口问人却又应该掌握的性能分析知识。本章的具体内容如下。● 介绍性能分析的明确定义，概述各种性能分析技术。● 论述性能分析在开发周期中的重要作用，因为性能分析不是
那种只做一次就抛到脑后的事情。性能分析应该是开发过程中一
个完整的组成部分，就像写测试一样。● 介绍哪些东西适合进行性能分析。看看我们可以度量哪些资
源，以及这些度量如何帮助我们发现性能瓶颈。● 分析过早优化的风险，即解释为什么未经性能分析便对代码
进行优化通常不是一种好做法。● 学习关于程序运行时间复杂性的知识。虽然理解性能分析技
术是成功优化程序的一个步骤，但我们也需要理解算法复杂性的
度量指标，这样才能够明白是否有必要优化算法。● 一些好的做法。本章最后将介绍一些对项目进行性能分析时
需要记住的好习惯。1.1 什么是性能分析
没有优化过的程序通常会在某些子程序（subroutine）上消耗大部分的CPU指令周期（CPU cycle）。性能分析就是分析代码和它正在使用的资源之间有着怎样的关系。例如，性能分析可以告诉你一个指令占用了多少CPU时间，或者整个程序消耗了多少内存。性能分析是通过使用一种被称为性能分析器（profiler）的工具，对程序或者二进制可执行文件（如果可以拿到）的源代码进行调整来完成的。
通常，当需要优化程序性能，或者程序遇到了一些奇怪的bug时（一般与内存泄漏有关），开发者会对他们的程序进行性能分析。这时，性能分析可以帮助开发者深刻地了解程序是如何使用计算机资源的（即可以细致到一个函数被调用了多少次）。
根据这些信息，以及对源代码的深刻认知，开发者就可以找到程序的性能瓶颈或者内存泄漏所在，然后修复错误的代码。
性能分析软件有两类方法论：基于事件的性能分析（event-based profiling）和统计式性能分析（statistical profiling）。在使用这两类软件时，应该牢记它们各自的优缺点。1.1.1 基于事件的性能分析
不是所有的编程语言都支持这类性能分析。支持这类基于事件的性能分析的编程语言主要有以下几种。● Java：JVMTI（JVM Tools Interface，JVM工具接口）为性
能分析器提供了钩子，可以跟踪诸如函数调用、线程相关的事件、
类加载之类的事件。● .NET：和Java一样，.NET运行时提供了事件跟踪功能（https://en.wikibooks.org/wiki/
Introduction_to_Software_Engineering/Testing/
Profiling#Methods_of_data_gathering）。● Python： 开发者可以用sys.setprofile函数，跟踪python_[call|
return|exception]或c_[call|return|exception]之类的事件。
基于事件的性能分析器（event-based profiler，也称为轨迹性能分析器，tracing profiler）是通过收集程序执行过程中的具体事件进行工作的。这些性能分析器会产生大量的数据。基本上，它们需要监听的事件越多，产生的数据量就越大。这导致它们不太实用，在开始对程序进行性能分析时也不是首选。但是，当其他性能分析方法不够用或者不够精确时，它们可以作为最后的选择。如果你想分析程序中所有返回语句的性能，那么这类性能分析器就可以为你提供完成任务应该有的颗粒度，而其他性能分析器都不能为你提供如此细致的结果。
一个Python基于事件的性能分析器的简单示例代码如下所示（当学完后面的章节时，你对这个主题的理解将会更加深刻）：import profileimport sysdef profiler(frame, event, arg): print 'PROFILER: %r %r' % (event, arg)sys.setprofile(profiler)# 计算斐波那契数列的简单（也是非常低效的）示例def fib(n): if n == 0: return 0 elif n == 1: return 1 else: return fib(n-1) + fib(n-2)def fib_seq(n): seq = [ ] if n > 0: seq.extend(fib_seq(n-1)) seq.append(fib(n)) return seqprint fib_seq(2)
上面程序的输出结果如下所示：PROFILER: 'call' NonePROFILER: 'call' NonePROFILER: 'call' NonePROFILER: 'call' NonePROFILER: 'return' 0PROFILER: 'c_call'
你会发现，PROFILER会被每一个事件调用。我们可以打印/收集PROFILER函数里我们觉得有意义的内容。在上面的简单示例代码中，最后一行表示执行fib_seq(2)生成一组数值。如果我们处理一个实际点儿的程序，性能分析输出的结果可能要比上述结果大好几个数量级。这就是基于事件的性能分析软件通常作为性能分析的最后选择的原因。虽然其他性能分析软件（马上就会看到）产生的结果会少很多，但是分析的精确程度也要低一些。1.1.2 统计式性能分析
统计式性能分析器以固定的时间间隔对程序计数器（program counter）进行抽样统计。这样做可以让开发者掌握目标程序在每个函数上消耗的时间。由于它对程序计数器进行抽样，所以数据结果是对真实值的统计近似。不过，这类软件足以窥见被分析程序的性能细节，查出性能瓶颈之所在。
这类性能分析软件的优点如下所示。● 分析的数据更少：由于我们只对程序执行过程进行抽样，而
不用保留每一条数据，因此需要分析的信息量会显著减少。● 对性能造成的影响更小：由于使用抽样的方式（用操作系统
中断），目标程序的性能遭受的干扰更小。虽然使用性能分析器
并不能做到100%无干扰，但是统计式性能分析器比基于事件的
性能分析器造成的干扰要小。
下面是一个Linux统计式性能分析器OProfile（http://oprofile.sourceforge.net/news/）的分析结果：Function name,File name,Times Encountered,Percentage"func80000","statistical_profiling.c",30760,48.96%"func40000","statistical_profiling.c",17515,27.88%"func20000","static_functions.c",7141,11.37%"func10000","static_functions.c",3572,5.69%"func5000","static_functions.c",1787,2.84%"func2000","static_functions.c",768,1.22%"func1500","statistical_profiling.c",701,1.12%"func1000","static_functions.c",385,0.61%"func500","statistical_profiling.c",194,0.31%
下面的性能分析结果，是通过Python的统计式性能分析器statprof对前面的代码进行分析得出的：% cumulative selftime seconds seconds name100.00 0.01 0.01 B02088_01_03.py:11:fib 0.00 0.01 0.00 B02088_01_03.py:17:fib_seq 0.00 0.01 0.00 B02088_01_03.py:21:
你会发现，两个性能分析器对同样代码的分析结果差异非常大。1.2 性能分析的重要性
现在我们已经知道了性能分析的涵义，还应该理解在产品开发周期中进行性能分析的重要性和实际意义。
性能分析并不是每个程序都要做的事情，尤其对于那些小软件来说，是没多大必要的（不像那些杀手级嵌入式软件或专门用于演示的性能分析程序）。性能分析需要花时间，而且只有在程序中发现了错误的时候才有用。但是，仍然可以在此之前进行性能分析，捕获潜在的bug，这样可以节省后期的程序调试时间。
在硬件变得越来越先进、越来越快速且越来越便宜的今天，开发者自然也越来越难以理解，为什么我们还要消耗资源（主要是时间）去对开发的产品进行性能分析。毕竟，我们已经拥有测试驱动开发、代码审查、结对编程，以及其他让代码更加可靠且符合预期的手段。难道不是吗？
然而，我们没有意识到的是，随着我们使用的编程语言越来越高级（几年间我们就从汇编语言进化到了JavaScript），我们愈加不关心CPU循环周期、内存配置、CPU寄存器等底层细节了。新一代程序员都通过高级语言学习编程技术，因为它们更容易理解而且开箱即用。但它们依然是对硬件和与硬件交互行为的抽象。随着这种趋势的增长，新的开发者越来越不会将性能分析作为软件开发中的一个步骤了。
让我们看看下面这种情景。
我们已经知道，性能分析是用来测量程序所使用的资源的。前面已经说过，资源正变得越来越便宜。因此，生产软件并让更多的客户使用我们的软件，其成本变得越来越低。
如今，随便开发一个软件就可以获得上千用户。如果通过社交网络一推广，用户可能马上就会呈指数级增长。一旦用户量激增，程序通常会崩溃，或者变得异常缓慢，最终被客户无情抛弃。
上面这种情况，显然可能是由于糟糕的软件设计和缺乏扩展性的架构造成的。毕竟，一台服务器有限的内存和CPU资源也可能会成为软件的瓶颈。但是，另一种可能的原因，也是被证明过许多次的原因，就是我们的程序没有做过压力测试。我们没有考虑过资源消耗情况；我们只保证了测试已经通过，而且乐此不疲。也就是说，我们目光短浅，结果就是项目崩溃夭折。
性能分析可以帮助我们避免项目崩溃夭折，因为它可以相当准确地为我们展示程序运行的情况，不论负载情况如何。因此，如果在负载非常低的情况下，通过性能分析发现软件在I/O操作上消耗了80%的时间，那么这就给了我们一个提示。有人可能觉得，在测试阶段程序运行很正常，在负载很重的情况下也应该不会有问题。想想内存泄漏的情况吧。在这种情况下，小测试是不会发现大负载里出现的bug的。但是，产品负载过重时，内存泄漏就会发生。性能分析可以在负载真的过重之前，为我们提供足够的证据来发现这类隐患。1.3 性能分析可以分析什么
要想深入地理解性能分析，很重要的一点是明白性能分析方法究竟能够分析什么指标。因为测量是性能分析的核心，所以让我们仔细看看程序运行时可以测量的指标。1.3.1 运行时间
做性能分析时，我们能够收集到的最基本的数值就是运行时间。整个进程或代码中某个片段的运行时间会暴露相应的性能。如果你对运行的程序有一些经验（比如说你是一个网络开发者，正在使用一个网络框架），可能很清楚运行时间是不是太长。例如，一个简单的网络服务器查询数据库、响应结果、反馈到客户端，一共需要100毫秒。但是，如果程序运行得很慢，做同样的事情需要花费60秒，你就得考虑做性能分析了。你还需要考虑不同场景的可比性。再考虑另一个进程：一个MapReduce任务把2TB数据存储到文件中要消耗20分钟，这时你可能不会认为进程很慢了，即使它比之前的网络服务器处理时间要长很多。
为了获得运行时间，你不需要拥有大量性能分析经验和一堆复杂的分析工具。你只需要把几行代码加入程序运行就可以了。
例如，下面的代码会计算斐波那契数列的前30位：import datetimetstart = Nonetend = Nonedef start_time(): global tstart tstart = datetime.datetime.now()def get_delta(): global tstart tend = datetime.datetime.now() return tend - tstartdef fib(n): return n if n == 0 or n == 1 else fib(n-1) + fib(n-2)def fib_seq(n): seq = [] if n > 0: seq.extend(fib_seq(n-1)) seq.append(fib(n)) return seqstart_time()print "About to calculate the fibonacci sequence for the number 30"delta1 = get_delta()start_time()seq = fib_seq(30)delta2 = get_delta()print "Now we print the numbers: "start_time()for n in seq: print ndelta3 = get_delta()print "====== Profiling results ======="print "Time required to print a simple message: %(delta1)s" % locals()print "Time required to calculate fibonacci: %(delta2)s" % locals()print "Time required to iterate and print the numbers: %(delta3)s" % locals()print "====== ======="
程序的输出结果如下所示：About to calculate the Fibonacci sequence for the number 30Now we print the numbers:01123581321#……省略一些数字418167651094617711286574636875025121393196418317811514229832040====== Profiling results =======Time required to print a simple message: 0:00:00.000030Time required to calculate fibonacci: 0:00:00.642092Time required to iterate and print the numbers: 0:00:00.000102
通过最后三行结果，我们会发现，代码中最费时的部分就是斐波那契数列的计算。下载源代码你可以用自己的账户登录http://www.packtpub.com，下载你购买过的Packt出版社的所有图书的示例代码。如果你是在其他地方购买的Packt出版社的书籍，可以通过http://www.packtpub.com/support注册账户，然后要求Packt把示例代码通过邮件发给你。1.3.2 瓶颈在哪里
只要你测量出了程序的运行时间，就可以把注意力移到运行慢的环节上做性能分析。通常，瓶颈都是由下面的一种或几种原因造成的。● 沉重的I/O操作，比如读取和分析大文件，长时间执行数据
库查询，调用外部服务（比如HTTP请求），等等。● 出现了内存泄漏，消耗了所有的内存，导致后面的程序没有
内存来正常执行。● 未经优化的代码被频繁地执行。● 密集的操作在可以缓存时没有缓存，占用了大量资源。
I/O关联的代码（文件读/写、数据库查询等）很难优化，因为优化有可能会改变程序执行I/O操作的方式（通常是语言的核心函数操作I/O）。相反，优化计算关联的代码（比如程序使用的算法很糟糕），改善性能会比较容易（并不一定很简单）。这是因为优化计算关联的代码就是改写程序。
在性能优化接近尾声的时候，剩下的大多数性能瓶颈都是由I/O关联的代码造成的。1.4 内存消耗和内存泄漏
软件开发过程中需要考虑的另一个重要资源是内存。一般的软件开发者不会意识到这一点，因为640KB RAM电脑的时代早已成为过去。但是一个内存泄漏的程序会把服务器糟蹋成640KB电脑。内存消耗不仅仅是关注程序使用了多少内存，还应该考虑控制程序使用内存的数量。
有一些开发项目，比如嵌入式系统开发，就会要求开发者关注内存配置，因为这类系统的资源是相当有限的。但是，普通开发者总希望目标系统能够提供他们需要的RAM。
随着RAM和高级编程语言都开始支持自动内存管理（比如垃圾回收机制），开发者不需要关注内存优化了，系统会帮忙完成的。
跟踪程序内存的消耗情况比较简单。最基本的方法就是使用操作系统的任务管理器。它会显示很多信息，包括程序占用的内存数量或者占用总内存的百分比。任务管理器也是检查CPU时间使用情况的好工具。在下面的截图中，你会发现一个简单的Python程序（就是前面那段程序）几乎占用了全部CPU（99.8%），内存只用了0.1%。
用这样的工具（Linux系统在命令行用top命令），可以轻松检测内存泄漏问题，不过这也要根据程序的具体情况综合考虑。如果你的程序在持续加载数据，那么其内存消耗的比例，可能会与那些没有频繁使用外部资源的程序不同。
例如，如果我们把一个调用大量外部资源的程序的内存消耗随时间的变化描绘出来，可能如下图所示。
资源加载时，内存使用曲线出现高峰；资源释放时，曲线会下降。虽然程序的内存消耗变化有点儿大，但是我们可以统计没有加载资源时程序的内存消耗的平均值。只要确定了这个平均值（图中用矩形表示），就可以判断内存泄漏的情况。
让我们再看一个资源加载效果比较糟糕的程序的内存消耗图（没有完全释放资源）。
在上图中你会发现，每当资源不再使用时，占用的内存并没有完全释放，这时内存消耗曲线就会位于矩形之上。这就表示程序会消耗越来越多的内存，即使加载资源已经释放也是如此。
同理，也可以检测那些没有负载的程序的内存消耗情况，把执行特定任务的程序运行一段时间。有了数据，就很容易检测内存消耗和内存泄漏情况了。
让我们来看一个例子：
当运行过程启动之后，内存消耗会在一个范围内不断增加。如果发现增幅超出范围，而且消耗增大之后一直没有回落，就可以判断出现内存泄漏了。
一个内存泄漏的例子如下图所示。1.5 过早优化的风险
优化通常被认为是一个好习惯。但是，如果一味优化反而违背了软件的设计原则就不好了。在开始开发一个新软件时，开发者经常犯的错误就是过早优化（permature optimization）。
如果过早优化代码，结果可能会和原来的代码截然不同。它可能只是完整解决方案的一部分，还可能包含因优化驱动的设计决策而导致的错误。
一条经验法则是，如果你还没有对代码做过测量（性能分析），优化往往不是个好主意。首先，应该集中精力完成代码，然后通过性能分析发现真正的性能瓶颈，最后对代码进行优化。1.6 运行时间复杂度
在进行性能分析和优化时，理解运行时间复杂度（Running Time Complexity，RTC）的知识，以及学习使用它们适当地优化代码十分重要。
RTC可以用来对算法的运行时间进行量化。它是对算法在一定数量输入条件下的运行时间进行数学近似的结果。因为是数学近似，所以我们可以用这些数值对算法进行分类。
RTC常用的表示方法是大O标记（big O notation）。数学上，大O标记用于表示包含无限项的函数的有限特征（类似于泰勒展开式）。如果把这个概念用于计算机科学，就可以把算法的运行时间描述成渐进的有限特征（数量级）。
也就是说，这种标记通过宽泛的估计，让我们了解算法在任意数量输入下的运行时间。但是它不能提供精确的时间值，需要对代码进行深入的分析才能获得。
前面说过，用这种标记方法可以对算法进行分类，下面就是常用的算法类型。1.6.1 常数时间——O(1)
常数时间（constant time）是最简单的算法复杂度类型。这基本上表示我们的测量结果将是恒定值，算法运行时间不会随着输入的增加而增加。
运行时间为O(1)的代码示例如下所示。● 判断一个数是奇数还是偶数：if number % 2: odd = Trueelse: odd = False● 用标准输出方式打印信息：print "Hello world!"
对于理论上更复杂的操作，比如在字典（或哈希表）中查找一个键的值，如果算法合理，就可以在常数时间内完成。技术上看，在哈希表中查找元素的消耗时间是O(1)平均时间，这意味着每次操作的平均时间（不考虑特殊情况）是固定值O(1)。1.6.2 线性时间——O(n)
线性时间复杂度表示，在任意 n 个输入下，算法的运行时间与 n 呈线性关系，例如，3n，4n+5，等等。
如上图所示，当 x 轴无线延伸时，蓝线（3n）和红线（4n+5）会和黑线（n）达到同样的上限。因此，为了简化，我们把这些算法都看成O(n)类。
这种数量级（order）的算法案例有：● 查找无序列表中的最小元素● 比较两个字符串● 删除链表中的最后一项1.6.3 对数时间——O(logn)
对数时间（logarithmic time）复杂度的算法，表示随着输入数量的增加，算法的运行时间会达到固定的上限。随着输入数量的增加，对数函数开始增长很快，然后慢慢减速。它不会停止增长，但是越往后增长的速度越慢，甚至可以忽略不计。
上图显示了三种不同的对数函数。你会看到三条线都是同样的形状，随着x的增大，都是无限增加的。
对数时间的算法示例如下所示：● 二分查找（binary search）● 计算斐波那契数列（用矩阵乘法）1.6.4 线性对数时间——O(n logn)
把前面两种时间类型组合起来就变成了线性对数时间（linearithmic time）。随着 x 的增大，算法的运行时间会快速增长。
这类算法的示例如下所示：● 归并排序（merge sort）● 堆排序（heap sort）● 快速排序（quick sort，至少是平均运行时间）
下图中的线性对数函数曲线可以让我们更好地理解这类算法。1.6.5 阶乘时间——O(n!)
阶乘时间（factorial time）复杂度的算法是最差的算法。其时间增速特别快，图都很难画。
下图是对阶乘函数的近似描述，可以看成这类算法的运行时间。
阶乘时间复杂度的一个示例，就是用暴力破解搜索方法解货郎担问题（遍历所有可能的路径）。21.6.6 平方时间——O(n)
平方时间是另一个快速增长的时间复杂度。输入数量越多，需要消耗的时间越长（大多数算法都是这样，这类算法尤其如此）。平方时间复杂度的运行效率比线性时间复杂度要慢。
这类算法的示例如下：● 冒泡排序（bubble sort）● 遍历二维数组● 插入排序（insertion sort）
这类函数的曲线图如下所示：
最后，我们把所有算法运行时间复杂度放在一张图上，比较一下运行效率：
不考虑常数时间复杂度（虽然它是最快的，但是显然复杂算法都不可能达到这个速度），那么时间复杂度排序如下所示：● 对数● 线性● 线性对数● 平方● 阶乘
有时候，你可能也没办法，只能选择平方时间复杂度作为最佳解决方案。理论上我们总是希望实现更快速的算法，但是问题和技术的限制往往会影响结果。
注意，平方时间类型与阶乘时间类型之间，有一些变体，如三次方时间类型、四次方时间类型等。
还有很重要的一点需要考虑，就是算法的时间复杂度往往不止一种类型，可能是三种类型，包括最好情况、正常情况和最差情况。三种情况是由输入条件的不同属性决定的。例如，如果结果已经排序，插入排序算法的运行速度会比较快（最好情况），其他情况则要更慢一些（指数复杂度）。
另外数据类型也会影响时间复杂度。算法运行时间复杂度也与实际的操作方式有关（索引、插入、搜索等）。常见的数据类型和操作的时间复杂度如下所示。数据结构时间复杂度正常情况最差情况索引查找插入删除索查插删引找入除O(O(----O(1)O(n)列表（list）1)n)O(O(O(O(O(n)O(n)O(1)O(1)单向链表（linked list）n)n)1)n)O(O(O(O(双向链表（doubly linked O(n)O(n)O(1)O(1)n)n)1)1)list）O(O(O(-O(1)O(1)O(1)-字典（dictionary）n)n)n)O(loO(loO(loO(loO(O(O(O(二分查找树（Binary g(n))g(n))g(n))g(n))n)n)n)n)Search Tree，BST）1.7 性能分析最佳实践
性能分析是重复性的工作。为了获得最佳性能，你可能需要在一个项目中做很多次性能分析，在另一个项目里还要再做一次。和软件开发中的其他重复性任务一样，有许多最佳实践可以帮助你高效地完成大多数性能分析工作。让我们来具体看看。1.7.1 建立回归测试套件
在进行性能优化时，需要保证不管代码怎么变化，功能都不会变糟。最好的做法，尤其是面对大型项目时，就是建立测试套件。确保代码具有足够的覆盖率，可以让你信心去优化。覆盖率只有60%的测试套件在优化时可能会导致严重后果。
回归测试套件可以保证你在代码中尝试任何优化时，都不用担心代码的结构被破坏。1.7.2 思考代码结构
函数代码之所以容易进行重构（refactor），是因为这种代码结构没有副作用。这样可以降低改变系统中其他部分的风险。如果你的代码没有局部可变的状态，将是另一个优势。这是因为，代码应该很容易理解和改变。没有按照前面的规则编写的代码，在重构过程中可能都需要额外的工作和注意。1.7.3 耐心
性能分析不是一个快速、简单、精确的过程。也就是说，你不能指望运行一下性能分线器就可以把问题找到。有时候也许可以这样。但是，大多数情况下，你遇到的问题都不是很容易解决的。这就表明你必须浏览数据，描绘图形以便理解，不断地缩小检测范围，直到你重新开启新一轮分析，或者最终找到问题所在。
值得注意的是，对数据分析得越深入，表明你陷入的坑越深，数据将无法指明正确的优化方向，因此要时刻清楚自己的目标，并且在你开始之前已准备好正确的工具。然而，也可能搞了半天除了备受挫折，什么进展也没有。1.7.4 尽可能多地收集数据
根据软件的不同类型和规模，在分析之前，你可能需要获取尽量多的数据。性能分析器很适合做这件事。但是，还有其他数据资源，如网络应用的系统日志、自定义日志、系统资源快照（如操作系统任务管理器），等等。1.7.5 数据预处理
当你拥有了性能分析器的信息、日志和其他资源之后，在分析之前可能需要对数据进行预处理。不要因为性能分析器不能理解就回避非结构化数据。数据分析会往往从其他数据中受益。
例如，如果分析网络应用的性能，获取网络服务器日志是个不错的主意，但是这些日志文件就是一行一个请求。解析文件并把数据存入数据库系统（像MongoDB、MySQL等），你就可以为数据确定含义（解析日期数据，通过IP获溯源地理位置等），并在后面进行查询。
前面这个过程称为ETL（extracting the data from it's sources, transforming it into something with meaning, and loading it into another system），表示从源抽取数据，根据数据含义转换形式，并加载到其他系统中使用。1.7.6 数据可视化
如果在错误发生之前，你不清楚自己要找的问题，只是想知道优化代码的方式，那么洞察你已经预处理过的数据的最好方式就是数据可视化。计算机很擅长处理数据，但是人类擅于通过图像来发现模式和理解现有信息中的某种特征。
例如，继续前面的网络服务器日志示例，一个简单的请求时间图（比如在微软的Excel中绘制）就可以显示客户行为的某种特征：
上图很清晰地显示出客户访问集中在下午晚些时候，并持续到深夜。后面你可以进一步针对这个特征进行性能分析。例如，针对这种现象的优化方案，可能就是在高峰期为基础设施增加更多资源（像亚马逊的AWS可以满足这类需求）。
另一个例子是用自定义性能分析数据可以画出下图：
上图是对本章第一个代码示例的性能分析结果中那些触发profile函数的事件进行数量统计。我们可以把它画成饼图，直观地看出数量最多的事件。可以看出，调用call和return占用了程序运行的绝大多数时间。1.8 小结
在这一章，我们介绍了性能分析的基础知识，理解了性能分析方法及其重要性，并学会了如何使用它分析大多数代码的性能。
下一章我们将动手试试Python的性能分析器，看看它们是如何对应用进行性能分析的。性能分析器
上一章介绍了性能分析的基础知识，展示了性能分析的重要性。如果把性能分析方法整合到开发过程中，就可以帮助我们提高产品的开发质量。另外，上一章还介绍了一些性能分析的具体方法。
上一章在最后介绍了程序运行时间复杂度的相关理论。在这一章，我们将会用到第一部分（关于性能分析的内容）。之后，我们将通过两个Python性能分析器（cProfile和line_profiler），把学到的理论付诸实践。
本章将介绍以下内容：● 性能分析器的基本信息● 性能分析器的下载和安装方法● 通过示例演示性能分析器的功能● 比较两种性能分析器的差异2.1 认识新朋友：性能分析器
学完上一章所有的理论和简单示例之后，我们应该看看真正的Python了。我们先来看看目前最受关注也是用户最多的两个Python性能分析器：cProfile和line_profiler。两者将通过不同的方式帮助我们分析代码的性能。
cProfile（https://docs.python.org/2/library/profile.html#module-cProfile）从Python 2.5开始就是该语言默认的性能分析器，官方推荐在绝大多数场景中使用。而line_profiler（https://github.com/rkern/line_profiler）虽然不是Python官方发布的性能分析器，但是也被广泛使用。
下面详细地介绍两种性能分析器的相关知识。2.2 cProfile
就像之前提到的，cProfile自Python 2.5以来就是标准版Python解释器默认的性能分析器。其他版本的Python，比如PyPy里面是没有cProfile的。它是一种确定性的性能分析器，提供了一组API帮助开发者收集Python程序运行的信息，更确切地说，是统计每个函数消耗的CPU时间。同时它还提供了其他细节，比如函数被调用的次数。
cProfile只测量CPU时间，并不关心内存消耗和其他与内存相关的信息统计。尽管如此，它是代码优化过程中一个很不错的起点，因为大多数时候，这个分析工具都会快速地为我们提供一组优化方案。
cProfile不需要安装，因为它是语言自带的一部分。要使用它，直接导入cProfile包即可。
确定性的性能分析器其实就是基于事件的性能分析器的另一种说法（更多细节请参考上一章内容）。也就是说，这个性能分析器会关注代码运行过程中的函数调用、返回语句等事件，甚至可以测量程序运行期间发生的每一个事件（与我们在上一章看到的统计式性能分析器不同）。
下面是从Python文档里提取出来的一个非常简单的例子：import cProfileimport recProfile.run('re.compile("foo|bar")')
上面代码的输出结果如下： 197 function calls (192 primitive calls) in 0.002 secondsOrdered by: standard namencalls tottime percall cumtime percall filename:lineno(function) 1 0.000 0.000 0.001 0.001
从这个结果中可以收集到如下信息。● 第一行告诉我们一共有197个函数调用被监控，其中192个
是原生（primitive）调用，表明这些调用不涉及递归。● ncalls表示函数调用的次数。如果在这一列中有两个数值，
就表示有递归调用。第二个数值是原生调用的次数，第一个数值
是总调用次数。这个数值可以帮助识别潜在的bug（当数值大得
试读结束[说明：试读内容隐藏了图片]