Почему наивная конкатенация строк становится квадратичной над определенной длиной?

Построение строки путем повторной конкатенации строк является анти-шаблоном, но мне все же интересно, почему его производительность переключается с линейного на квадратичный после длины строки, превышающей приблизительно 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 мкс
для 10 ** 6 < n, time_per_iteration почти идеально линейна, достигая 520 мкс при n == 10 ** 7.

Линейный рост в time_per_iteration эквивалентен квадратичному росту в total_time.

Линейная сложность получается из optimization в более поздних версиях CPython (2.4+), которые повторно использовать исходное хранилище, если ссылки на исходный объект не оставлены. Но я ожидал, что линейная производительность будет продолжаться бесконечно, а не переключиться на квадратичную в какой-то момент.

Мой вопрос основан на этом комментарии. По какой-то нечетной причине запуск

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

занимает невероятно долгое время (гораздо длиннее квадратичного), поэтому я никогда не получал фактические результаты времени от timeit. Поэтому вместо этого я использовал простой цикл, как указано выше, для получения номеров производительности.

Update:

Мой вопрос также может быть озаглавлен "Как может показаться append в списках append без перераспределения?". Из наблюдаемой константы time_per_iteration для малогабаритных строк я предположил, что оптимизация строк должна быть чрезмерно распределена. Но realloc (неожиданно для меня) довольно успешно избегает копирования памяти при расширении небольших блоков памяти.

Ответ 1

В конце концов, распределители платформы C (например, malloc()) являются основным источником памяти. Когда CPython пытается перераспределить пространственное пространство, чтобы расширить его размер, на самом деле система C realloc() определяет детали происходящего. Если строка начинается с "короткой", вероятность того, что системный распределитель найдет неиспользуемую память рядом с ней, поэтому расширение размера - это просто вопрос, когда распределитель библиотеки C обновляет некоторые указатели. Но после повторения этого количества раз (в зависимости от деталей распределителя платформы C), он будет исчерпан. В этот момент realloc() нужно будет скопировать всю строку до совершенно нового блока памяти. Это источник квадратично-временного поведения.

Обратите внимание, например, что рост списка Python сталкивается с теми же компромиссами. Тем не менее, списки предназначены для выращивания, поэтому CPython намеренно запрашивает больше памяти, чем это действительно необходимо в то время. Объем этого обсчета увеличивается с увеличением списка, что позволяет сделать его редким, чтобы realloc() нужно было скопировать весь список - так далеко. Но оптимизация строк не перекрывается, что делает случаи, когда realloc() нужно копировать гораздо чаще.

Ответ 2

[XXXXXXXXXXXXXXXXXX............]
 \________________/\__________/
     used space      reserved
                      space

При увеличении структуры массива смежных массивов (проиллюстрировано выше) посредством добавления к нему линейная производительность может быть достигнута, если дополнительное пространство, зарезервированное при перераспределении массива, пропорционально текущему размеру массива. Очевидно, что для больших строк эта стратегия не соблюдается, скорее всего, с целью не тратить слишком много памяти. Вместо этого фиксированное количество дополнительного места резервируется во время каждого перераспределения, что приводит к квадратичной временной сложности. Чтобы понять, откуда возникает квадратичная производительность в последнем случае, представьте, что вообще не выполняется никакого общего назначения (что является граничным случаем этой стратегии). Затем на каждой итерации должно выполняться перераспределение (требующее линейного времени), а полная продолжительность выполнения - квадратичная.

Ответ 3

TL; DR: Просто потому, что конкатенация строк оптимизирована при определенных обстоятельствах, это не означает, что она обязательно O(1), это не всегда O(n). То, что определяет производительность, является ультимативно вашей системой, и это может быть умным (остерегайтесь!). Списки, которые "garantuee" амортизируют операции добавления O(1), все еще намного быстрее и лучше, избегая перераспределения.

Это чрезвычайно сложная проблема, потому что трудно "измерить количественно". Если вы прочтете объявление:

Конкретности строк в операторах формы s = s + "abc" и s += "abc" теперь выполняются более эффективно при определенных обстоятельствах.

