为什么“join”比普通连接更快？

Question

我看到了来自不同编程语言的多个示例，明确证明连接列表（数组）元素比仅串联字符串快很多。为什么？

这两种操作下的内部算法是什么，为什么其中一种更快？

以下是一个Python示例：

# This is slow
x = 'a'
x += 'b'
...
x += 'z'

# This is fast
x = ['a', 'b', ... 'z']
x = ''.join(x)

- Ilian Iliev

---

当你阅读 str.join 的代码时，你学到了什么？ - S.Lott

很抱歉，我不理解这个问题。 - Ilian Iliev

这是源代码链接：http://svn.python.org/view/python/trunk/Objects/stringobject.c?view=markup。当你阅读join的源代码时，你学到了什么关于`join`的速度？ - S.Lott

Answer 1

原因是Python（以及许多其他语言）中的字符串是不可变对象，即一旦创建，就不能更改。相反地，将字符串连接起来实际上会生成一个新的字符串，该字符串由连接的两个较小字符串的内容组成，然后用新字符串替换旧的字符串。

由于创建一个字符串需要一定的时间（需要分配内存，将字符串的内容复制到该内存中等），因此制作许多字符串比制作单个字符串需要更长的时间。 在这个过程中，进行N次连接需要创建N个新字符串。 另一方面，join()只需创建一个字符串（即最终结果），因此运行速度更快。

- Amber

Answer 2

在join函数中的代码提前知道所有需要连接的字符串以及这些字符串的大小，因此它可以在操作开始之前计算出最终字符串的长度。

因此，它只需要为最终字符串分配一次内存，然后就可以将每个源字符串（和分隔符）放置在内存中的正确位置。

另一方面，对字符串进行单个+=操作只能简单地为最终字符串分配足够的内存，该字符串是仅由两个字符串连接而成的。随后的+=操作必须执行相同的操作，每次都会分配内存，并且下一个+=操作将丢弃之前分配的内存。每次不断增长的字符串都会从一处内存复制到另一处内存。

- AnthonyWJones

Answer 3

这是因为字符串拼接需要分配更大的内存空间:

x = 'a' # String of size 1 allocated
x += 'b' # String of size 2 allocated, x copied, and 'b' added. Old x discarded
x += 'b' # String of size 3 allocated, x copied, and 'c' added. Old x discarded
x += 'b' # String of size 4 allocated, x copied, and 'd' added. Old x discarded
x += 'b' # String of size 5 allocated, x copied, and 'e' added. Old x discarded

所以发生的情况是你进行了大量的分配和复制，但随后又将它们丢弃。非常浪费。

x = ['a', 'b', ..., 'z'] # 26 small allocations
x = ''.join(x) # A single, large allocation

- Ignacio Vazquez-Abrams

---

如果您提到不可变对象，我会给您点赞。并非所有语言在连接字符串时都需要丢弃现有的字符串。 - Amber

Answer 4

请参阅Python字符串连接性能和一个特定的回答，其中描述得非常好：

该建议是关于连接大量字符串的。

要计算s = s1 + s2 + ... + sn，

1. 使用+。创建新字符串s1+s2，然后创建新字符串s1+s2+s3，等等，因此涉及许多内存分配和复制操作。实际上，s1被复制n-1次，s2被复制n-2次，...等等。
2. 使用"".join([s1，s2，...，sn]）。连接在一遍完成，并且每个字符串中的每个字符只复制一次。

- Leo

Answer 5

其他回答已经基本涵盖了它，但如果您想要更多细节，Joel Spolsky有一篇文章，其中描述了“Schlemiel画家算法”，这非常相关，并且很好地阐述了为什么即使在像Python这样的高级语言中工作，理解这种低级实现细节仍然非常重要。

- thraxil

---

是的，随着列表变得越来越长和性能影响变得更加严重，这是最重要的方面。 - Peter Mortensen

Answer 6

嗯，这严重依赖于编程语言，但通常的想法是：一个大操作比许多小操作更快。

在您的第二个示例中，联接知道要联接的所有元素，因此只需分配必要的资源并将字符放入其中。

在您的第一个示例中进行串联时，需要在每个步骤（最坏情况）重新分配资源。

- Björn Pollex

Answer 7

我不清楚 join 的内部工作原理，但在第一个版本中，每次调用 += 运算符时都会创建一个新的字符串。由于字符串是不可变的，因此每次都会分配新的内存并进行复制。

现在，join（它是一个字符串方法）只需要进行一次分配，因为它可以预先计算出大小。

- kgiannakakis