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 实现中搜索了一些，但找不到确切的位置。

Answer 1

使用另一个名称指向同一个对象会终止优化。优化基本上通过调整字符串对象的大小并附加到位来工作。如果对该对象有多个引用，则无法在不影响另一个引用的情况下调整大小。由于字符串是不可变的，因此允许这将是实现的一个严重缺陷。temp = result增加了名为 by 的字符串对象的引用计数，result从而禁止优化。在+=( 最终转换为PyUnicode_Append)的情况下执行的检查的完整列表可以在unicode_modifiable函数中看到。除其他外，它会检查对象的引用计数是否等于 1，它没有被实习，并且它不是字符串子类。如果您想要更完整的列表，则在保护此优化的if语句中还有一些检查。虽然不是您问题的基本问题，但未来的读者可能会对如何有效地执行字符串连接感到好奇。除了关于 SO 的类似问题外，Python FAQ 也有关于此的条目。

Answer 2

实际上，您观察到的行为由操作系统上 C 运行时的内存分配器的行为决定。CPython 有一个优化，如果 unicode-object 只有一个引用，它可以就地更改 - 没有人会注意到 unicode-object 会暂时失去其不变性。有关更多详细信息，请参阅我对此问题的回答。在 中foo2，还有另一个对 unicode 对象 ( temp) 的引用，它阻止了就地优化：就地更改它会破坏不变性，因为它可以通过 观察到temp。然而，即使进行了就地优化，也不清楚为什么O(n^2)可以避免行为，因为 unicode 对象不会过度分配，因此必须在每次添加时扩展底层缓冲区，这天真地意味着整个内容的副本（即O(n)) 在每一步。但是，大多数时候realloc（不同于malloc+copy）可以在 中完成O(1)，因为如果直接在分配的缓冲区后面的内存是空闲的，它可以用于扩展原始而不进行复制。一个有趣的细节是，不能保证它foo会在O(n)以下情况下运行：如果内存是碎片化的（例如，在一个长时间运行的进程中）。realloc不复制数据将无法扩展缓冲区，因此运行时间将变为O(n^2).因此，不应依赖这种优化来避免二次运行时间。