为什么'join'比普通串联快？

Question

我看到过很多来自不同编程语言的例子，清楚地证明把列表（数组）里的元素连接起来，比单纯地拼接字符串要快很多倍。这是为什么呢？

这两种操作背后有什么样的算法？为什么一种比另一种更快呢？

下面是一个Python的例子，来说明我的意思：

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

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

Answer 1

请查看 Python 字符串连接性能，里面有一个特别好的回答：

这个建议是关于如何连接很多字符串的。

假设我们要计算 s = s1 + s2 + ... + sn，

1. 如果用 + 号连接。每次连接都会创建一个新的字符串，比如先创建 s1+s2，然后再创建 s1+s2+s3，依此类推。这就涉及到很多内存分配和复制操作。实际上，s1 会被复制 n-1 次，s2 会被复制 n-2 次，等等。

2. 如果用 "".join([s1,s2,...,sn])。这样连接只需要一次操作，每个字符串中的字符只会被复制一次。

Answer 2

原因在于，Python（以及很多其他编程语言）中的字符串是不可变对象，也就是说，一旦创建了字符串，就不能再改变它。每次你想把两个字符串拼在一起时，其实是生成了一个新的字符串，这个新字符串包含了你要拼接的两个小字符串的内容，然后用这个新字符串替换掉旧的字符串。

创建字符串需要一定的时间（要分配内存，把字符串的内容复制到那块内存等等），所以如果你要创建很多字符串，所花的时间就会比只创建一个字符串要长。做N次拼接就需要在这个过程中创建N个新字符串。而使用join()方法，只需要创建一个最终的字符串，因此速度会快很多。

Answer 3

在一个连接字符串的函数里，它一开始就知道要连接哪些字符串，以及这些字符串的大小，所以它可以在开始操作之前计算出最终字符串的长度。

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

而另一方面，单独使用 += 操作符来连接字符串时，就只能为最终的字符串分配足够的内存，这个字符串是由两个字符串连接而成的。之后的每一次 += 操作也必须这样做，每次都要分配内存，而在下一个 += 操作时，这些内存又会被丢弃。每次增长的字符串都要从内存的一个地方复制到另一个地方。