Python 字符串 'join' 比 '+' 快（？），但这里有什么问题？

Question

我之前问过关于如何高效地拼接多个字符串的方法，大家都建议我使用join方法，认为这是最好的、最简单的和最快的方式。但是在我尝试拼接字符串的时候，发现了一些奇怪的结果。我觉得这里面肯定有什么原因，但我不太明白。以下是我做的事情：

我定义了这些函数：

import timeit
def x():
    s=[]
    for i in range(100):
        # Other codes here...
        s.append("abcdefg"[i%7])
    return ''.join(s)

def y():
    s=''
    for i in range(100):
        # Other codes here...
        s+="abcdefg"[i%7]
    return s

def z():
    s=''
    for i in range(100):
        # Other codes here...
        s=s+"abcdefg"[i%7]
    return s

def p():
    s=[]
    for i in range(100):
        # Other codes here...
        s+="abcdefg"[i%7]
    return ''.join(s)

def q():
    s=[]
    for i in range(100):
        # Other codes here...
        s = s + ["abcdefg"[i%7]]
    return ''.join(s)

我尽量保持其他部分（除了拼接）在各个函数中几乎相同。然后我用以下方式进行了测试，并在注释中写下了结果（使用的是Windows 32位机器上的Python 3.1.1 IDLE）：

timeit.timeit(x) # 31.54912480500002
timeit.timeit(y) # 23.533029429999942 
timeit.timeit(z) # 22.116181330000018
timeit.timeit(p) # 37.718607439999914
timeit.timeit(q) # 108.60377576499991

结果显示strng = strng + dyn_strng是最快的。虽然时间上的差异并不算太大（除了最后一个），但我想知道为什么会这样。这是因为我使用的是Python 3.1.1，所以'+'操作符效率最高吗？我应该把'+'作为join的替代方法吗？还是说我做了什么特别傻的事情？请详细解释一下。

Answer 1

关于为什么 q 会慢很多：当你写

l += "a"

时，你是在把字符串 "a" 加到 l 的末尾，但当你写

l = l + ["a"]

时，你是在创建一个新列表，这个新列表包含了 l 的内容和 ["a"]，然后再把这个新列表赋值回 l。所以，新的列表一直在被生成。

Answer 2

一些Python的开发者，比如Rigo和Hettinger，曾经在2.5版本的开发过程中，特别努力地优化了一个非常常见的情况，就是用 s += something 这种写法。他们认为，初学者根本不会相信 ''.join 是更好的选择，而 += 的速度太慢，可能会让Python的名声变差。还有一些人对这个问题不太在意，因为他们觉得不可能优化每一个出现的地方（甚至大部分地方）到一个合理的性能水平；不过，他们也没有强烈反对这些优化。

我觉得这个讨论证明我们应该更坚决地反对这些优化。现在的情况是，他们在一些难以预测的特定情况下优化了 +=，让它在某些情况下比正确的写法（也就是 ''.join）快了大约20%。这就像是给初学者设了一个陷阱，让他们追求那些无关紧要的20%的速度提升，结果却可能在某个重要的、大的操作中遭遇200%（甚至更多）的性能下降，这种情况是非常糟糕的。这与Python“理想情况下只有一种明显的方法”的理念相悖，感觉我们集体上给初学者设了一个陷阱，尤其是那些不只是接受“前辈”所说的，而是好奇地去探究和质疑的人。

唉，我放弃了。OP，@mshsayem，随便吧，尽情使用 +=，享受那些在微不足道的小情况中获得的20%的速度提升吧，记得好好享受这些提升，因为有一天，当你没有预料到的时候，在一个重要的大操作上，你会被突然出现的200%的性能下降狠狠击中（当然也有可能是2000%的下降；-）。只要记住：如果你觉得“Python非常慢”，大概率是因为你那些心爱的 += 循环在反咬你自己。

对于我们其他人来说——那些明白大约97%的时间应该忘记小效率的人，我会继续大力推荐 ''.join，这样我们都能安心睡觉，知道不会在最不期待的时候遭遇超线性的性能下降。但对于你，Armin Rigo和Raymond Hettinger（顺便说一下，后两位是我亲密的朋友，不仅仅是共同开发者；-)），希望你们的 += 一切顺利，性能不会比N!更糟糕！

