为什么'.join()在Python中比+ =更快？

Question

我能够在线找到一大堆信息(在Stack Overflow和其他方面),关于如何在Python中使用+或+=连接它是一种非常低效和糟糕的做法.

我似乎无法找到为什么+=这么低效.除了这里提到"它在某些情况下已经优化了20%的改进"(仍然不清楚这些情况是什么),我找不到任何其他信息.

在更技术层面上发生了什么,''.join()优于其他Python串联方法？

Answer 1

假设你有这个代码来构建一个来自三个字符串的字符串:

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

在这种情况下,Python首先需要在分配和创建'foobar'之前进行分配和创建'foobarbaz'.

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

有了.join,Python可以发挥一些技巧,因为不需要创建中间字符串.CPython预先计算出需要多少内存,然后分配一个正确大小的缓冲区.最后,它然后将每个片段复制到新缓冲区中,这意味着每个片段只复制一次.

+=在某些情况下,还有其他可行的方法可以带来更好的性能.例如,如果内部字符串表示实际上是一个rope或者运行时实际上足够聪明,以某种方式弄清楚临时字符串对程序没用,并优化它们.

但是,CPython肯定不能可靠地进行这些优化(虽然它可能适用于一些极端情况)并且因为它是最常用的实现,所以许多最佳实践都基于对CPython有效的方法.拥有一套标准化的规范也使其他实现更容易集中他们的优化工作.

Answer 2

我认为在Lua的字符串缓冲区章节中最好地解释了这种行为.

要在Python的上下文中重写该解释,让我们从一个无辜的代码片段开始(Lua的docs的衍生物):

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

假设每个l都是20个字节,s并且已经解析为50 KB的大小.当Python连接时,s + l它会创建一个包含50,020字节的新字符串,并将50 KB复制s到此新字符串中.也就是说,对于每个新行,程序移动50 KB的内存,并且不断增长.在阅读了100个新行(仅2 KB)之后,该代码段已经移动了超过5 MB的内存.更糟糕的是,在任务完成后

s += l

旧字符串现在是垃圾.在两个循环周期之后,有两个旧字符串总共产生超过100 KB的垃圾.因此,语言编译器决定运行其垃圾收集器并释放那些100 KB.问题是这将每两个周期发生一次,程序将在读取整个列表之前运行其垃圾收集器两千次.即使完成所有这些工作,其内存使用量也将是列表大小的倍数.

并且,最后:

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

Python字符串也是不可变对象.