猛踩油门！令Python加速

先要能做，做得对，最后才是要做得快。

——Kent Beck

这篇附录将致力于提供一些优化代码的工具，以便能使我们的代码变得更简洁，或者更快速。尽管此类优化在大多数情况下并不能代替算法设计（特别是当我们所处理的问题规模非常大的时候），但是让我们的程序运行快上10倍应该还是能做到的。

在调用外部辅助之前，我们应该首先审视一下自己是否已经做到Python的内置工具物尽其用了。在本书中，我曾列举过许多类似的例子，其中包括了适用于双向队列的deque，以及如何在合适的条件下运用bisect和heapq来提升算法的性能。另外，作为一个Python 程序员，我们也很幸运Python提供了当今最高级也最为有效的排序算法（list.sort()，并且高效地实现了它），以及一个功能多样而又迅速的散列表（dict）。甚至您还会发现，itertools与functools模块中也能给我们带来某种程度的高性能代码1。

除此之外，当我们选择要用外部库来优化代码时，还应该先确认一下这种优化是否有必要。优化本身也往往会让我们的代码变得更复杂，依赖关系更多，所以优化之前要想一想，优化是否真的值得。如果您的算法已经“足够好”，代码也“足够快”，那么通常就不值得引入用其他语言（如C语言）撰写的外部模块了。当然，什么是“足够好”、“足够快”，也取决于我们自己的判断。（您可以在第2章找到一些用于代码测速与剖析的例子。）

需要注意的是，本篇附录中所讨论的包和外部扩展库主要用于优化单处理器的代码，其中既包括高效的函数实现，也包括封装好了的扩展模块，以及速度更快的Python解释器。当然，考虑将我们代码改为多处理器版本确实能有助于大幅提高运行效率，所以您真的想这么做的话，multiprocessing模块是一个好的开始。如果您希望深入了解多核编程，您同样可以找到非常多的关于分布式计算的第三方工具。例如，您可以查看一下Python wiki上Parallel Processing页面中的内容。

在接下来的内容中，我们将会看到一份加速工具的选单。其中包含了业界在若干个方向上的努力，应对于各种情境的变化，毕竟新项目会与时俱进，而一些旧项目则逐渐被淘汰。如果您对下面所介绍的工具方案很感兴趣，打算将其运用到自己的项目来，我们建议您可以先浏览一下这些扩展库的网站以及社区——当然，这要根据您自己的需要，本篇附录最后附有这些网站的地址（见表A-1）。

NumPy、SciPy、Sage与Pandas：NumPy是一个历史悠久的包。它起源于Numeric和numaray这些更为古老的项目。NumPy的核心是一个多维数字数组的实现。除了该数据结构外，它还实现了若干个函数与运算符，它们能够高效地进行数组运算，并且对函数被调用的次数进行了精简。您可以用它来进行极其高效的数学运算，而无需对内置模块进行任何额外的编译。SciPy和Sage则属于那种更为宏大的项目，它们将NumPy内置为自身的一部分，同时内置了几种不同的工具，实现了用于特定科学、数学及高性能计算的模块（关于这些内容，我们在后面的内容中还会提到）。Pandas是一个侧重于数据分析的工具，但只有等它的数据模块适用于我们的问题实例时，它才是一个强大而快捷的工具。另一个与之相关的工具叫Blaze，它在我们处理大量半结构化数据的时候是非常有用的。

PyPy、Pyston、Parakeet、Psyco与Unladen Swallow：让代码运行得更快，且侵入性最小的方式之一就是使用实时编译器（just-in-time (JIT) compiler）。在以前，我们可以用Python安装器来安装Psyco。安装完成之后，我们就只需要直接导入psyco模块，然后调用psyco.full()，代码的运行速度就会有明显的提升。在您运行Python程序时，Psyco会将我们的一部分代码编译为机器码。而由于它可以在运行时监控程序，因此也就可以做出某些静态编译器无法做到的优化。例如，一个Python list中可以包含任意类型的值，但当Psyco注意到该list其实只包含整型时，它就会假设，可能该list在之后的运行时间里也仅会包含整型，因而对相关代码进行编译，将该list编译为整型列表。遗憾的是，如今包括Psyco在内的数个类似的Python加速器项目以及它们的网站都已经处于“停止维护以及消亡”的状态了，尽管类似的功能在PyPy中得到了传承。

PyPy则是一个更为宏大的项目：它用Python语言重新将Python实现了一遍。当然，这本身不会直接加快运行速度，这么做主要是为便于代码的分析、优化与翻译。正是基于这个框架，JIT编译才变为了可能（这使得我们不再需要Psyco，代码在PyPy内就能完成编译）。甚至PyPy还能将代码翻译成像C那样的、性能更高的编程语言。另外，在PyPy中所实现的Python的核心子集被称为RPython（restricted Python），这部分已经有工具可以静态地编译成高效的机器码。

在某种程度上，Unladen Swallow也是一种Python的JIT编译器。或者更精确地说，它是Python解释器的一个版本，被称为底层虚拟机（Low Level Virtual machine，LLVM）。该项目的目标是将加速因子相对标准编译器提高至5。然而，Unladen Swallow项目还没有达到这个目标，但它的开发活动似乎已经停止了。

Pyston也是一个由Dropbox开发的、与LLVM平台较为接近的Python JIT编译器。在本书写作期间，Pyston还是一个非常年轻的项目，只支持了语言的一个子集，并且完全不支持Python 3。然而在很多情况下，它已经优于Python的标准实现，并且目前还在积极地开发中。此外，Parakeet也是一个相当年轻的项目，用该项目Web页面的话说，“其中包含了类型接口、并行数据的数组操作以及大量能使代码加速的黑魔法”。

