Python 字符串连接内部细节

Question

假设我们有一个字符串列表，我们想通过连接该列表中的所有元素来创建一个字符串。像这样：

def foo(str_lst):
    result = ''
    for element in str_lst:
        result += element
    return result

由于字符串是不可变对象，我希望 python 创建一个新的 str 对象并在每次迭代时复制 result 和 element 的内容。它使得 O(M * N^2) 时间复杂度，M 是每个元素的长度，N 是列表的大小。

然而，我的实验表明它以线性时间运行。

N = 1000000 # 1 million
str_lst = ['a' for _ in range(N)]

foo(str_lst) # It takes around 0.5 seconds

N = 2000000 # 2 million
str_lst = ['a' for _ in range(N)]

foo(str_lst) # It takes around 1.0 seconds

N = 10000000 # 10 million
str_lst = ['a' for _ in range(N)]

foo(str_lst) # It takes around 5.3 seconds

我怀疑 python 在后台使用了类似 stringbuffer 的东西。因此，它不会在每次迭代时创建新对象。

现在考虑一个稍微不同的实现。唯一的区别是一项额外的作业。

def foo2(str_lst):
    result = ''
    for element in str_lst:
        result += element
        temp = result # new added line
    return result

我知道 temp = result 行不会创建新对象。 temp 只是指向同一个对象。所以，这个小改动应该不会对性能产生太大影响。

N = 1000000 # 1 million
str_lst = ['a' for _ in range(N)]
foo(str_lst) # It takes around 0.5 seconds
foo2(str_lst) # It takes around 30 seconds

N = 2000000 # 2 million
str_lst = ['a' for _ in range(N)]
foo(str_lst) # It takes around 1 seconds
foo2(str_lst) # It takes around 129 seconds

但是，有很大的不同。看起来 foo2 函数是 O(N^2) 而 foo 是 O(N)。

我的问题是 python 如何在不破坏不可变对象赋值等其他语言组件的情况下实现字符串连接的线性时间？那条额外的线是如何影响性能的呢？我在 cpython 实现中搜索了一下，但找不到确切位置。

更新

这是线路分析结果。

foo 函数的结果

Total time: 0.545577 s
File: <ipython-input-38-b9bb169e8fe0>
Function: foo at line 1

Line #      Hits         Time  Per Hit   % Time  Line Contents
==============================================================
 1                                           def foo(str_lst):
 2         1          2.0      2.0      0.0      result = ''
 3   1000001     238820.0      0.2     43.8      for element in str_lst:
 4   1000000     306755.0      0.3     56.2          result += element
 5         1          0.0      0.0      0.0      return result

foo2 函数的结果

Total time: 30.6663 s
File: <ipython-input-40-34dd53670dd9>
Function: foo2 at line 1
Line #      Hits         Time  Per Hit   % Time  Line Contents
==============================================================
 1                                           def foo2(str_lst):
 2         1          2.0      2.0      0.0      result = ''
 3   1000001     299122.0      0.3      1.0      for element in str_lst:
 4   1000000   30033127.0     30.0     97.7          result += element
 5   1000000     413283.0      0.4      1.3          temp = result
 6         1          0.0      0.0      0.0      return result

temp = result 行以某种方式影响了 result += element 行的性能。

Answer 1

让另一个名称指向同一个对象会破坏优化。优化基本上通过 resizing the string object 和附加到位来工作。如果对该对象有多个引用，则无法在不影响其他引用的情况下调整大小。由于字符串是不可变的，允许这将是实现的一个严重缺陷。

temp = result

增加了对result命名的字符串对象的引用计数，从而禁止优化。

在 += 情况下执行的完整检查列表（最终转化为 PyUnicode_Append) can be seen in the unicode_modifiable 函数。除其他外，它检查对象的引用计数是否等于 1，它不是 interned 也不是字符串子类。

如果您想要更详尽的列表，the if statement 中还有更多检查来保护此优化。

虽然这不是您问题的基本问题，但未来的读者可能会对如何有效地执行字符串连接感到好奇。除了 S.O 上的类似问题，Python FAQ also has an entry 上的

Answer 2

实际上，您观察到的行为是由 OS.

上 C-运行time 的内存分配器的行为决定的

CPython 有一个优化，如果 unicode-object 只有一个引用，它可以就地更改 - 没有人会注册 unicode-object 暂时失去其不变性。有关更多详细信息，请参阅我的回答。

在 foo2 中，还有另一个对 unicode 对象的引用 (temp)，它阻止了就地优化：就地更改它会破坏不变性，因为它可以通过 temp.

观察

然而，即使使用就地优化，为什么可以避免 O(n^2) 行为并不明显，因为 unicode 对象不会过度分配，因此必须在每次添加时扩展底层缓冲区，这很天真将意味着在每个步骤中复制全部内容（即 O(n)）。

然而，大多数时候 realloc（不同于 malloc+copy）可以在 O(1) 中完成，因为如果分配缓冲区后面的内存是空闲的，无需复制即可用于扩展原件

一个有趣的细节是，无法保证 foo 会在 O(n) 中运行：如果内存碎片化（例如在长时间的运行ning过程）。 realloc 将无法在不复制数据的情况下扩展缓冲区，因此运行ning 时间将变为 O(n^2)。

因此不应依赖此优化来避免二次运行宁时间。

Python 字符串连接内部细节

Python string concatenation internal details

python

python-3.x

string

cpython

python-internals