13

我已经看到了来自不同语言的几个示例，这些示例明确地证明了连接列表（数组）的元素比仅连接字符串要快几倍。不幸的是，我没有找到解释为什么？有人可以解释在这两种操作下都有效的内部算法，以及为什么一种比另一种更快。

这是我的意思的python示例：

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

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

谢谢提前）

4

7 回答 7

15

连接函数中的代码预先知道它被要求连接的所有字符串以及这些字符串有多大，因此它可以在开始操作之前计算最终的字符串长度。因此，它只需要为最终字符串分配一次内存，然后它就可以将每个源字符串（和分隔符）放置在内存中的正确位置。

另一方面，对字符串的单个 += 操作别无选择，只能为最终字符串分配足够的内存，即两个字符串的串联。随后的 += 必须做同样的事情，每个分配的内存在下一个 += 将被丢弃。每次不断增长的字符串从内存中的一个地方复制到另一个地方。

于 2010-02-24T09:52:31.023 回答
14

原因是 Python（和许多其他语言）中的字符串是不可变的对象——也就是说，一旦创建，它们就无法更改。相反，连接一个字符串实际上会生成一个新字符串，该字符串由连接的两个较小字符串的内容组成，然后用新字符串替换旧字符串。

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

于 2010-02-24T09:51:52.333 回答
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
于 2010-02-24T09:51:00.383 回答
3

请参阅python 字符串连接性能和一个很好地描述它的特定 anwser：

建议是关于连接很多字符串。

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

1）使用+。一个新的字符串 s1+s2 被创建，然后一个新的字符串 s1+s2+s3 被创建，……等等，因此涉及到大量的内存分配和复制操作。实际上，s1 被复制了 n-1 次，s2 被复制了 n-2 次，...，等等。

2) 使用 "".join([s1,s2,...,sn])。连接是一次性完成的，字符串中的每个字符只复制一次。

于 2010-02-24T09:53:54.780 回答
1

其他回复基本上已经涵盖了它，但如果你想要更多细节，Joel Spolsky 有一篇文章，他描述了“画家施莱米尔的算法”，这非常相关，很好地说明了为什么要理解这种低级实现细节即使您使用 Python 这样的高级语言，这仍然非常重要。

于 2010-02-24T15:23:53.777 回答
0

好吧，这在很大程度上取决于语言，但总的来说，一个大操作比许多小操作快。在您的第二个示例中，连接知道它必须连接的所有元素，因此可以分配必要的资源并将字符放入。第一个示例中的连接必须在每一步重新分配资源（最坏的情况）。

于 2010-02-24T09:50:35.583 回答
0

我不知道 join 的内部结构，但在第一个版本中，每次调用 += 运算符时都会创建一个新字符串。由于字符串是不可变的，因此每次分配新内存并制作副本时。

现在，连接（这是一个字符串方法）只能进行一次分配，因为它可以预先计算大小。

于 2010-02-24T09:51:43.100 回答