为什么在Python中字符串拼接的顺序会极大地影响速度？

Question

我通过调试代码找到了这个问题。我有一个字符串消息列表，想要将它们连接在一起，并在每条消息末尾添加换行符。

方法1：

total_str = ""
for m in messages:
    total_str = total_str + m + "\n"

这非常慢 - 在大约第100,000条消息后，每添加一条消息需要大约2-3秒钟，在第300,000条消息左右，这个过程基本上停止了。

方法2：

total_str = ""
for m in messages:
    tmp = m + "\n"
    total_str = total_str + tmp

这种方法在不到一秒的时间内就完成了对160万条消息的拼接。

我想知道的是，为什么第二种方法比第一种方法快得多？

- Jihan Yin

---

奖励：total_str += m + '\n'比第一种方法更快。 - Aran-Fey

https://docs.python.org/3/library/stdtypes.html#str.join - Stephen Rauch

你的实现存在与在循环中连接不可变字符串相关的性能问题；行为是多项式时间。然而，我怀疑CPython运行时中的Peephole优化器能够优化使用临时变量的版本。这是一个不应该被依赖的实现细节。使用messages.append("")，然后'\n'.join(messages)。 - juanpa.arrivillaga

@juanpa.arrivillaga 我认为这不是一种优化，恰恰相反。CPython愚蠢到将a + b + c解释为(a + b) + c，这会导致长字符串a被复制两次。（而a + (b + c)只需要复制一次） - Aran-Fey

Answer 1

a + b + c不是将a、b和c连接成一个字符串的单个操作。它实际上是两个操作，分别是t = a + b 和 t + c，这意味着将a的内容复制两次；一次是将a复制到t中，另一次是当t被复制到t + c的结果中时再次复制。由于在您的示例中，a是保持变长的字符串，因此每一步最好只复制一份数据。

最好的方法是避免使用+创建所有临时字符串对象，并使用join：

total_str = "\n".join(messages)

join 直接操作每个字符串，而不需要逐个迭代地将它们附加到初始空字符串中。通过扫描 messages，join 可以确定结果字符串的长度，为其分配足够的内存，然后逐个将数据从 messages 的每个元素顺序复制到指定位置。

- chepner

---

很好的回答，除了a + b必须创建a的副本这一点并不那么明显。您可能需要更详细地解释一下这部分内容。 - Aran-Fey

Answer 2

好的，由于执行 a = a + b + c 时会被解释为 a = (a + b) + c，因此可以看出计算顺序如下：

• tmp_1 = a + b。这需要复制巨大的字符串 a，因为字符串是不可变的。
• a = tmp_1 + c。这需要复制（更大的）巨大字符串 tmp_1，因为字符串是不可变的。

所以，在第二个版本中，a = a + tmp（就像您第二个示例中的那样），只需要进行一个这样的复制，而在第一个版本中则涉及两个巨大的复制。显然，后一种方法将更快。

- ForceBru

Answer 3

Python中的字符串是不可变且连续的。前者意味着它们无法被修改，后者意味着它们存储在内存中的一个位置。这与诸如绳数据结构之类的情况不同，其中附加数据是一项廉价操作，只需要为末尾形成一个新节点。这意味着每次连接操作必须复制两个输入字符串，并且使用类似total_str = total_str + m + "\n"这样的东西，因为+是左相关} }，会将所有total_str复制两次。通常的解决方案是保留所有小字符串，直到整个集合完成，然后使用{{link4:str.join执行一次连接。这只会将每个组件字符串复制一次，而不是成比例（与平方成正比）的几次。另一种选项是在进行操作时构建缓冲区，可以使用io.StringIO。这将给您一个类似于其他语言中的StringBuilder的文件对象，从中可以提取最终字符串。我们还有像writelines之类的操作，可以接受迭代器，因此可能根本不需要连接。

我猜第二个实现之所以能够快得多（不仅是两倍），是因为有一些优化措施可以使CPython有时根本不需要执行左操作数的复制。PyUnicode_Append似乎正好有这样的优化，基于unicode_modifiable，如果引用计数恰好为1，字符串从未被哈希过，并且满足其他一些条件，则它可以改变一个对象。这通常适用于您使用+=的局部变量，并且假定编译器在没有第二个运算符的同一赋值中生成了这种行为。

- Yann Vernier