所以，对于我们其他人，这里有一组更有意义和有趣的测量结果：

$ python -mtimeit -s'r=[str(x)*99 for x in xrange(100,1000)]' 's="".join(r)'
1000 loops, best of 3: 319 usec per loop

900个297个字符的字符串，直接连接列表当然是最快的，但OP对在此之前进行追加操作感到恐惧。不过：

$ python -mtimeit -s'r=[str(x)*99 for x in xrange(100,1000)]' 's=""' 'for x in r: s+=x'
1000 loops, best of 3: 779 usec per loop
$ python -mtimeit -s'r=[str(x)*99 for x in xrange(100,1000)]' 'z=[]' 'for x in r: z.append(x)' '"".join(z)'
1000 loops, best of 3: 538 usec per loop

...在处理一些重要的数据（几百KB的量级——每种方式都需要可测量的毫秒数），即使是普通的 .append 也已经优于 +=。而且，优化这个过程显然是简单明了的：

$ python -mtimeit -s'r=[str(x)*99 for x in xrange(100,1000)]' 'z=[]; zap=z.append' 'for x in r: zap(x)' '"".join(z)'
1000 loops, best of 3: 438 usec per loop

在平均循环时间上再减少几分之一毫秒。每个人（至少是那些对性能极其痴迷的人）都知道“提升”（把重复计算从内循环中拿出来，避免重复执行）是优化中的关键技术——Python不会为你自动提升，所以在那些每微秒都很重要的情况下，你得自己进行提升。

Answer 3

我从这里专家们的回答中找到了答案。Python 字符串连接（还有时间测量）主要受以下几个因素影响：

• 连接的次数
• 字符串的平均长度
• 函数调用的次数

我写了一个新的代码来关联这些因素。感谢 Peter S Magnusson、sepp2k、hughdbrown、David Wolever 以及其他指出我之前遗漏的重要点的人。此外，我的代码中可能还有遗漏，所以非常欢迎大家指出错误、提出建议或批评。毕竟，我在这里是为了学习。以下是我的新代码：

from timeit import timeit

noc = 100
tocat = "a"
def f_call():
    pass

def loop_only():
    for i in range(noc):
        pass

def concat_method():
    s = ''
    for i in range(noc):
        s = s + tocat

def list_append():
    s=[]
    for i in range(noc):
        s.append(tocat)
    ''.join(s)

def list_append_opt():
    s = []
    zap = s.append
    for i in range(noc):
        zap(tocat)
    ''.join(s)

def list_comp():
    ''.join(tocat for i in range(noc))

def concat_method_buildup():
    s=''

def list_append_buildup():
    s=[]

def list_append_opt_buildup():
    s=[]
    zap = s.append

def function_time(f):
    return timeit(f,number=1000)*1000

f_callt = function_time(f_call)

def measure(ftuple,n,tc):
    global noc,tocat
    noc = n
    tocat = tc
    loopt = function_time(loop_only) - f_callt
    buildup_time = function_time(ftuple[1]) -f_callt if ftuple[1] else 0
    total_time = function_time(ftuple[0])
    return total_time, total_time - f_callt - buildup_time - loopt*ftuple[2]

functions ={'Concat Method\t\t':(concat_method,concat_method_buildup,True),
            'List append\t\t\t':(list_append,list_append_buildup,True),
            'Optimized list append':(list_append_opt,list_append_opt_buildup,True),
            'List comp\t\t\t':(list_comp,0,False)}

for i in range(5):
    print("\n\n%d concatenation\t\t\t\t10'a'\t\t\t\t 100'a'\t\t\t1000'a'"%10**i)
    print('-'*80)
    for (f,ft) in functions.items():
        print(f,"\t|",end="\t")
        for j in range(3):
            t = measure(ft,10**i,'a'*10**j)
            print("%.3f %.3f |" % t,end="\t")
        print()

这是我得到的结果。[在时间列中显示了两个时间（经过缩放）：第一个是函数的总执行时间，第二个是实际的连接时间。我已经减去了函数调用时间、函数构建时间（初始化时间）和迭代时间。这里我考虑的是一个必须使用循环的情况（比如里面有更多的语句）。]

