字符串串联以防止两个字符串在内存中移动

Question

为了连接两个字符串，内存管理器将尝试重新分配一个字符串的内存位置，以便另一个字符串能够适应内存中紧挨着它的另一个字符串。 /sf/answers/2380573961/迭代字符串追加的时间复杂度实际上是 O(n^2) 还是 O(n)？ 如果它不能就地重新分配，那么它必须将两者都移动到一个新的内存位置。

问题是为了避免将两个字符串移动到新内存位置的这种开销，是否有一种首选的、有效的方法在 Python 中连接两个字符串。我正在考虑使用 StringIO 使其成为文本缓冲区？你怎么看？

Answer 1

对于两个字符串，big-O 无关紧要，因为您无法对其进行改进。a + b很好；您无法摊销增长，因此您可以将它们连接起来，为新字符串执行一次分配，并将两份复制到该单一分配中，每个来源一份。

对于大量字符串，标准的 Python 方法是创建一个tuple（对于同时已知的许多字符串）或list（对于一组零碎构建的字符串）并调用''.join(seq)它。str.join计算所有输入的组合长度，为结果预分配缓冲区，并将每个组件一个接一个地复制到该缓冲区中，保持运行时O(n)。

您可以使用io.StringIO来实现类似的效果，但这不是必需的，并且在幕后，它必须执行类似的工作来构建 alist和joining 它。