В чём «амортизированный» подвох

В прошлом уроке мы видели: список не сразу растёт на 1 при каждом append. Он растёт «ступенями» — то 4, то 8, то 16. Между ступенями append — это запись + инкремент ob_size, дешёвая операция. А вот в момент ступени происходит realloc: выделяется новый, бо́льший буфер; все старые элементы копируются; старый освобождается.

Иными словами, один из миллиона append дорогой — O(n). Остальные дешёвые — O(1). Если усреднить по всей последовательности операций, получается амортизированный O(1): суммарная стоимость N вставок — линейная, O(N), значит на каждую — константа в среднем. Сейчас разберём почему именно так получается.

Как растёт CPython list

В файле Objects/listobject.c есть функция list_resize. В CPython 3.13 формула роста:

new_allocated = (size_t)newsize + (newsize >> 3) + (newsize < 9 ? 3 : 6);

Перевод на Python:

def new_allocated(newsize):
    growth = (newsize >> 3) + (3 if newsize < 9 else 6)
    return newsize + growth

То есть при росте до размера newsize CPython выделяет newsize * 1.125 + const. Это умеренный рост — примерно ×1.125, что меньше, чем у Java ArrayList (×1.5) или C++ std::vector (×2). Запас меньше — память экономится; зато ребалансировок чуть чаще.

Можно посмотреть фактические ступени capacity:

import sys

def capacity(xs):
    return (sys.getsizeof(xs) - 56) // 8  # 56 — header PyListObject, 8 — указатель

xs = []
prev = -1
for i in range(1, 2001):
    xs.append(i)
    cap = capacity(xs)
    if cap != prev:
        print(f"len={i:>4}  capacity={cap:>4}")
        prev = cap

Получим (CPython 3.13):

len=   1  capacity=   4
len=   5  capacity=   8
len=   9  capacity=  16
len=  17  capacity=  24
len=  25  capacity=  32
len=  33  capacity=  40
len=  41  capacity=  52
...
len=1769  capacity=1996
len=1997  capacity=2248

Видно: ступеньки сначала маленькие (4, 8, 16, 24, 32), потом примерно на 12% больше каждый раз.

Доказательство: банковский метод

Идея банковского метода: каждой дешёвой операции даём «лишнюю монетку» (запас), чтобы потом «оплатить» дорогую. Если на каждый append выдавать константное количество монет, и этих монет хватает на все будущие resize — значит, amortized стоимость каждого append константна.

Пусть рост — ×2 (для простоты). Цена операции:

• дешёвый append (есть место): 1 единица работы.
• resize при росте от n до 2n: n единиц работы (надо скопировать n элементов).

Берём с каждого append по 3 единицы:

• 1 единица — собственно вставка.
• 1 единица — резерв на «оплату» собственного будущего копирования.
• 1 единица — резерв на «оплату» копирования элемента-«дублёра».

Когда буфер размера n полон, мы сделали n дешёвых append после прошлого resize. У нас на счету ~2n единиц резерва. Resize стоит n единиц. Резерва хватает с запасом.

Значит, amortized cost = 3 единицы = O(1). Это и есть формальное доказательство, что несмотря на дорогие resize, в среднем append константен.

Реальные измерения: 1M append

Проверим на timeit. Будем добавлять элементы в чистый список и измерять полное время:

import time

def measure_append(n):
    xs = []
    t0 = time.perf_counter()
    for i in range(n):
        xs.append(i)
    t1 = time.perf_counter()
    return t1 - t0

for n in [10_000, 100_000, 1_000_000, 10_000_000]:
    t = measure_append(n)
    per_op_ns = (t / n) * 1e9
    print(f"n={n:>10,}  total={t*1000:>7.2f} ms  per op={per_op_ns:>6.1f} ns")

На обычном ноуте (Apple M-серии, CPython 3.13):

n=    10,000  total=   0.45 ms  per op=  45.0 ns
n=   100,000  total=   4.20 ms  per op=  42.0 ns
n= 1,000,000  total=  42.10 ms  per op=  42.1 ns
n=10,000,000  total= 425.00 ms  per op=  42.5 ns

Время на операцию стабильно ~42 нс, не растёт с n. Это и есть amortized O(1) глазами: общее время растёт линейно, на операцию — константа.

Сравните с popleft из list (O(n) на каждую операцию):

def measure_popleft(n):
    xs = list(range(n))
    t0 = time.perf_counter()
    while xs:
        xs.pop(0)
    t1 = time.perf_counter()
    return t1 - t0

for n in [1000, 10_000, 100_000]:
    t = measure_popleft(n)
    print(f"n={n:>10,}  total={t*1000:>10.2f} ms")

n=     1,000  total=      0.30 ms
n=    10,000  total=     16.50 ms     # x55, не x10!
n=   100,000  total=   1620.00 ms     # x100 от 10k — это O(n) на вызов

Видно квадратичный рост: x10 в n даёт x100 в времени. Это потому что каждый pop(0) сдвигает все оставшиеся элементы — O(n) per call, итого O(n^2) суммарно.

Когда амортизация ломается

Amortized O(1) — это среднее по последовательности. Если измерять отдельные операции, иногда вы попадёте на дорогую. Например, добавление миллионного элемента может включать копирование ~1M указателей — это микросекунды, на 5 порядков медленнее обычного append.

В реальной DE-системе это редко критично: пакетная обработка миллиардов записей не страдает от 100 дорогих append. Но в low-latency сервисе с p99 SLA — может: латенси «торчит» именно на этих spikes. Решение — резервировать ёмкость заранее:

# плохо для low-latency: возможны spike-resize
xs = []
for item in stream:
    xs.append(item)

# лучше: предаллоцировать
xs = [None] * EXPECTED_SIZE
i = 0
for item in stream:
    xs[i] = item
    i += 1

Или сразу строить через генератор-литерал — он внутри тоже делает resize, но за один проход, без python-loop overhead.

Сравнение стратегий роста

Все три стратегии дают amortized O(1). Различия — в trade-off: память против частоты resize. Python выбрал минимальный overhead памяти, потому что в python overhead на каждый объект и так огромный. Об этом — следующий модуль.

Попробуй сам

Запустите бенчмарк append и сравните результат на разных n. Также попробуйте этот вариант с резервированием:

import time

def measure_preallocated(n):
    xs = [None] * n
    t0 = time.perf_counter()
    for i in range(n):
        xs[i] = i
    t1 = time.perf_counter()
    return t1 - t0

def measure_append(n):
    xs = []
    t0 = time.perf_counter()
    for i in range(n):
        xs.append(i)
    t1 = time.perf_counter()
    return t1 - t0

n = 1_000_000
print(f"append:       {measure_append(n)*1000:>7.2f} ms")
print(f"preallocated: {measure_preallocated(n)*1000:>7.2f} ms")

Скорее всего, preallocated будет на 20-30% быстрее. Когда размер известен заранее — резервируйте.