GPULib、PyStream、PyCUDA与PyOpenCL：这四个包都是在用图像处理单元（graphics processing units，GPUs）来实现代码的加速。它们与Psyco这样的JIT编译器不一样，后者是通过代码优化来实现加速的。但如果我们有一个强大的GPU的话，为什么不用它来进行计算呢？比起GPULib，PyStream更加古老一点，而Tech-X公司已经转向了更为年轻的GPULib项目的开发。它提供了基于GPU的各种形式的数值计算。另外，如果您想用GPU来加速自己的代码，PyCUDA、PyOpenCL这两个项目也值得您试试看。

Pyrex、Cython、Numba与Shedskin：这四个项目都致力于将Python代码翻译为C、C++及LLVM代码。其中，Shedskin会将Python代码编译为C++程序，而Pyrex和Cython（后者实际上是前者的一个分支）的编译目标主要是C语言。另外，当我们用Cython（及其前身Pyrex）来进行编译时，我们可以在代码中加入一些可选的类型声明，例如静态声明一个整型变量之类的。此外，Cython还有NumPy数组的额外支持，这使您可以写出某种针对底层逻辑的代码，以高效操作数组内容。我在自己的代码中使用了这个特性，其中的部分代码的加速因子提升到300至400。而且，由Pyrex和Cython生成的代码可以直接编译为Python扩展模块，然后在Python代码中导入即可。如果您想从Python程序中生成出通用的C代码，Cython也依然是一种安全的选择。而如果您只是在寻找一种加速方式，特别是在面向数组与数学计算的代码的时候，或许Numba是一个值得看看的选择。它在被导入时会自动生成相应的LLVM代码。其升级版本NumbaPro还提供一些更为高级的功能，甚至还包含了对GPU的支持。

SWIG、F2PY与Boost.Python：这些工具可以帮助您将其他语言封装为Python的模块。它们所封装的语言分别是：C/C++，Fortran，C++。尽管我们也可以自行编写访问扩展模块的代码，但使用这些工具可以帮助我们免于许多单调乏味的工作——而且它们也更能确保结果的正确性。以SWIG为例，您只需要启动一个命令行工具，往里输入C（或C++）的头文件，封装器代码就自动生成了。SWIG的另一个优点在于，除了Python，它还可以成为很多语言的生成封装器。例如，您同样也能轻易地利用JAVA或php这样的语言来编写相关的扩展。

ctypes、llvm-py与CorePy2：这些模块可以帮助我们实现对Python底层对象的操纵。ctypes模块可用于在内存中构建编译C的对象，并且调用某些共享库中（如某些DLL）的C函数。而llvm-py包则正如之前所说，主要提供了LLVM的Python接口，以便于我们可以构建代码，然后更高效地编译它们。甚至如果您愿意的话，也可以在Python中用它来构建您自己的编译器（没准能搞出一种属于自己的编程语言！）。CorePy2也一样，它可以帮助您处理与高效运行代码对象，只不过，它是运行在汇编层的。（值得注意的是，ctypes如今已是Python标准库的一部分了。）

Weave、Cinpy与PyInline：通过这三个包，我们就可以在Python代码中直接使用C语言（或其他语言）。虽然不同的语言被混排在了一起，但代码仍然可以保持干净整洁，因为您可以使用Python字符串的多行特性，将C代码部分按照其自身的风格来排版。然后就能即时进行编译，并输出可用在Python代码中的代码对象。这样，我们就可以像使用ctypes模块那样使用它们了。

其他工具：显然，可用的工具远远不止这些，我们可以根据自己的需要来选择更多的工具。例如，如果我们希望节省的是内存而不是时间，那么JIT就不太适合了——JIT通常都需要耗费大量的内存。这时候，我会建议您去看看Micro Python项目。这是一个专为最小内存占用，使用Python的微控制器及嵌入式设备而设计的编程环境。而且，谁知道呢？也许我们有些时候根本不想用Python。或许我们只是在某种Python环境中工作，然后想使用某种高级编程语言，但同时希望自己所有代码都能运行得飞快，这时我会建议您看看Julia这个项目。尽管这项目在Python体系中算是个异类，实际上是一种不同的语言，但它的语法对于所有Python程序员来说都会感觉很熟悉。同时它也支持Python库的调用，这意味着Julia团队与Python项目之间一直有着密切的合作，例如IPython项目等2，甚至这一直是SciPy项目研讨会上的主题之一3。

表A-1　各加速器工具网站的URL

本文摘自《Python算法教程》中的附录A

Python是一种面向对象、解释型计算机程序设计语言，其应用领域非常广泛，包括数据分析、自然语言处理、机器学习、科学计算以及推荐系统构建等。

本书用Python语言来讲解算法的分析和设计。本书主要关注经典的算法，但同时会为读者理解基本算法问题和解决问题打下很好的基础。全书共11章。分别介绍了树、图、计数问题、归纳递归、遍历、分解合并、贪心算法、复杂依赖、Dijkstra算法、匹配切割问题以及困难问题及其稀释等内容。本书在每一章结束的时候均有练习题和参考资料，这为读者的自我检查以及进一步学习提供了较多的便利。在全书的最后，给出了练习题的提示，方便读者进行查漏补缺。 本书概念和知识点讲解清晰，语言简洁。本书适合对Python算法感兴趣的初中级用户阅读和自学，也适合高等院校的计算机系学生作为参考教材来阅读。