Каков коэффициент изменения размеров списков в Python?

Question

Например, ArrayList в Java имеет коэффициент изменения размера 2. Когда массив, в который обернут ArrayList, заканчивается пространство, все элементы этого массива переносятся в новый массив, равный 2 умноженный на размер исходного массива.

Поскольку списки / массивы Python являются естественно динамическими, каковы их размеры? Или они используют какой-то другой метод масштабирования? Если так, что это за метод? Каково его асимптотическое время выполнения (большое О)?

Answer 1

Чтобы ответить на ваш другой вопрос: добавление элемента в конец ArrayList или аналогичного занимает амортизированное O (1) время, пока существует любой коэффициент k> 1 таким образом, что перераспределение всегда создает массив, который в k раз больше предыдущего.

Фактический используемый фактор не имеет большого значения, если он больше единицы. Альтернативные схемы перераспределения могут иметь различную сложность. Если перераспределение добавляет, например, постоянную сумму, то добавление элемента занимает амортизированное O (N) время.

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

Допустим, вы используете коэффициент k и только что выполнили перераспределение Nth . Это означает, что вы добавили около k ^ N предметов. Сколько предметов вы скопировали? Пусть будет C . Тогда:

C = k ^ (N-1) + k (N-2) + ... + 1

kC - C = k ^ N + k ^ (N-1) - k ^ (N-1) + k ^ (N-2) - k ^ (N-2) ... - 1

кС - C = k ^ N - 1

C = (k ^ N-1) / (k-1)

Количество копий на каждый добавленный элемент , затем C / K ^ N , что в значительной степени 1 / (k-1) .

Таким образом, коэффициент Java k = 2 означает, что на одну операцию добавления приходится около одной копии, с количеством неиспользуемых слотов до 50% , а коэффициент CPython k = 1,125. означает, что на операцию добавления приходится около 8 копий с количеством неиспользуемых слотов до 11% .

Answer 2

В частности, для CPython перераспределение во время изменения размера реализовано в objects / listobject.c . Это описано как

мягкий, но ... достаточно, чтобы дать амортизированное поведение в течение линейного времени для длинной последовательности appends () в присутствии плохо работающей системы realloc ().

Когда список необходимо увеличить, он увеличивается примерно до 112,5% от необходимого размера. В частности, фактический размер составляет new_size + new_size >> 3 + (newsize < 9 ? 3 : 6).