[翻译]Python模式──优化轶事
2008年05月29日 00:33
原文见http://www.python.org/doc/essays/list2str.html
翻译：令狐虫
前几天，一个朋友问了我一个看起来很简单的问题：将一个整数列表转换成一个字符串的最好方法是什么，假设这些整数都是ASCII值。例如，列表[97, 98, 99]应该被转换成字符串'abc'。我们假定要写一个函数来做这件事。
我写出的第一个版本相当的直观：
def f1(list):
string = ""
for item in list:
string = string + chr(item)
return string
这一定不是最快的方法，朋友说，这个怎么样：
def f2(list):
return reduce(lambda string, item: string + chr(item), list, "")
这个版本使用了与第一个完全相同的字符串操作集，但去除了for循环的开销，转用更快的reduce()函数中的隐式循环。
当然，我回答，但它这样做会在每一个列表项中产生函数调用（lambda函数）的成本。我跟你打赌它会更慢，因为在Python中，函数调用开销比for循环开销更大。
（OK，其实我已经做过比较了。 f2() 比 f1() 多花了60%的时间。你瞧，我说的没错吧 ：-）
唔，朋友说，我得让它再快点儿。好吧，我说，这个版本如何：
def f3(list):
string = ""
for character in map(chr, list):
string = string + character
return string
让我们俩都感到吃惊的是，f3()比f1()快了整整两倍！令我们吃惊的原因是双重的：第一，它使用了更多的存储空间（map(chr, list)的结果是另一个相同长度的列表）；第二，它包含了双重循环而不是单重（一个是map()函数中的隐式循环，一个是for循环）。
当然，空间换时间是一个众所皆知的代换方法，所以对于第一点我们不该感到吃惊。然而，为什么双重循环比单重循环还要更快呢？两点原因。
第一点，在f1()中，内置函数chr()在每次迭代中都要被查找，而在f3()中它只被查找了一次（作为map()的参数）。这个查找代价比较昂贵，我告诉朋友，因为Python的动态作用域规则意味着它首先查找当前模块的全局字典（不会成功），然后再找内置函数字典（这里找到了）。更糟的是，因为哈希链表的工作原理，不成功的字典查找（平均）要比成功查找慢一些。
第二点f3()为什么比f1()更快的原因在于对chr(item)的调用，被字节码解释器执行时，要比被map()函数执行慢一些。字节码解释器必须在每次调用时执行三条字节码指令（load 'chr'， load 'item', call），而map()函数在C代码里做这些。
这里让我们做一个折衷，不要浪费额外的空间，但是加速一下对chr()函数的查找：
def f4(list):
string = ""
lchr = chr
for item in list:
string = string + lchr(item)
如我们所期，f4()比f3()要慢，但只慢了25%；它仍然比f1()快差不多40%。这是因为本地变量查找比全局或内置变量查找要快得多：Python“编译器”对大多数函数体进行了优化，因此对于本地变量，不需要进行字典查找，一个简单的数组索引操作足够了。跟f1()和f3()比较而言，f4()的相对速度暗示了为什么f3()是一个更快选择的全部原因，但第一个原因（更少的查找）比较重要一点。（要得到关于这一点更精确的数据，我们将不得不深入研究一下解释器。）
至此，我们最好的版本，f3()，也只比我们的最直观的版本f1()快了2倍。我们还能做得更好吗？
我怕那些算法的二次行为（译注：指算法时间非线性增长的行为）会搞死我们。目前为止我们已经用到了一个256个整数的列表作为测试数据，因为那是我朋友对此函数的需求。但如果把它用在一个两千个字符的列表上呢？我们将会拼接越来越长的字符串，每次一个字符。很容易看到，除了时间开销之外，用这种方法建立一个长度为N的列表，一共有1 + 2 + 3 + ... + (N-1)个字符需要被复制，也就是N*(N-1)/2，也就是0.5*N**2 - 0.5*N。除此之外，有N个字符串内存分配操作，但对于非常大的N来说，公式中包含的N**2将会超过限度。甚至，对于一个8倍长度的列表（2048项）来说，这个函数需要花费的时间远远超过8倍；事实上，是接近于16倍。我没敢尝试64倍长的列表。
有一个通用的技术可以避免像这样的算法二次行为。对于正好是256项的字符串，我做了如下编码：
def f5(list):
string = ""
for i in range(0, 256, 16): # 0, 16, 32, 48, 64, ...
s = ""
for character in map(chr, list[i:i+16]):
s = s + character
string = string + s
不幸的是，对于256项的列表，这个版本比f3()要慢一些（20%以内）。由于写一个通用版本只会让它慢更多，我们就不费心在这条路上继续下去了。（除此之外我们也跟另一个没有使用map的变种做了一比较，当然那更慢了。）
最后，我尝试了一种完全不同的激进方法：仅使用隐式循环。注意到整个操作可以作如下描述：应用chr()到每一个列表项；然后将结果字符连接起来。我们已经在第一部分使用了一个隐式循环：map()。
幸运的是，在string模块中有几个用C实现的字符串连接函数。特别是string.joinfields(list_of_strings, delimiter)连接一个字符串列表，在每两个字符串之间放置一个选好的分割符。你瞧：
import string
def f6(list):
return string.joinfields(map(chr, list), "")
这个函数跑起来比我们最快的竞争者f3()要快4-5倍。更重要的是，它没有像其它版本那样的二次行为。
获胜的是……
第二天，我想起了Python的一个犄角旮旯：array模块。它用于从一个Python整数列表生成一个单字节长度的整数数组，并且每一个数组可以作为二进制数据结构写入一个文件或一个字符串。这就是应用这些操作实现的函数：
import array
def f7(list):
return array.array('B', list).tostring()
这比f6()大约快三倍，也就是比f3()快12-15倍！同时它使用了更少的中间存储空间──它只分配了2个N字节的对象（加上固定长度的额外空间），而f6()开始分配了N项的一个列表，实际占用4N字节（64位机器上是8N字节）──假设字符对象在程序的其它地方共享相同的对象（就像小整数，Python在大多数情况下，将它们缓存在长度为1的字符串里）。
够了，朋友说，在你得到负倍数之前──这对我的程序而言已经够快了。我同意，不过我还是想尝试多一种方法：将整个函数用C写。这可以做到最小存储空间需求（它可以分配正好N长的字符串）以及在C代码中节省据我所知在array模块中存在的一些指令，因为它的通用性（它支持宽度为1、2和4字节的整型）。然而，它不能避免每次从list分解出一项，以及从项中分解出C整型，这两项都是Python-C API中的耗时操作，因此我预期跟f7()相比最多只能得到适度的加速。跟编写和测试扩展所做的努力（对比那些快速完成的单行python代码），以及对非标准Python扩展的依赖，我决定不再继续这个选择……。
结论
如果你感受到对速度的需要，首选内置函数──你无法打败一个用C写成的循环。检查内置函数库手册，找到你想要的。如果没有，这里是一些优化循环的指南：
- 第一规则：仅当速度被证实是瓶颈时才优化。仅优化最内部的循环。（这条规则是独立于Python的。不过它再怎么重复也不过分，因为它能节省大量的工作 ：-）
- 小就是美。既然Python已经有了完备的字节码指令和变量查找的管理，于是很少会达到这样的一种平衡，即为了省下一些工作，而增加额外的测试。
- 使用内置操作。map()中的隐式循环比显式的for循环要快。使用显式循环计数器的while循环更慢。
- 不要在你的内部循环中调用Python写的函数。包括lambda。在内部循环中内联代码（译注：这里指的是类似C++中inline函数，将代码在调用处展开）将节省很多时间。
- 本地变量比全局的要快；如果你在循环中使用一个全局常量，在进入循环前将它复制到一个本地变量。并且，在Python中，函数名（全局的或内置的）也是全局常量！
- 尝试使用map()、filter()或reduce()替换显式for循环，但仅在你可以使用内置函数的时候：使用内置函数的map胜过for循环，但使用内联代码的for循环胜过使用lambda函数的map()！
- 检查算法的二次行为。但要注意更复杂的算法只对大的N有利——对于小的N，复杂不会带来什么好处。在我们的例子中，256算是够小的了，一个更简单的版本也还是很快。你的情况可能不同——这是值得去调研的。
- 最后但并非最不重要的：收集数据。Python优秀的profile模块可以快速的显示你代码中的瓶颈。如果你决定尝试一个算法的不同版本，在一个密集循环中用time.clock()函数测试它。
顺便说一句，这是我所使用的计时函数。它以a为参数，调用一个函数f n*10次。并打印出函数的名称后面跟着他所用的时间，四舍五入到毫秒。10个重复的调用是为了让计时函数本身的循环开销降到最低。你可以更进一步，做100次调用……。另外要注意表达式range(n)的计算是在计时段的外面——另一个让计时函数本身开销降低的小技巧。如果你确实很在意这种开销，你可以通过调用计时函数测量一个什么都不做的函数来进行校准。
import time
def timing(f, n, a):
print f.__name__,
r = range(n)
t1 = time.clock()
for i in r:
f(a); f(a); f(a); f(a); f(a); f(a); f(a); f(a); f(a); f(a)
t2 = time.clock()
print round(t2-t1, 3)
尾声
几天后，我的朋友又带着问题回来了：如何做一个相反的操作？也就是说，通过一个字符串建立一个整数ASCII值的列表。哦不，又来了，这个念头在我脑海中一闪而过……。
不过这次，相对来说没什么痛苦。有两个候选者，直观的：
def g1(string):
return map(ord, string)
和不那么直观的：
import array
def g2(string):
return array.array('b', string).tolist()
计时显示，g2()差不多是g1()的5倍快。但这里有一个值得注意的地方：g2()返回整型的范围是-128..127，而g1()返回整型范围是0..255。如果你需要正整型，g1()会比g2()更快，无论你用什么方法对g2()结果做事后处理。（注意，在本文写作过程中，类型值'B'被加入了array模块，它保存非负字节码，所以再没有任何理由选择g1()了。）
示例代码
（略）
