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

Question

我能够在线找到大量关于在Python中使用+或+=进行字符串连接是非常低效和不良做法的信息（在Stack Overflow和其他地方）。

但我似乎找不到+=为什么如此低效的原因。除了提到这里有一些情况下会有20%的优化（不清楚是哪些情况），我找不到任何额外的信息。

在更深层次上，''.join()相对于其他Python连接方法的优势是什么？

- Rodney Wells

---

相关。https://dev59.com/zFsX5IYBdhLWcg3wS9w7 - OneCricketeer

+= 在处理字符串和整数时表现不同。Python 可能需要更长时间来确定 += 操作的数据类型，如整数则为加法，如果是字符串则为连接。而在 ' '.join() 操作中，它仅期望字符串元素 - 这使得 Python 不必担心处理的数据类型。 - stuartnox

@cricket_007提供了一个很棒的帖子，提供了更多的见解。然而，我已经接受了mgilson的答案。 - Rodney Wells

@BryanOakley 没有想到查看源代码。这是解决问题的另一个好方法。 - Rodney Wells

当你试图理解大量使用字符串连接操作符 += 的潜在性能成本时，可以阅读 Shlemiel the painter的故事（最初在这里讲述：http://www.joelonsoftware.com/articles/fog0000000319.html）。尽管 Python 中 += 的确切原因可能与 C 中的 strcat 的 O(N) 复杂度不完全相同，但两者有些相似之处。 - Blckknght

Answer 1

假设您有以下代码，从三个字符串构建一个字符串：

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

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

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

使用 .join，Python 可以玩一些技巧，因为不需要创建中间字符串。CPython 事先确定它需要多少内存，然后分配一个正确大小的缓冲区。最后，它将每个部分复制到新缓冲区中，这意味着每个部分只复制一次。

---

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

然而，CPython确实不可靠地执行这些优化（尽管它在一些边缘案例中可能会这样做），由于它是最常用的实现，许多最佳实践都是基于对CPython的良好适应。拥有一个标准化的规范集也使得其他实现更容易集中他们的优化努力。

- mgilson

---

当我第一次阅读您的答案时，我想：“翻译器如何知道它需要为'foobar'分配空间？它是读取我的思维，知道我将在某个时候加入它们吗？”我认为您假设存在像foo += bar + baz这样的代码。如果您展示会导致分配的代码，那么您的答案可能更有意义。 - Bryan Oakley

@BryanOakley: foo += bar; foo += baz;的行为与这篇文章描述的完全相同。foo = foo + bar + baz;也一样。foo += bar + baz的行为略有不同，但速度并没有更快。 - Mooing Duck

@MooingDuck：我明白。但这不是重点。重点是，原问题和答案都没有展示foo += bar这个表达式。初学者可能会被这个答案绊倒，并想知道为什么Python在没有表达式的情况下分配了空间给“foobar”。 - Bryan Oakley

“@Random832 -- 它确实是真的。join 确实会通过输入两次。它通过在第一次运行之前从输入创建一个序列来实现这一点。” - mgilson

@freakish -- FWIW，至少在Stackoverflow上有很好的文档说明，连接列表推导式比连接生成器表达式稍微快一些。然而，现实世界中的时间差异是非常微小的，因此我不同意哪种方式更受欢迎（例如，我从未在样式指南中看到过它）。个人而言，我通常仍然使用生成器以保持与我编写的其他代码的一致性，但在代码审查中，当我不会让像sum([x for x in ...])这样的东西通过时（为什么浪费内存？）... - mgilson

Answer 2

我认为这种行为最好通过 Lua 的字符串缓冲区章节 来解释。

为了在 Python 的上下文中重新编写该解释，让我们从一个无害的代码片段开始（该代码是 Lua 文档中的一个衍生版本）：

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

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

最后：

这个问题不仅仅出现在Lua上：其他具有真正垃圾回收机制且字符串是不可变对象的语言也呈现类似的行为，Java是其中最著名的例子。（Java提供了StringBuffer结构来改善这个问题。）

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

- hjpotter92

---

值得注意的是，CPython（主要的Python解释器）在处理不可变字符串方面有一点欺骗性（这就是之前提到的“优化”）。如果它看到你使用+=，并且左边的名称绑定到一个只有一个引用的字符串，它会尝试原地调整该字符串的缓冲区大小（根据一些底层内存分配细节，这可能起作用或者不起作用）。当它起作用时，它可以使重复的+=操作更快（实际上，使用带有+=的循环可能比使用"".join更快）。不使用它的主要原因是为了跨解释器兼容性。 - Blckknght

LuaJIT 对这种循环轻松应对，我真的怀疑你在这里能得到超过2-3个分配。不过，我很乐意被证明是错误的。 - Benjamin Gruenbaum

@Blckknght，您能详细解释一下“跨解释器兼容性”吗？ - laike9m

@Blckknght，那么您认为接受的答案怎么样？它说：“因此，对于每个+=被调用的操作，字符串的全部内容以及要添加到其中的任何内容都需要复制到全新的内存缓冲区中。”。 - laike9m