为什么朴素的字符串连接在一定长度以上会变成二次方？
Why does naive string concatenation become quadratic above a certain length?
通过重复的字符串连接构建一个字符串是一个anti-pattern，但我仍然很好奇为什么它的性能在字符串长度超过大约 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 几乎是完全线性的，在 n == 10 ** 7 处达到 520 µs。
time_per_iteration 的线性增长等同于 total_time 的二次增长。
如果没有对原始 object 的引用，则 optimization in the more recent CPython versions (2.4+) that reuse the original storage 会产生线性复杂度。但我预计线性性能会无限期地持续下去，而不是在某个时候切换到二次方。
我的问题是基于 this comment 提出的。出于某种奇怪的原因 运行
python -m timeit -s"s=''" "for i in range(10**7):s+='a'"
需要非常长的时间（比二次方长得多），所以我从来没有从 timeit 得到实际的计时结果。因此，我使用上面的简单循环来获取性能数据。
更新：
我的问题还不如标题为 "How can a list-like append have O(1) performance without over-allocation?"。通过观察 small-size 字符串上的常量 time_per_iteration，我假设字符串优化必须是 over-allocating。但是 realloc 在扩展小内存块时（出乎我的意料）在避免内存复制方面非常成功。
[XXXXXXXXXXXXXXXXXX............]
\________________/\__________/
used space reserved
space
当通过附加到连续数组数据结构（如上所示）时，如果在重新分配数组时保留的额外 space 与数组的当前大小成比例，则可以实现线性性能。显然，对于大字符串，不遵循这种策略，很可能是为了不浪费太多内存。相反，在每次重新分配期间都会保留固定数量的额外 space，从而导致二次时间复杂度。要了解后一种情况下二次性能的来源，请假设根本没有执行过度分配（这是该策略的边界情况）。然后在每次迭代中必须执行重新分配（需要线性时间），并且完整的运行时间是二次的。
最后，平台 C 分配器（如 malloc()）是内存的最终来源。当 CPython 试图重新分配字符串 space 以扩展其大小时，实际上是系统 C realloc() 决定了发生的细节。如果字符串以 "short" 开头，系统分配器很可能会找到与其相邻的未使用内存，因此扩展大小只是 C 库的分配器更新一些指针的问题。但是在重复多次之后（再次取决于平台 C 分配器的详细信息），它 will 运行 out of space。到那时，realloc() 将需要将整个字符串复制到一个全新的更大的空闲内存块中。这就是二次时间行为的来源。
请注意，例如，增加 Python 列表面临相同的权衡。然而，列表是设计的，因此 CPython 故意要求比当时实际需要更多的内存。随着列表的增长，这种过度分配的数量会增加，足以使 realloc() 很少需要复制整个列表。但是字符串优化不会过度分配，使得 realloc() 需要更频繁地复制的情况。
TL;DR：仅仅因为字符串连接在某些情况下被优化并不意味着它一定是 O(1)，它并不总是 O(n)。最终决定性能的是您的系统，它可能是智能的（注意！）。 "garantuee" 分摊 O(1) 追加操作的列表在避免重新分配方面仍然更快更好。
这是一个极其复杂的问题，因为很难"measure quantitativly"。如果您阅读公告：
String concatenations in statements of the form s = s + "abc" and s += "abc" are now performed more efficiently in certain circumstances.
如果您仔细查看它，您会注意到它提到了 "certain circumstances"。棘手的事情是找出这些特定情况是什么。一个是显而易见的：
- 如果其他东西持有对原始字符串的引用。
否则改s.
不安全
但另一个条件是：
- 如果系统可以在
O(1) 中进行重新分配 - 这意味着无需将字符串的内容复制到新位置。
那就是它变得棘手了。因为系统负责做一个重新分配。这不是您可以从 python 中控制的。但是你的系统很聪明。这意味着在许多情况下您实际上可以进行重新分配而无需复制内容。 .
我将从实验者的角度来解决这个问题。
您可以通过检查 ID 更改的频率（因为 CPython 中的 id 函数 returns 内存地址）来轻松检查实际需要复制多少次重新分配：
changes = []
s = ''
changes.append((0, id(s)))
for i in range(10000):
s += 'a'
if id(s) != changes[-1][1]:
changes.append((len(s), id(s)))
print(len(changes))
每个 运行（或几乎每个 运行）给出不同的数字。在我的电脑上大约有 500 个。即使 range(10000000) 在我的电脑上也只有 5000。
但是，如果您认为 "avoiding" 副本真的很棒，那您就错了。如果将它与 list 需要的调整大小数量进行比较（list 有意过度分配，因此 append 被摊销 O(1)）：
import sys
changes = []
s = []
changes.append((0, sys.getsizeof(s)))
for i in range(10000000):
s.append(1)
if sys.getsizeof(s) != changes[-1][1]:
changes.append((len(s), sys.getsizeof(s)))
len(changes)
只需要 105 次重新分配（总是）。
我提到 realloc 可能很聪明，当重新分配发生在列表中时，我有意保留了 "sizes"。许多 C 分配器试图避免内存碎片，至少在我的计算机上，分配器会根据当前大小做一些不同的事情：
# changes is the one from the 10 million character run
%matplotlib notebook # requires IPython!
import matplotlib.pyplot as plt
import numpy as np
fig = plt.figure(1)
ax = plt.subplot(111)
#ax.plot(sizes, num_changes, label='str')
ax.scatter(np.arange(len(changes)-1),
np.diff([i[0] for i in changes]), # plotting the difference!
s=5, c='red',
label='measured')
ax.plot(np.arange(len(changes)-1),
[8]*(len(changes)-1),
ls='dashed', c='black',
label='8 bytes')
ax.plot(np.arange(len(changes)-1),
[4096]*(len(changes)-1),
ls='dotted', c='black',
label='4096 bytes')
ax.set_xscale('log')
ax.set_yscale('log')
ax.set_xlabel('x-th copy')
ax.set_ylabel('characters added before a copy is needed')
ax.legend()
plt.tight_layout()
注意x轴代表的是"copies done"个数不是字符串的大小！
该图对我来说实际上非常有趣，因为它显示了清晰的模式：对于小型数组（最多 465 个元素），步骤是恒定的。它需要为每添加 8 个元素重新分配。然后它需要为每个添加的字符实际分配一个新数组，然后在大约 940 个字符时所有赌注都关闭，直到（大约）一百万个元素。然后它似乎以 4096 字节的块分配。
我的猜测是 C 分配器对不同大小的对象使用不同的分配方案。小对象以 8 字节的块分配，然后对于大于小但仍然小的数组，它停止过度分配，然后对于中等大小的数组，它可能将它们定位在 "may fit" 的位置。然后对于巨大的（相对而言）数组，它以 4096 字节的块分配。
我猜 8 字节和 4096 字节不是随机的。 8 个字节是 int64（或 float64 又名 double）的大小，我在一台 64 位计算机上 python 编译为 64 位。 4096 是我电脑的页面大小。我假设有很多 "objects" 需要这些大小，因此编译器使用这些大小是有道理的，因为它可以避免内存碎片。
您可能知道，但只是为了确保：对于 O(1)（摊销）追加行为，过度分配必须取决于大小。如果过度分配是常数，它将是 O(n**2)（过度分配越大，常数因子越小，但它仍然是二次方的）。
所以在我的计算机上，运行时间行为将始终是 O(n**2) 除了长度（大约）1 000 到 1 000 000 - 它似乎确实未定义。在我的测试中 运行 它能够添加许多（一万）个元素而无需副本，因此它可能会 "look like O(1)" 计时。
请注意，这只是我的系统。它可能在另一台计算机上看起来完全不同，甚至在我的计算机上使用另一个编译器。不要把这些看得太严重。我提供了自己做图的代码，所以你可以自己分析你的系统。
您还问了这个问题（在评论中）如果过度分配字符串是否会有缺点。这真的很简单：字符串是不可变的。所以任何过度分配的字节都是在浪费资源。只有少数情况下它确实会增长，这些被认为是实现细节。开发人员可能不会丢弃 space 以使实现细节表现得更好，some python developers also think that adding this optimization was a bad idea.
通过重复的字符串连接构建一个字符串是一个anti-pattern，但我仍然很好奇为什么它的性能在字符串长度超过大约 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几乎是完全线性的，在n == 10 ** 7处达到 520 µs。
time_per_iteration 的线性增长等同于 total_time 的二次增长。
如果没有对原始 object 的引用，则 optimization in the more recent CPython versions (2.4+) that reuse the original storage 会产生线性复杂度。但我预计线性性能会无限期地持续下去，而不是在某个时候切换到二次方。
我的问题是基于 this comment 提出的。出于某种奇怪的原因 运行
python -m timeit -s"s=''" "for i in range(10**7):s+='a'"
需要非常长的时间（比二次方长得多），所以我从来没有从 timeit 得到实际的计时结果。因此，我使用上面的简单循环来获取性能数据。
更新：
我的问题还不如标题为 "How can a list-like append have O(1) performance without over-allocation?"。通过观察 small-size 字符串上的常量 time_per_iteration，我假设字符串优化必须是 over-allocating。但是 realloc 在扩展小内存块时（出乎我的意料）在避免内存复制方面非常成功。
[XXXXXXXXXXXXXXXXXX............]
\________________/\__________/
used space reserved
space
当通过附加到连续数组数据结构（如上所示）时，如果在重新分配数组时保留的额外 space 与数组的当前大小成比例，则可以实现线性性能。显然，对于大字符串，不遵循这种策略，很可能是为了不浪费太多内存。相反，在每次重新分配期间都会保留固定数量的额外 space，从而导致二次时间复杂度。要了解后一种情况下二次性能的来源，请假设根本没有执行过度分配（这是该策略的边界情况）。然后在每次迭代中必须执行重新分配（需要线性时间），并且完整的运行时间是二次的。
最后，平台 C 分配器（如 malloc()）是内存的最终来源。当 CPython 试图重新分配字符串 space 以扩展其大小时，实际上是系统 C realloc() 决定了发生的细节。如果字符串以 "short" 开头，系统分配器很可能会找到与其相邻的未使用内存，因此扩展大小只是 C 库的分配器更新一些指针的问题。但是在重复多次之后（再次取决于平台 C 分配器的详细信息），它 will 运行 out of space。到那时，realloc() 将需要将整个字符串复制到一个全新的更大的空闲内存块中。这就是二次时间行为的来源。
请注意，例如，增加 Python 列表面临相同的权衡。然而，列表是设计的，因此 CPython 故意要求比当时实际需要更多的内存。随着列表的增长，这种过度分配的数量会增加，足以使 realloc() 很少需要复制整个列表。但是字符串优化不会过度分配，使得 realloc() 需要更频繁地复制的情况。
TL;DR：仅仅因为字符串连接在某些情况下被优化并不意味着它一定是 O(1)，它并不总是 O(n)。最终决定性能的是您的系统，它可能是智能的（注意！）。 "garantuee" 分摊 O(1) 追加操作的列表在避免重新分配方面仍然更快更好。
这是一个极其复杂的问题，因为很难"measure quantitativly"。如果您阅读公告：
String concatenations in statements of the form
s = s + "abc"ands += "abc"are now performed more efficiently in certain circumstances.
如果您仔细查看它，您会注意到它提到了 "certain circumstances"。棘手的事情是找出这些特定情况是什么。一个是显而易见的：
- 如果其他东西持有对原始字符串的引用。
否则改s.
但另一个条件是：
- 如果系统可以在
O(1)中进行重新分配 - 这意味着无需将字符串的内容复制到新位置。
那就是它变得棘手了。因为系统负责做一个重新分配。这不是您可以从 python 中控制的。但是你的系统很聪明。这意味着在许多情况下您实际上可以进行重新分配而无需复制内容。
我将从实验者的角度来解决这个问题。
您可以通过检查 ID 更改的频率（因为 CPython 中的 id 函数 returns 内存地址）来轻松检查实际需要复制多少次重新分配：
changes = []
s = ''
changes.append((0, id(s)))
for i in range(10000):
s += 'a'
if id(s) != changes[-1][1]:
changes.append((len(s), id(s)))
print(len(changes))
每个 运行（或几乎每个 运行）给出不同的数字。在我的电脑上大约有 500 个。即使 range(10000000) 在我的电脑上也只有 5000。
但是，如果您认为 "avoiding" 副本真的很棒，那您就错了。如果将它与 list 需要的调整大小数量进行比较（list 有意过度分配，因此 append 被摊销 O(1)）：
import sys
changes = []
s = []
changes.append((0, sys.getsizeof(s)))
for i in range(10000000):
s.append(1)
if sys.getsizeof(s) != changes[-1][1]:
changes.append((len(s), sys.getsizeof(s)))
len(changes)
只需要 105 次重新分配（总是）。
我提到 realloc 可能很聪明，当重新分配发生在列表中时，我有意保留了 "sizes"。许多 C 分配器试图避免内存碎片，至少在我的计算机上，分配器会根据当前大小做一些不同的事情：
# changes is the one from the 10 million character run
%matplotlib notebook # requires IPython!
import matplotlib.pyplot as plt
import numpy as np
fig = plt.figure(1)
ax = plt.subplot(111)
#ax.plot(sizes, num_changes, label='str')
ax.scatter(np.arange(len(changes)-1),
np.diff([i[0] for i in changes]), # plotting the difference!
s=5, c='red',
label='measured')
ax.plot(np.arange(len(changes)-1),
[8]*(len(changes)-1),
ls='dashed', c='black',
label='8 bytes')
ax.plot(np.arange(len(changes)-1),
[4096]*(len(changes)-1),
ls='dotted', c='black',
label='4096 bytes')
ax.set_xscale('log')
ax.set_yscale('log')
ax.set_xlabel('x-th copy')
ax.set_ylabel('characters added before a copy is needed')
ax.legend()
plt.tight_layout()
注意x轴代表的是"copies done"个数不是字符串的大小！
该图对我来说实际上非常有趣，因为它显示了清晰的模式：对于小型数组（最多 465 个元素），步骤是恒定的。它需要为每添加 8 个元素重新分配。然后它需要为每个添加的字符实际分配一个新数组，然后在大约 940 个字符时所有赌注都关闭，直到（大约）一百万个元素。然后它似乎以 4096 字节的块分配。
我的猜测是 C 分配器对不同大小的对象使用不同的分配方案。小对象以 8 字节的块分配，然后对于大于小但仍然小的数组，它停止过度分配，然后对于中等大小的数组，它可能将它们定位在 "may fit" 的位置。然后对于巨大的（相对而言）数组，它以 4096 字节的块分配。
我猜 8 字节和 4096 字节不是随机的。 8 个字节是 int64（或 float64 又名 double）的大小，我在一台 64 位计算机上 python 编译为 64 位。 4096 是我电脑的页面大小。我假设有很多 "objects" 需要这些大小，因此编译器使用这些大小是有道理的，因为它可以避免内存碎片。
您可能知道，但只是为了确保：对于 O(1)（摊销）追加行为，过度分配必须取决于大小。如果过度分配是常数，它将是 O(n**2)（过度分配越大，常数因子越小，但它仍然是二次方的）。
所以在我的计算机上，运行时间行为将始终是 O(n**2) 除了长度（大约）1 000 到 1 000 000 - 它似乎确实未定义。在我的测试中 运行 它能够添加许多（一万）个元素而无需副本，因此它可能会 "look like O(1)" 计时。
请注意，这只是我的系统。它可能在另一台计算机上看起来完全不同，甚至在我的计算机上使用另一个编译器。不要把这些看得太严重。我提供了自己做图的代码，所以你可以自己分析你的系统。
您还问了这个问题（在评论中）如果过度分配字符串是否会有缺点。这真的很简单：字符串是不可变的。所以任何过度分配的字节都是在浪费资源。只有少数情况下它确实会增长，这些被认为是实现细节。开发人员可能不会丢弃 space 以使实现细节表现得更好，some python developers also think that adding this optimization was a bad idea.