我提出的第一个版本非常直接

    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 循环开销更大。”

（好吧，所以我已经做了比较。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() 函数执行时慢一点——字节码解释器必须为每个调用执行三条字节码指令（加载 'chr'，加载 'item'，调用），而 map() 函数则全部在 C 中完成。

这使我们考虑了一种折衷方案，它不会浪费额外的空间，但会加快 chr() 函数的查找速度

    def f4(list):
        string = ""
        lchr = chr
        for item in list:
            string = string + lchr(item)
        return string

正如所料，f4() 比 f3() 慢，但只慢了 25%；它仍然比 f1() 快大约 40%。这是因为局部变量查找_远_快于全局或内置变量查找：Python“编译器”优化了大多数函数体，使得对于局部变量，无需进行字典查找，简单的数组索引操作就足够了。f4() 相对于 f1() 和 f3() 的相对速度表明 f3() 更快的两个原因都有贡献，但第一个原因（查找次数更少）更为重要。（要获得更精确的数据，我们需要对解释器进行插桩。）

尽管如此，我们最好的版本 f3() 仍然只比最直接的版本 f1() 快两倍。我们能做得更好吗？

我担心算法的二次行为会拖垮我们。到目前为止，我们一直使用包含 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
        return string

不幸的是，对于 256 个项目的列表，这个版本的运行速度略慢于 f3()（尽管在 20% 以内）。由于编写通用版本只会使其更慢，我们没有再进一步追究这条路径（除了我们还将其与一个不使用 map() 的变体进行了比较，当然那个更慢）。

最后，我尝试了一种截然不同的方法：_只_使用隐含的循环。请注意，整个操作可以描述如下：对每个列表项应用 chr()；然后连接生成的字符。我们已经为第一部分使用了隐含循环：map()。幸运的是，string 模块中有一些字符串连接函数是用 C 实现的。特别是，string.joinfields(list_of_strings, delimiter) 连接字符串列表，在每两个字符串之间放置一个选择的分隔符。没有什么能阻止我们连接字符列表（在 Python 中，字符只是长度为一的字符串），使用空字符串作为分隔符。瞧！

    import string
    def f6(list):
        return string.joinfields(map(chr, list), "")

这个函数比我们最快的竞争者 f3() 快四到五倍。此外，它没有其他版本的二次行为。

赢家是...

第二天，我忽然想起 Python 的一个不为人知的角落：array 模块。它恰好有一个操作，可以从 Python 整数列表中创建 1 字节宽的整数数组，并且每个数组都可以写入文件或转换为字符串作为二进制数据结构。以下是使用这些操作实现的函数

    import array
    def f7(list):
        return array.array('B', list).tostring()

这比 f6() 快大约三倍，或者比 f3() 快 12 到 15 倍！它还使用了更少的中间存储——它只分配了 N 字节的 2 个对象（加上固定的开销），而 f6() 首先分配了一个包含 N 个项目的列表，这通常需要 4N 字节（在 64 位机器上为 8N 字节）——假设字符对象与程序中其他地方的类似对象共享（就像小整数一样，Python 在大多数情况下会缓存长度为一的字符串）。

“停，”我的朋友说，“在你还没进入负值时间之前——这已经足够快了，我的程序。”我同意了，尽管我本来还想尝试一种方法：用 C 语言编写整个函数。这可以实现最小的存储要求（它会立即分配一个长度为 N 的字符串）并在 C 代码中节省一些指令，我知道这些指令存在于 array 模块中，因为它具有通用性（它支持 1、2 和 4 字节的整数宽度）。然而，它无法避免必须一个接一个地从列表中提取项目，并从中提取 C 整数，这两者在 Python-C API 中都是相当昂贵的操作，所以我预计与 f7() 相比，速度提升最多是适度的。考虑到编写和测试扩展的努力（与快速编写 Python 单行代码相比），以及对非标准 Python 扩展的依赖，我决定不再追求这个选项……

结论

如果你需要速度，请选择内置函数——你无法超越用 C 编写的循环。查阅库手册，看看是否有你想要的内置函数。如果没有，这里有一些循环优化的指导方针

• _第一条规则：_ 只有在有确凿证据表明存在速度瓶颈时才进行优化。只优化最内层的循环。（这条规则与 Python 无关，但重复它并无坏处，因为它能节省大量工作。:-)）
• 小即是美。鉴于 Python 在字节码指令和变量查找方面的巨大开销，增加额外的测试以节省一点点工作量通常不划算。
• 使用内在操作。map() 中的隐含循环比显式 for 循环更快；带有显式循环计数器的 while 循环甚至更慢。
• 避免在内层循环中调用用 Python 编写的函数。这包括 lambda 函数。将内层循环内联可以节省大量时间。
• 局部变量比全局变量快；如果在一个循环中使用全局常量，请在循环之前将其复制到局部变量中。在 Python 中，函数名（全局或内置）也是全局常量！
• 尝试使用 map()、filter() 或 reduce() 来替换显式 for 循环，但前提是你能够使用内置函数：map 结合内置函数胜过 for 循环，但带有内联代码的 for 循环胜过 map 结合 lambda 函数！
• 检查你的算法是否存在二次行为。但请注意，更复杂的算法只对大 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() 的五倍。不过有一个问题：g2() 返回的整数范围是 -128..127，而 g1() 返回的整数范围是 0..255。如果你需要正整数，g1() 会比你对 g2() 结果进行任何后处理都要快。（注意：自本文撰写以来，array 模块中添加了 'B' 类型代码，它存储无符号字节，因此不再有理由偏好 g1()。）

示例代码

• 计时 f1() 到 f7()
• 计时 g1() 和 g2()