1 concatenation                 1'a'                  10'a'               100'a'
-------------------     ----------------------  -------------------  ----------------
List comp               |   2.310 2.168       |  2.298 2.156       |  2.304 2.162
Optimized list append   |   1.069 0.439       |  1.098 0.456       |  1.071 0.413
Concat Method           |   0.552 0.034       |  0.541 0.025       |  0.565 0.048
List append             |   1.099 0.557       |  1.099 0.552       |  1.094 0.552


10 concatenations                1'a'                  10'a'               100'a'
-------------------     ----------------------  -------------------  ----------------
List comp               |   3.366 3.224       |  3.473 3.331       |  4.058 3.916
Optimized list append   |   2.778 2.003       |  2.956 2.186       |  3.417 2.639
Concat Method           |   1.602 0.943       |  1.910 1.259       |  3.381 2.724
List append             |   3.290 2.612       |  3.378 2.699       |  3.959 3.282


100 concatenations               1'a'                  10'a'               100'a'
-------------------     ----------------------  -------------------  ----------------
List comp               |   15.900 15.758     |  17.086 16.944     |  20.260 20.118
Optimized list append   |   15.178 12.585     |  16.203 13.527     |  19.336 16.703
Concat Method           |   10.937 8.482      |  25.731 23.263     |  29.390 26.934
List append             |   20.515 18.031     |  21.599 19.115     |  24.487 22.003


1000 concatenations               1'a'                  10'a'               100'a'
-------------------     ----------------------  -------------------  ----------------
List comp               |   134.507 134.365   |  143.913 143.771   |  201.062 200.920
Optimized list append   |   112.018 77.525    |  121.487 87.419    |  151.063 117.059
Concat Method           |   214.329 180.093   |  290.380 256.515   |  324.572 290.720
List append             |   167.625 133.619   |  176.241 142.267   |  205.259 171.313


10000 concatenations              1'a'                  10'a'               100'a'
-------------------     ----------------------  -------------------  ----------------
List comp               |   1309.702 1309.560 |  1404.191 1404.049 |  2912.483 2912.341
Optimized list append   |   1042.271 668.696  |  1134.404 761.036  |  2628.882 2255.804
Concat Method           |   2310.204 1941.096 |  2923.805 2550.803 |  STUCK    STUCK
List append             |   1624.795 1251.589 |  1717.501 1345.137 |  3182.347 2809.233

总结一下，我做出了以下决定：

1. 如果你有一个字符串列表，使用字符串的 'join' 方法是最好的，也是最快的。
2. 如果可以使用列表推导，那是最简单且快速的方法。
3. 如果你需要进行 1 到 10 次的连接（平均），字符串长度在 1 到 100 之间，使用列表的 append 和 '+' 这两种方法几乎耗时相同（注意时间是经过缩放的）。
4. 优化后的列表 append 在大多数情况下表现很好。
5. 当连接次数或字符串长度增加时，使用 '+' 的时间会显著增加。注意，对于 10000 次连接 100 个 'a'，我的电脑会卡住！
6. 如果你总是使用列表的 append 和 'join'，你就安全了（这是 Alex Martelli 指出的）。
7. 但在某些情况下，比如需要用户输入并打印 'Hello 用户的世界！'，使用 '+' 是最简单的。我觉得像 x = input("请输入用户名：") 然后用 x.join(["Hello ", "'s world!"]) 这种方式比 "Hello %s's world!"%x 或 "Hello " +x+ "'s world" 看起来要复杂得多。
8. Python 3.1 改进了连接性能。但是，在某些实现中，比如 Jython，使用 '+' 的效率较低。
9. 过早优化是万恶之源（专家的说法）。大多数时候你不需要优化。所以，不要在追求优化上浪费时间（除非你在写一个大型或计算密集型的项目，每一微秒都很重要）。
10. 根据这些信息，写出你喜欢的代码，考虑具体情况。
11. 如果你真的需要优化，使用性能分析工具，找出瓶颈并尝试优化这些部分。

最后，我正在努力更深入地学习 Python。所以，我的观察中可能会有错误（bug），这并不奇怪。请对此进行评论并建议我是否走错了方向。感谢所有参与的人。