Python 字符串连接惯用语。需要澄清。

Question

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

“将字符串构建为列表并使用 ''.在最后加入。 join 是一个字符串 在分隔符上调用的方法，而不是 名单。从空处呼唤它 字符串连接没有的片段 分隔符，这是 Python 的一个怪癖 起初相当令人惊讶。这是 重要：用 + 构建字符串是 二次时间而不是线性时间！如果 你学一种习语，就学这个。

错误：对于字符串中的 s：结果 += s

右：结果 = ''.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

是的。对于您选择的示例，重要性尚不清楚，因为您只有两个非常短的字符串，因此附加可能会更快。

但每次在 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 秒。

Answer 2

重复串联是二次的，因为它是 Schlemiel the Painter 算法（请注意，某些实现会优化此算法）远离，使其不是二次的）。 join 避免了这种情况，因为它需要整个字符串列表，分配必要的空间并一次性完成连接。

Answer 3

当您编写s1 + s2时，Python需要分配一个新的字符串对象，将s1的所有字符复制到其中，然后将s2的所有字符复制到其中代码>.这个简单的操作不承担二次时间成本：成本是O(len(s1) + len(s2))（加上一个用于分配的常量，但这不在big-O中计算； -)。

但是，请考虑您给出的引用中的代码：for s in strings: result += s。

这里，每次添加一个新s，所有之前的都必须首先复制到新分配的空间中以获取结果 （字符串是不可变的，因此必须进行新的分配和复制）。假设你有 N 个长度为 L 的字符串：第一次复制 L 个字符，第二次复制 2 * L，第三次复制 3 * L...总之，这使得它 L * N * (N+1) / 2 个字符被复制...所以，是的，它是 N

的二次算法。在其他一些情况下，对于足够小的 N 值，二次算法可能比线性算法更快（因为乘数和固定固定成本可能要小得多）；但这里的情况并非如此，因为分配成本很高（直接和间接，因为内存碎片的可能性）。相比之下，将字符串累积到列表中的开销基本上可以忽略不计。

Answer 4

Joel 在回归基础中对此进行了介绍。

Answer 5

如果您指的是与其他人相同的事物，那就不太明显了。当您有许多个字符串时，例如长度为N的M，这种优化非常重要。那么

A

x = ''.join(strings) # Takes M*N operations 

B

x = ''
for s in strings:
    x = x + s  # Takes N + 2*N + ... + M*N operations

除非通过实现进行优化，是的，A 与总长度呈线性 T = M*N 和 B 是 T*T / N，如果 M >>> ，它总是更差并且大致是二次方。 N。

现在为什么join实际上非常直观：当您说“我有一些字符串”时，通常可以通过说您有一个返回字符串的迭代器来形式化。现在，这正是您传递给 "string".join() 的内容