我想到的第一个版本非常简单

    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()。幸运的是，字符串模块中有一些用 C 实现的字符串连接函数。特别是，string.joinfields(list_of_strings, delimiter) 连接一个字符串列表，在每两个字符串之间放置一个选择的分隔符。没有任何东西阻止我们使用空字符串作为分隔符来连接字符列表（在 Python 中只是长度为 1 的字符串）。瞧

    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 会缓存长度为 1 的字符串）。

停！我的朋友说，在你进入负时间之前 - 这对我的程序来说已经足够快了。我同意了，尽管我想尝试另一种方法：用 C 编写整个函数。这可以最大限度地减少存储需求（它会立即分配一个长度为 N 的字符串），并在我知道 array 模块中存在的 C 代码中节省一些指令，因为它具有通用性（它支持 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 循环比带有 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() 快大约五倍。但这里有一个问题：g2() 返回 -128..127 范围内的整数，而 g1() 返回 0..255 范围内的整数。如果你需要正整数，那么 g1() 将比你对 g2() 的结果进行任何后处理都要快。（注意：自从本文撰写以来，array 模块中添加了“B”类型代码，该代码存储无符号字节，因此不再有理由优先选择 g1() 了。）

示例代码

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