假设我们有一个字符串列表，我们想通过连接这个列表中的所有元素来创建一个字符串。像这样:
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 行的性能。
最佳答案
让另一个名称指向同一个对象会破坏优化。优化基本上通过 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对此。
关于Python 字符串连接内部细节，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/55063068/