Pythonstring“join”比“+”更快(?),但这里有什么问题?

我在前面的post中询问了用于大规模dynamicstring连接的最有效的方法,并且我build议使用连接方法,这是最好的,最简单和最快速的方法(正如大家所说的那样)。 但是当我玩string连接时,我发现了一些奇怪的(?)结果。 我确定有些事情正在进行,但我不能完全理解。 这是我做的:

我定义了这些函数:

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) 

我试图让其他的东西(除了连接)在整个函数中保持一致。 然后我用下面的结果进行了testing(在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的替代方法吗? 或者,我做了一件非常愚蠢的事情吗? 或者是什么? 请解释清楚。

我们中的一些Python提交者,我相信大多数Rigo和Hettinger,(我相信在2.5的路上),以优化一些特殊的情况 – 太常见s += something ,争辩说被certificate,初学者永远不会确信''.join是正确的路要走,可怕的缓慢的可能会给Python一个坏名字。 我们其他人并不那么热,因为他们不可能把每一次事件(甚至只是大部分事件)都优化成体面的performance。 但是我们对这个问题感到不够热情,试图积极阻止。

我相信这个线程certificate我们应该更严厉地反对他们。 就像现在一样,他们在某些难以预测的案例子集中优化了+= ,对于特定的愚蠢案例来说,比正确的方法快20%(这仍然是''.join ) – 只是完美的方式来阻止初学者通过使用错误的习语来追求那些不相关的20%的收益……不惜一次又一次地从他们的POV中突然出现200%(或更多)的性能损失,因为非线性行为仍然潜伏在Hettinger和Rigo打扮并放入鲜花的angular落之外 – 这是一个重要的问题,一个会让他们感到痛苦的问题。 这与Python的“理想情况下只有一个显而易见的方式”是一致的,对我来说,就像我们总体上对初学者有一个陷阱 – 最好的一样……那些不仅仅接受他们被“更好的”所告知,但好奇地去质疑和探索。

啊,我放弃了。 OP,@mshsayem,继续前进,在任何地方使用+ =,享受你无关紧要的20%加速,微不足道的情况下,你最好享受他们的剑柄 – 因为有一天,当你看不到它在一个重要的,大的操作中,你会被200%减速的迎面而来的拖车卡车撞击(除非你运气不好,这是一个2000%的;)。 请记住:如果你觉得“Python速度非常慢”,请记住,它更可能是你喜欢的旋转的方式之一。

对于我们其他人来说 – 那些懂得什么意思的人, 我们应该忘记小效率,大约有97%的时间 ,我会一直热心地推荐''.join ,所以我们都可以睡得安宁,知道我们不会遇到超线性放缓,当我们最不能期望和最less可以承受的时候。 但是对你来说,Armin Rigo和Raymond Hettinger(后两位,亲爱的私人朋友,不仅仅是共同犯罪者;-) – 可能你会很顺利,你的大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 

每个297个字符的900个string,直接join列表当然是最快的,但是在这之前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 

在平均循环时间内再削减十分之一毫秒。 每个人(至less每个完全沉迷于performance的人)显然知道,HOISTING(取代内部循环,反复计算,否则会反复执行)是优化中的关键技术 – Python不会代表您提升,所以你必须在每微秒重要的罕见场合做你自己的提升。

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

 l += "a" 

你将string"a"附加到l的结尾,但是当你说

 l = l + ["a"] 

你正在用l["a"]的内容创build一个新的列表,然后将结果重新分配给l 。 因此新的列表不断被生成。

我假设x()比较慢,因为你先构build数组然后join。 所以你不仅要测量join的时间,还要测量build立arrays的时间。

在已经有一个数组的情况下,你想从它的元素中创build一个string,join应该比遍历数组并且一步一步地构buildstring要快。

这个问题真的是关于什么东西的成本。 我们会在这里玩一下,松一点,在相似的情况下减去结果。 你可以自己决定这是否是一个有效的方法。 这里有一些基本的testing用例:

 import timeit def append_to_list_with_join(): s=[] for i in xrange(100): s.append("abcdefg"[i%7]) return ''.join(s) def append_to_list_with_join_opt(): s=[] x = s.append for i in xrange(100): x("abcdefg"[i%7]) return ''.join(s) def plus_equals_string(): s='' for i in xrange(100): s+="abcdefg"[i%7] return s def plus_assign_string(): s='' for i in xrange(100): s=s+"abcdefg"[i%7] return s def list_comp_join(): return ''.join(["abcdefg"[i%7] for i in xrange(100)]) def list_comp(): return ["abcdefg"[i%7] for i in xrange(100)] def empty_loop(): for i in xrange(100): pass def loop_mod(): for i in xrange(100): a = "abcdefg"[i%7] def fast_list_join(): return "".join(["0"] * 100) for f in [append_to_list_with_join, append_to_list_with_join_opt, plus_equals_string,plus_assign_string,list_comp_join, list_comp, empty_loop,loop_mod, fast_list_join]: print f.func_name, timeit.timeit(f) 

这是他们的成本:

 append_to_list_with_join 25.4540209021 append_to_list_with_join_opt 19.9999782794 plus_equals_string 16.7842428996 plus_assign_string 14.8312124167 list_comp_join 16.329590353 list_comp 14.6934344309 empty_loop 2.3819276612 loop_mod 10.1424356308 fast_list_join 2.58149394686 

首先,很多东西在Python中有意想不到的成本。 append_to_list_with_join与append_to_list_with_join_opt的比较表明,即使在对象上查找方法也具有不可忽略的成本。 在这种情况下,查找s.append是四分之一的时间。

接下来,list_comp_join与list_comp显示join()速度相当快:大约需要1.7或者只有list_comp_join的10%。

loop_mod表明,这个testing的最大的部分实际上是在设置数据,而不pipe使用哪种string构造方法。 通过推论,“string = string +”,“string + =”和列表理解所花费的时间是:

 plus_equals_string = 16.78 - 10.14 = 6.64 plus_assign_string = 14.83 - 10.14 = 4.69 list_comp = 14.69 - 10.14 = 4.55 

关于OP的问题,join()是快速的,但创build底层列表的时间,无论是使用列表基元还是列表理解,都可以与创build带有string基元的string相媲美。 如果你已经有了一个列表,用join()将它转换成一个string – 它会很快。

OP提出的时间表明,使用连接运算符构造列表是很慢的。 相比之下,使用列表parsing是快速的。 如果你必须build立一个列表,使用列表理解。

最后,让我们来看看OP的三个最接近的函数:x,p和q之间的区别是什么? 让我们简化一下:

 import timeit def x(): s=[] for i in range(100): s.append("c") def p(): s=[] for i in range(100): s += "c" def q(): s=[] for i in range(100): s = s + ["c"] for f in [x,p,q]: print f.func_name, timeit.timeit(f) 

结果如下:

 x 16.0757342064 p 87.1533697719 q 85.0999698984 

这里是拆卸 :

 >>> import dis >>> dis.dis(x) 2 0 BUILD_LIST 0 3 STORE_FAST 0 (s) 3 6 SETUP_LOOP 33 (to 42) 9 LOAD_GLOBAL 0 (range) 12 LOAD_CONST 1 (100) 15 CALL_FUNCTION 1 18 GET_ITER >> 19 FOR_ITER 19 (to 41) 22 STORE_FAST 1 (i) 4 25 LOAD_FAST 0 (s) 28 LOAD_ATTR 1 (append) 31 LOAD_CONST 2 ('c') 34 CALL_FUNCTION 1 37 POP_TOP 38 JUMP_ABSOLUTE 19 >> 41 POP_BLOCK >> 42 LOAD_CONST 0 (None) 45 RETURN_VALUE >>> dis.dis(p) 2 0 BUILD_LIST 0 3 STORE_FAST 0 (s) 3 6 SETUP_LOOP 30 (to 39) 9 LOAD_GLOBAL 0 (range) 12 LOAD_CONST 1 (100) 15 CALL_FUNCTION 1 18 GET_ITER >> 19 FOR_ITER 16 (to 38) 22 STORE_FAST 1 (i) 4 25 LOAD_FAST 0 (s) 28 LOAD_CONST 2 ('c') 31 INPLACE_ADD 32 STORE_FAST 0 (s) 35 JUMP_ABSOLUTE 19 >> 38 POP_BLOCK >> 39 LOAD_CONST 0 (None) 42 RETURN_VALUE >>> dis.dis(q) 2 0 BUILD_LIST 0 3 STORE_FAST 0 (s) 3 6 SETUP_LOOP 33 (to 42) 9 LOAD_GLOBAL 0 (range) 12 LOAD_CONST 1 (100) 15 CALL_FUNCTION 1 18 GET_ITER >> 19 FOR_ITER 19 (to 41) 22 STORE_FAST 1 (i) 4 25 LOAD_FAST 0 (s) 28 LOAD_CONST 2 ('c') 31 BUILD_LIST 1 34 BINARY_ADD 35 STORE_FAST 0 (s) 38 JUMP_ABSOLUTE 19 >> 41 POP_BLOCK >> 42 LOAD_CONST 0 (None) 45 RETURN_VALUE 

循环几乎相同。 比较总计为CALL_FUNCTION + POP_TOP与INPLACE_ADD + STORE_FAST与BUILD_LIST + BINARY_ADD + STORE_FAST。 但是,我不能给出比这更低级的解释 – 我只是无法在网上findpython字节码的代价。 不过,您可以从Doug Hellmann的“本周Python模块”上获取灵感。

您正在测量两个不同的操作:创build一个string数组,以及string连接。

  import timeit def x(): s = [] for i in range(100): s.append("abcdefg"[i%7]) return ''.join(s) def y(): s = '' for i in range(100): s += "abcdefgh"[i%7] # timeit.timeit(x) returns about 32s # timeit.timeit(y) returns about 23s 

从上面看来,“+”的确比join更快。 但是请考虑:

  src = [] def c(): global src s = [] for i in range(100): s.append("abcdefg"[i%7]) src = s def x2(): return ''.join(src) def y2(): s = '' for i in range(len(src)): s += src[i] return s # timeit.timeit(c) returns about 30s # timeit.timeit(x2) returns about 1.5s # timeit.timeit(y2) returns about 14s 

换句话说,通过计时x()vs y(),你的结果受到源数组构造的污染。 如果你打破了这一点,你会发现join速度更快。

而且,你正在使用小型数组,而你的计时数恰好吻合。 如果你显着地增加了数组的大小和每个string的长度,差别就更加明显了:

  def c2(): global src s = [] for i in range(10000): s.append("abcdefghijklmnopqrstuvwxyz0123456789" src = s # timeit.timeit(x2, number=10000) returns about 1s # timeit.timeit(y2, number=10000) returns about 80s 

+ =和+与string是有区别的 – 如果没有其他的引用“x”,x + = y只能附加到x,而不是必须把string的副本追加到 – 这是相同的您从使用“”.join()获得的好处。

join()应该总是给出线性performance,而在很多情况下+ / + =会给出二次performance(即,当你将文本数量加倍时,翻倍所花费的时间)。 但是,这只会涉及到大量的文本,而不仅仅是100字节,而且我认为如果只有一个引用了你要附加的string,它就不会被触发。

详细:

string连接的最佳情况是查看最后一个string中的每个字符一次。 “”.join()自然就是这么做的 – 它从一开始就拥有了所有需要的信息。

然而,a + = b可以用两种方式工作,既可以在现有的string中添加“b”,在这种情况下,只需要查看“b”中的字符,也可以查看“一个“也是。

在C中,strcat()总是查看两个string中的所有字符,所以它始终工作得很糟糕。 然而,在Python中,string的长度是存储的,所以只要不在其他地方引用它就可以扩展string,只需要复制“b”中的字符即可获得良好的性能。 如果在其他地方被引用,python会首先创build一个“a”的副本,然后将“b”添加到最后,从而导致性能不佳。 如果你用这种方式添加五个string,你的时间将是:

 ab = a+b # Time is a + b abc = ab+c # Time is (a+b) + c abcd = abc+d # Time is (a+b+c) + d abcde = abcd+e # Time is (a+b+c+d) + e 

如果a,b,c,d,e都大致相同,比如说n是n *(n-1)/ 2-1运算,或者基本上是n平方。

要获得x + = y的不良行为,请尝试:

 def a(n=100): res = "" for k in xrange(n): v=res res += "foobar" return res 

即使v没有被实际使用,也足以触发+ =的较慢path,并得到令人担忧的不良行为。

我相信+ =在Python 2.0之前并没有被引入,所以在Python 1.6和更早的版本中不使用类似“.join()”的东西是不可能的。

已经有很多很好的总结,但只是为了更多的证据。

来源:我盯着python源代码一个小时,计算复杂性!

我的发现。

对于2个string。 (假设n是两个string的长度)

 Concat (+) - O(n) Join - O(n+k) effectively O(n) Format - O(2n+k) effectively O(n) 

超过2个string。 (假设n是所有string的长度)

 Concat (+) - O(n^2) Join - O(n+k) effectively O(n) Format - O(2n+k) effectively O(n) 

结果:

如果你有两个string,技术上的连接(+)更好,尽pipe它和连接和格式完全一样。

如果你有两个以上的string,concat会变得糟糕,连接和格式实际上是一样的,尽pipe从技术上来说join更好一点。

概要:

如果你不关心效率使用上面的任何一个。 (虽然自从你问了这个问题,我会认为你很在意)

因此 –

如果你有2个string使用concat(当不在循环中!)

如果你有两个以上的string(所有的string)(或循环)使用连接

如果你有什么没有string使用的格式,因为呃。

希望这可以帮助!

我已经find了专家在这里发表的答案的答案。 Pythonstring连接(和时间测量)取决于这些(据我所见):

  • 连接数
  • 平均长度的string
  • 函数调用次数

我已经build立了一个新的代码,涉及这些。 感谢Peter S Magnusson,sepp2k,hughdbrown,David Wolever和其他人指出了我之前错过的要点。 而且,在这个代码中,我可能错过了一些东西。 所以,我非常感谢任何回复指出我们的错误,build议,批评等。毕竟,我在这里学习。 这是我的新代码:

 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. 如果你有一个string列表可用,string“join”方法是最好的和最快的。
  2. 如果你可以使用列表理解,这也是最简单和快速的。
  3. 如果需要长度为1到100的1到10级联(平均值),列表附加,“+”两者都需要相同(几乎注意时间被缩放)。
  4. 在大多数情况下,优化列表附加似乎非常好。
  5. 当#连接或string长度增加时,“+”开始花费越来越多的时间。 请注意,与100'a'我的电脑连接10000卡住了!
  6. 如果你总是使用list append和'join',那么你是安全的(Alex Martelli指出)。
  7. 但在某些情况下,如果需要用户input并打印“Hello user's world!”,则最简单的方法就是使用“+”。 我想build立一个列表,join这个例子,如x = input(“input用户名:”),然后x.join([“Hello”,“的世界!”))比“Hello%s的世界! “%x或”你好“+ x +”的世界“
  8. Python 3.1改进了连接性能。 但是在像Jython这样的一些实现中,“+”效率较低。
  9. 不成熟的优化是万恶之源(专家说)。 大多数时候你不需要优化。 所以,不要浪费时间来寻求优化(除非你正在编写一个大的计算项目,每微秒/毫秒的计数。
  10. 使用这些信息,并以您喜欢的任何方式写下考虑的情况。
  11. 如果您确实需要优化,请使用分析器,find瓶颈并尝试优化这些瓶颈。

最后,我正在尝试更深入地学习python。 所以,在我的观察中会出现错误(错误)并不罕见。 所以,评论这一点,并build议我,如果我走错了路线。 感谢所有参与。

有趣的是:我已经做了一些testing,其中string的大小发生了变化,这就是我发现的:

 def x(): x = "a" * 100 s=[] for i in range(100): # Other codes here... s.append(x) return ''.join(s) def z(): x = "a" * 100 s='' for i in xrange(100): # Other codes here... s=s+x return s from timeit import timeit print "x:", timeit(x, number=1000000) print "z:", timeit(z, number=1000000) 

对于长度为1( x = "a" * 1 )的string:

 x: 27.2318270206 z: 14.4046051502 

对于长度为100的string:

 x: 30.0796670914 z: 21.5891489983 

而对于长度为1000的string,运行时间为100,000次,而不是1,000,000次

 x: 14.1769361496 z: 31.4864079952 

其中,如果我阅读Objects/stringobject.c是正确的,这是有道理的。

看起来,在第一次阅读,String.joinalgorithm(边缘情况旁边)是:

 def join(sep, sequence): size = 0 for string in sequence: size += len(string) + len(sep) result = malloc(size) for string in sequence: copy string into result copy sep into result return result 

所以这将需要更多或更less的O(S)步骤(其中S是所有串连接的长度的总和)。

除了其他人所说的外,100个1字符的string真的很小 。 (我有点惊讶,你得到的结果分离。)这是适合你的处理器caching的那种数据集。 你不会在microbenchmark上看到渐近的performance。

在Python 2.5之前,string连接要慢得多,当时它仍然为每个string连接创build一个新的副本,而不是追加到原始文件,导致join()成为一个受欢迎的解决方法。

这是一个陈旧的问题,旧的基准: http : //www.skymind.com/~ocrow/python_string/