假设我们有一个字符串列表，我们想通过连接此列表中的所有元素来创建一个字符串。像这样的东西：
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线的表现。
具有指向同一对象的另一个名称会导致优化。优化基本上由resizing the string object工作并附加到位。如果您对该对象有多个引用，则无法在不影响其他引用的情况下调整大小。由于字符串是不可变的，允许这将是实现的严重缺陷。
temp = result
增加了由result命名的字符串对象的引用计数，从而禁止优化。
在+=函数中可以看到在PyUnicode_Append（最终转换为unicode_modifiable）的情况下执行的完整检查列表。除此之外，它还检查对象的引用计数是否等于1，它是否未被实现，并且它不是字符串子类。
如果你想要一个更彻底的列表，那么在the if statement中还有一些检查这个优化的检查。
虽然不是你问题的基本问题，但未来的读者可能会对如何有效地执行字符串连接感到好奇。除了关于S.O的类似问题，Python FAQ also has an entry就此问题。
实际上，您观察到的行为取决于操作系统上C运行时的内存分配器的行为。
CPython有一个优化，如果unicode-object只有一个引用，它可以就地更改 - 没有人会注册unicode-object暂时失去其不变性。有关详细信息，请参阅我的回答to this SO-question。
在foo2中，还有另一个对unicode对象（temp）的引用，它阻止了就地优化：就地改变它会破坏不变性，因为它可以通过temp观察到。
然而，即使使用inplace优化，也不明显，为什么O(n^2)行为可以避免，因为unicode对象没有进行全面定位，因此必须在每次添加时都释放底层缓冲区，这天真地意味着整个内容的副本（即O(n)）每一步。
但是，大多数情况下realloc（与malloc + copy不同）可以在O(1)中完成，因为如果直接在分配的缓冲区后面的内存是免费的，它可以用来扩展原始而不复制。
一个有趣的细节是，无法保证foo将在O(n)中运行：如果内存被激励（例如在长时间运行的过程中）。 realloc无法在不复制数据的情况下扩展缓冲区，因此运行时间将变为O(n^2)。
因此，不应该依赖于这种优化来避免二次运行时间。