为什么join比正常连接更快

Question

我已经看到了来自不同语言的几个例子,这些例子毫不含糊地证明了连接列表(数组)的元素比连接字符串要快一些.不幸的是我没有找到解释原因？有人可以解释在两种操作下都能运行的内部算法,为什么这种算法比另一种更快.

这是我的意思的python示例:

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

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

谢谢提前)

Answer 1

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

另一方面,字符串上的单个+ =操作别无选择,只能为最终字符串分配足够的内存,而最终字符串只是两个字符串的串联.后续+ =必须相同,每个分配内存,在下一个+ =将被丢弃.每次将不断增长的字符串从内存中的一个位置复制到另一个位置.

Answer 2

原因是Python(以及许多其他语言)中的字符串是不可变对象 - 也就是说,一旦创建,它们就无法更改.相反,连接一个字符串实际上会产生一个新字符串,该字符串由两个较小字符串的内容组成,然后将旧字符串替换为新字符串.

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