Если вы более подробно рассмотрите это, вы заметите, что в нем упоминаются "определенные обстоятельства". Трудность заключается в том, чтобы выяснить, каковы эти определенные условия. Одно из них очевидно:

Если что-то еще содержит ссылку на исходную строку.

В противном случае было бы безопасно изменить s.

Но другое условие:

Если система может выполнить перераспределение в O(1) - это означает, что вам не нужно копировать содержимое строки в новое место.

Это было сложно. Потому что система отвечает за перераспределение. Это то, что вы можете контролировать изнутри python. Однако ваша система умна. Это означает, что во многих случаях вы действительно можете перераспределить, не копируя содержимое. Возможно, вы захотите взглянуть на ответ @TimPeters, который объясняет некоторые из них более подробно.

Я подхожу к этой проблеме с точки зрения экспериментаторов.

Вы можете легко проверить, сколько перераспределений действительно нуждается в копировании, проверяя, как часто изменяется идентификатор (потому что функция id в CPython возвращает адрес памяти):

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 на моем компьютере.

Но если вы думаете, что действительно хорошо "избегаете" копий, вы ошибаетесь. Если вы сравните его с количеством изменений размера 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 может быть умным, и я намеренно сохранял "размеры", когда перераспределения произошли в списке. Многие распределители 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 представляет количество выполненных "копий", а не размер строки!

Этот график был действительно очень интересен для меня, потому что он показывает четкие шаблоны: для небольших массивов (до 465 элементов) этапы являются постоянными. Он должен перераспределить для каждого 8 добавленных элементов. Затем ему нужно на самом деле выделить новый массив для каждого добавленного символа, а затем примерно в 940 все ставки будут удалены до (примерно) миллиона элементов. Тогда, кажется, он выделяет в блоках 4096 байт.

Моя догадка заключается в том, что распределитель C использует разные схемы распределения для объектов различного размера. Маленькие объекты выделяются в блоках по 8 байт, затем для массивов большего размера, чем мелкие, но все еще мелкие, он останавливается, чтобы засечь, а затем для средних массивов он, вероятно, позиционирует их там, где они "могут поместиться". Затем для огромных (сравнительно говоря) массивов он выделяет в блоках 4096 байт.

Я думаю, что 8 байтов и 4096 байт не являются случайными. 8 байтов - это размер int64 (или float64 aka double), и я нахожусь на 64-битном компьютере с питоном, скомпилированным для 64 бит. И 4096 - это размер страницы моего компьютера. Я предполагаю, что существует множество "объектов", которые нуждаются в таких размерах, поэтому имеет смысл, что компилятор использует эти размеры, поскольку он может избежать фрагментации памяти.

Вероятно, вы знаете, но только для того, чтобы убедиться: для приложенного поведения O(1) (амортизированного) общееобложение должно зависеть от размера. Если общее значение будет постоянным, оно будет O(n**2) (чем больше общее значение, тем меньше постоянный коэффициент, но он все еще квадратичен).

Итак, на моем компьютере поведение во время выполнения всегда будет O(n**2) за исключением длин (примерно) от 1 000 до 1 000 000 - там действительно кажется undefined. В моем тестовом прогоне он смог добавить много (десяти-) тысяч элементов, не нуждающихся в копии, поэтому, если это было время, оно будет выглядеть "O(1)".

Обратите внимание, что это только моя система. Это может выглядеть совершенно иначе на другом компьютере или даже с другим компилятором на моем компьютере. Не воспринимайте их слишком серьезно. Я предоставил код, чтобы делать сюжеты самостоятельно, поэтому вы можете сами проанализировать свою систему.

Вы также задали вопрос (в комментариях), если будут недостатки, если вы перераспределите строки. Это очень просто: строки неизменны. Таким образом, любой обобщенный байт расходует ресурсы. Есть только несколько ограниченных случаев, когда они действительно растут, и они рассматриваются как детали реализации. Разработчики, вероятно, не выбрасывают пространство, чтобы детали реализации выполнялись лучше, Некоторые разработчики python также считают, что добавление этой оптимизации было плохим решением.