4

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

“将字符串构建为列表并在末尾使用 ''.join。join 是在分隔符上调用的字符串方法，而不是列表。从空字符串调用它会连接没有分隔符的片段，这是 Python 的怪癖，而不是一开始很惊讶。这很重要：用 + 构建字符串是二次时间而不是线性时间！如果你学了一个习语，就学这个。

错误：对于字符串中的 s：result += 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是二次时间吗？

4

5 回答 5

14

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

但是每次你a + b在 Python 中处理字符串时，它都会导致一个新的分配，然后将所有字节从 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 秒。

于 2009-12-28T02:27:02.483 回答
6

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

于 2009-12-28T02:24:10.597 回答
4

编码时s1 + s2，Python 需要分配一个新的字符串对象，将 的所有字符复制s1到其中，然后复制 . 的所有字符s2。这个微不足道的操作不承担二次时间成本：成本是O(len(s1) + len(s2))（加上一个用于分配的常数，但这在 big-O 中不存在；-）。

但是，请考虑您给出的报价中的代码：for s in strings: result += s.

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

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

于 2009-12-28T02:28:58.127 回答
1

Joel 在Back to Basics中对此进行了描述。

于 2009-12-28T02:34:33.653 回答
0

如果您指的是与其他人相同的事情，这并不明显。当您有很多字符串时，这种优化很重要，比如长度为N的M。然后

一种 

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

乙

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

除非通过实现进行优化，否则A在总长度上是线性的，T = M*N而B总是T*T / N更差并且大致是二次的 if M >> N。

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

于 2009-12-28T02:23:15.373 回答