为什么在Python中“.join()比+ =快?

我可以在网上find大量的信息(Stack Overflow和其他方式),了解如何在Python中使用++=进行连接,这是一种非常低效和糟糕的做法。

我似乎无法findWHY +=是如此低效。 除了在这里提到“在某些情况下已经优化20%”(还不清楚这些情况是怎么样的),我找不到任何额外的信息。

在更技术层面上发生了什么,使''.join()优于其他Python连接方法?

假设你有这个代码从三个stringbuild立一个string:

 x = 'foo' x += 'bar' # 'foobar' x += 'baz' # 'foobarbaz' 

在这种情况下,Python首先需要分配和创build'foobar'然后才能分配和创build'foobarbaz'

因此,对于被调用的每个+= ,string的全部内容以及添加到其中的任何内容都需要被复制到一个全新的内存缓冲区中。 换句话说,如果你要连接Nstring,你需要分配大约N临时string,第一个子string被复制〜N次。 最后一个子string只被复制一次,但平均而言,每个子string被复制~N/2次。

使用.join ,Python可以发挥一些技巧,因为不需要创build中间string。 CPython会预测它需要多less内存,然后分配一个正确大小的缓冲区。 最后,它将每一块复制到新的缓冲区中,这意味着每个块只被复制一次。


在某些情况下,还有其他可行的方法可以导致更好的性能。 例如,如果内部string表示实际上是一个rope或者如果运行时确实足够聪明,以某种方式发现临时string对程序没有用处并优化它们。

但是,CPython肯定不会可靠地进行这些优化(虽然可能会出现一些问题 ),并且由于它是最常用的实现,所以许多最佳实践都基于对CPython有效的方法。 拥有一套标准化的规范也使得其他实现更容易集中优化工作。

我认为这个行为最好在Lua的string缓冲区章节中解释。

为了在Python的上下文中重写这个解释,让我们从一个无辜的代码片断(Lua文档中的衍生物)开始:

 s = "" for l in some_list: s += l 

假设每个l是20个字节,并且s已经被parsing为大小为50 KB。 当Python连接s + l它会创build一个包含50,020字节的新string,并将s从这个新string中复制50 KB。 也就是说,对于每一个新的行,程序移动50 KB的内存,并增长。 在阅读100个新行(仅2 KB)之后,该片段已经移动了超过5 MB的内存。 让事情变得更糟,在分配之后

 s += l 

旧的string现在是垃圾。 两个循环后,有两个旧的string,总共超过100 KB的垃圾。 所以,语言编译器决定运行它的垃圾收集器,并释放这些100 KB。 问题是,这将发生每两个周期,程序将运行其垃圾收集器两千次,然后再阅读整个列表。 即使所有这些工作,其内存使用量将是列表大小的一个很大的倍数。

最后:

这个问题并不是Lua所特有的:具有真正的垃圾收集的其他语言,以及string是不可变的对象,呈现出类似的行为,Java是最着名的例子。 (Java提供了结构StringBuffer来改善问题。)

Pythonstring也是不可变的对象 。