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

使用另一个名称指向同一对象会破坏优化。优化基本上是通过调整字符串对象的大小并附加到适当位置来进行的。如果对该对象有多个引用，则不能在不影响另一引用的情况下调整大小。由于字符串是不可变的，因此这将是实现的严重缺陷。

temp = result

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

在的情况下执行的检查的完整列表+=（最终转换为PyUnicode_Append）可以在unicode_modifiable函数中看到。除其他事项外，它还会检查对象的引用计数是否等于1，没有被intern并且不是字符串子类。

如果您想要更详尽的清单，则可以在if声明中进行更多检查以保护这种优化。

尽管这不是您问题的基本问题，但未来的读者可能会对如何有效执行字符串连接感到好奇。除了关于SO的类似问题外，Python FAQ也对此进行了介绍。