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

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

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

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

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

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

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

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

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

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

Иначе было бы небезопасно менять s.

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

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

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

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

Вы можете легко проверить, сколько перераспределений действительно требует копии, проверив, как часто меняется идентификатор (потому что _ 8_ в 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 (lists намеренно перераспределены, поэтому 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()

Обратите внимание, что ось абсцисс представляет количество «сделанных копий», а не размер строки!

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

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

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

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

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

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

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