为什么天真的字符串连接在一定长度之上变成二次方？

Question

通过重复的字符串连接来构建字符串是一种反模式,但我仍然很好奇为什么它的性能在字符串长度超过大约10**6后从线性切换到二次方:

# this will take time linear in n with the optimization
# and quadratic time without the optimization
import time
start = time.perf_counter()
s = ''
for i in range(n):
    s += 'a'
total_time = time.perf_counter() - start
time_per_iteration = total_time / n

例如,在我的机器上(Windows 10,python 3.6.1):

• 因为10 ** 4 < n < 10 ** 6,time_per_iteration几乎完全恒定在170±10μs
• 因为10 ** 6 < n,time_per_iteration几乎是完全线性的,达到520μs n == 10 ** 7.

线性增长time_per_iteration相当于二次增长total_time.

线性复杂性来自最近的CPython版本(2.4+)中的优化,如果没有对原始对象的引用,则重用原始存储.但我预计线性性能会无限期地持续下去,而不是在某个时刻切换到二次方.

我的问题是基于这个评论.出于某种奇怪的原因跑步

python -m timeit -s"s=''" "for i in range(10**7):s+='a'"

需要非常长的时间(比二次方长得多),所以我从来没有得到实际的时间结果timeit.因此,我使用上面的简单循环来获得性能数字.

更新:

我的问题可能也被标题为" 如果没有过度分配,列表如何append具有O(1)性能？".从观察time_per_iteration小型字符串的常量开始,我认为字符串优化必须过度分配.但是realloc(对我来说意外)在扩展小内存块时非常成功地避免了内存复制.

Answer 1

最后,平台C分配器(如malloc())是最终的内存源.当CPython尝试重新分配字符串空间以扩展其大小时,系统C realloc()确实会确定所发生的细节.如果字符串开头是"短"的,那么系统分配器找到与其相邻的未使用内存的可能性是不错的,因此扩展大小只是C库的分配器更新某些指针的问题.但这种重复若干次(在平台的C分配器的细节同样取决于)后,它会耗尽空间.此时,realloc()将需要将整个字符串复制到一个全新的更大的可用内存块.这是二次时间行为的来源.

请注意,例如,增长Python列表面临着相同的权衡.但是,列表是为了增长而设计的,因此CPython故意要求的内存比当时实际需要的内存多.随着列表的增长,这种分配的数量会增加,足以使得realloc()需要复制整个列表的情况很少- 到目前为止.但是字符串优化不会过度分配,因此realloc()需要复制的情况要频繁得多.