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并且提供'+'是最有效的吗？我应该使用'+'作为加入的替代方案吗？或者,我做过一些非常愚蠢的事情吗？或者是什么？请清楚解释一下.

Answer 1

我们中的一些Python提交者,我相信主要是Rigo和Hettinger,他们不顾一切地(在我认为的2.5路上)来优化一些特殊情况 - 唉 - 太普通的s += something 枯萎病,认为它已被证明是初学者永远不会被认为''.join是正确的方法,可怕的缓慢+=可能给Python一个坏名声.我们其他人并不热,因为他们不可能优化每次事件(或者甚至只是大多数事件)以获得不错的表现; 但我们在这个问题上并没有足够的热情来尝试并积极阻止他们.

我相信这个帖子证明我们应该更严厉地反对他们.就像现在一样,他们+=在一个难以预测的案例子集中进行了优化,对于特定的愚蠢案例来说,它可能比正常方式(仍然是IS ''.join)快20%- 这只是将初学者陷入困境的完美方式通过使用错误的成语追求那些不相关的20%收益......成本,偶尔和他们的POV突然出现,遭遇性能损失200%(或更多,因为非线性行为)仍然潜伏在那里的角落里,Hettinger和Rigo漂亮地把鲜花放进去;-) - 一个让人感到悲惨的事情.这与Python的"理想情况下只有一种显而易见的方式"相反,我感觉像我们一样,为初学者设置了一个陷阱 - 最好的一类......那些不接受的人什么他们被他们的"更好"告诉他们,但好奇地去问问和探索.

好吧 - 我放弃了.OP,@ mshsayem,继续,使用+ =无处不在,在琐碎,微小,无关紧要的情况下享受无关的20%加速,你最好享受它们 - 因为有一天,当你看不到它时在一个重要的,大型的操作中,你会受到200%减速的迎面而来的拖车卡车的打击(除非你运气不好,这是一个2000%的一个;-).请记住:如果你觉得"Python速度非常慢",记住,更可能的是它是你心爱的循环中的一个+=转身并咬住喂它的手.

对于我们其他人 - 那些理解它意味着什么的人我们应该忘记小的效率,大约97%的时间说,我会继续衷心地推荐''.join,所以我们都可以安然入睡,知道我们赢了'当我们最不期望并且最不能负担得起你时,会受到超线性减速的打击.但是对你来说,Armin Rigo和Raymond Hettinger(最后两位,我的亲爱的朋友,BTW,不仅仅是共同通讯员;-) - 可能你+=会顺利而且你的大O永远不会比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

......有一个半重要的数据量(非常少的百分之100的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

在平均循环时间内削减十分之一毫秒.每个人(至少是所有完全痴迷的人都表现得很好)显然知道HOISTING(从内循环中取出一遍又一遍地执行的重复计算)是优化中的关键技术--Python不会代表你提升,所以你必须在每微秒都很重要的罕见场合自己吊装.

Answer 2

至于为什么q慢得多:当你说的时候

l += "a"

你把字符串附加"a"到结尾l,但是当你说

l = l + ["a"]

要创建一个使用的内容的新列表l和["a"],然后重新分配结果回l.因此,不断生成新列表.

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 到 100 的 1 到 10 个串联（平均），则列表附加、“+”都需要相同的时间（几乎，注意时间是按比例缩放的）。
4. 优化的列表追加在大多数情况下似乎都非常好。
5. 当 #concatenation 或字符串长度增加时，“+”开始花费越来越多的时间。请注意，对于 10000 次与 100'a' 的串联，我的电脑被卡住了！
6. 如果您始终使用列表追加和“加入”，那么您始终都是安全的（Alex Martelli 指出）。
7. 但在某些情况下，例如，您需要获取用户输入并打印“Hello user's world！”，最简单的方法是使用“+”。我认为在这种情况下构建一个列表并加入 x = input("输入用户名:") 然后 x.join(["Hello ","'s world!"]) 比 "Hello %s's world!" 更丑陋！ “%x 或“你好”+x+“的世界”
8. Python 3.1 改进了串联性能。但是，在 Jython 等某些实现中，“+”效率较低。
9. 过早的优化是万恶之源（专家的说法）。大多数时候你不需要优化。因此，不要浪费时间追求优化（除非您正在编写一个大型或计算项目，其中每一微/毫秒都很重要。
10. 使用这些信息并考虑情况以您喜欢的任何方式写作。
11. 如果您确实需要优化，请使用分析器，找到瓶颈并尝试优化它们。

最后，我想更深入地学习python。所以，我的观察出现错误（错误）并不罕见。因此，对此发表评论并建议我是否走错了路。感谢大家的参与。