Python 字符串连接内部细节

Question

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

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

由于字符串是不可变对象(immutable对象)，我希望 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 如何在不破坏不可变对象(immutable对象)分配等其他语言组件的情况下实现字符串连接的线性时间？那条额外的线是如何影响性能的呢？我在 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 )可以在 unicode_modifiable 中看到功能。除其他事项外，它检查对象的引用计数是否等于 1、它不是 interned 以及它不是字符串子类。

the if statement 中还有几项检查如果您想要更详尽的列表，请注意此优化。

---

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