Python 字符串连接习惯用法，需澄清。

Question

来自 http://jaynes.colorado.edu/PythonIdioms.html

“构建字符串时，先把它们放在一个列表里，最后用 ''.join 来连接。join 是一个字符串的方法，它是用分隔符来调用的，而不是列表。用空字符串来调用它时，会把这些部分直接连接在一起，没有任何分隔符，这在 Python 中是个小特点，刚开始可能会让人感到惊讶。这一点很重要：用 + 来拼接字符串的效率是平方级别的，而不是线性级别的！如果你只学会一个技巧，那就学这个吧。

错误的写法：for s in strings: result += s

正确的写法：result = ''.join(strings)

我不太明白为什么这样做是对的。如果我有一些字符串想要连接，对我来说，把它们放在一个列表里再调用 ''.join 并不是直观的好方法。把它们放进列表里难道不会增加一些开销吗？为了澄清一下……

Python 命令行：

>>> str1 = 'Not'
>>> str2 = 'Cool'
>>> str3 = ''.join([str1, ' ', str2]) #The more efficient way **A**
>>> print str3
Not Cool
>>> str3 = str1 + ' ' + str2 #The bad way **B**
>>> print str3
Not Cool

难道 A 真的是线性时间，而 B 是平方时间吗？

Answer 1

当你写 s1 + s2 这段代码时，Python需要先创建一个新的字符串对象，然后把 s1 的所有字符复制到这个新对象里，接着再把 s2 的所有字符也复制进去。这个看似简单的操作其实并不会消耗太多时间，时间复杂度是 O(len(s1) + len(s2))（再加上一些分配内存的常量，但这在大O表示法中不算）。

不过，想想你提到的这段代码： for s in strings: result += s。

在这里，每次添加一个新的 s 时，之前的所有字符都必须先被复制到为 result 新分配的空间里（因为字符串是不可变的，所以必须进行新的分配和复制）。假设你有 N 个长度为 L 的字符串：第一次复制 L 个字符，第二次复制 2 * L 个字符，第三次复制 3 * L 个字符……总共要复制的字符数是 L * N * (N+1) / 2，所以，这样的操作时间复杂度是 N 的平方。

在某些情况下，对于较小的 N 值，平方级别的算法可能会比线性级别的算法快（因为乘数和固定的常量可能会小得多）；但在这里并不是这样，因为内存分配的成本很高（直接的成本和间接的成本，比如可能导致内存碎片）。相比之下，把字符串累积到一个列表中的开销几乎可以忽略不计。

Answer 2

重复地把字符串拼接在一起会变得很慢，这是因为它遵循了一个叫做“施莱米尔画家的算法”的方法（有些实现会优化这个过程，所以不会变得那么慢）。而使用 join 方法就不会有这个问题，因为它会先把所有的字符串放在一起，分配好需要的空间，然后一次性完成拼接。

Answer 3

没错。对于你选择的例子，重要性不太明显，因为你只有两个很短的字符串，所以用拼接的方法可能会更快。

但是，每次在Python中用 a + b 拼接字符串时，都会新建一个空间，然后把a和b的所有字节复制到这个新字符串里。如果你在一个循环中处理很多字符串，这些字节就得一次又一次地复制，而且每次复制的内容会越来越多。这就导致了效率变得很低。

另一方面，创建一个字符串列表并不会复制字符串的内容，而只是复制了它们的引用。这种做法非常快，运行时间是线性的。接着，使用join方法只需进行一次内存分配，并且每个字符串只复制到正确的位置一次。这同样也是线性的时间。

所以，如果你可能要处理很多字符串，建议使用 ''.join 这种写法。对于只有两个字符串的情况，使用哪种方法都没关系。

如果你还不太相信，可以自己试试用10M字符创建一个字符串：

>>> chars = ['a'] * 10000000
>>> r = ''
>>> for c in chars: r += c
>>> print len(r)

对比一下：

>>> chars = ['a'] * 10000000
>>> r = ''.join(chars)
>>> print len(r)

第一种方法大约需要10秒，第二种方法不到1秒。