Что такое динамический массив

В предыдущем модуле мы видели: классический массив — это блок фиксированного размера. Расширить его нельзя — только выделить новый, скопировать всё и освободить старый. Это и есть realloc.

Динамический массив (Python list, Java ArrayList, C++ std::vector) — это надстройка над массивом, которая автоматизирует realloc и даёт пользователю иллюзию «бесконечной» структуры с быстрым доступом по индексу. Внутри это всё та же пара (буфер, длина), но с третьим полем — capacity (ёмкость буфера). Когда длина достигает capacity, происходит resize.

Главный вопрос дизайнера динамического массива: на сколько увеличивать буфер, когда он переполнился? Это и есть стратегия роста, и она определяет всю экономику структуры.

Три классических множителя

В реальных реализациях множитель — это вещественное число между 1 и 2:

Чем больше множитель, тем реже realloc, но тем больше «лишней» памяти. Это базовый trade-off.

Зачем именно геометрический рост

Если бы мы росли арифметически (на +const за раз) — каждый append стоил бы O(n), потому что каждый realloc копирует весь буфер, и таких realloc будет N штук на N append. Суммарно — O(n^2).

Если растём геометрически (×k для k > 1) — количество resize за N операций будет log_k(N). На каждом resize копируем текущий буфер. Сумма копирований — геометрическая прогрессия: n + n/k + n/k^2 + … = n * k/(k-1). Это O(n), а в среднем на операцию — O(1). И именно это даёт амортизированный O(1) для append.

Множитель k влияет на константу в этой O(1): чем k больше, тем константа меньше (реже копирование), но тем больше памяти впустую.

Аналитика: «лишняя» память

Возьмём множитель k=2 (классический vector). После последнего удвоения буфер размера 2N, в нём лежит N элементов. Половина пустая. Но в среднем по жизни массива — сколько пустоты?

Если длина равномерно распределена между N и 2N (длина растёт линейно), средняя пустота = N/2 / средний размер ((N + 2N)/2 = 1.5N) = N/2 / 1.5N = 1/3. То есть 33% буфера в среднем впустую.

Для k=1.5: после resize буфер 1.5N, лежит N элементов; пустота 0.5N. Средний размер ≈ 1.25N. Пустота 0.5N/1.25N = 40%? Подождите — это пиковая. А средняя: 0.25N / 1.25N = 20%.

Для k=1.125 (CPython): после resize буфер ~1.125N, пустота 0.125N. Средняя пустота ~6%.

Эти числа — почему Python с x1.125 экономит память лучше всех. У Python каждый элемент list дорогой (см. модуль 4), поэтому держать ещё 50% «впрок» — расточительно.

Microsoft Visual C++ и проблема in-place расширения

Один из аргументов в пользу x1.5 (вместо x2): при некоторых параметрах аллокатора можно переиспользовать освобождающуюся память для следующего resize. Если каждый раз новый буфер вдвое больше прошлого, освобождённые блоки слишком маленькие, чтобы вместить будущий. Если рост ×1.5, есть шанс, что после нескольких resize сумма освобождённых буферов покроет нужный размер. Это «теоретический» аргумент, на практике зависит от аллокатора.

Поэтому MSVC long ago пошёл с x1.5. libc++/libstdc++ остались с x2. Java с самого начала была x1.5 (более «академический» выбор). Python выбрал минималистичный x1.125.

Влияние выбора на DE-нагрузку

Где это важно junior DE?

1. Память. Если вы строите большой буфер событий в python, list с x1.125 даст до 10% оверхеда на буфер указателей — не страшно. В Java тот же ArrayList съест до 50% впустую — это уже видно при загрузке 10M записей в RAM.

2. Realloc spike. Реже resize = реже спайки латенси. На load-test с p99 SLA Java и C++ выигрывают, потому что между resize они держат больше запаса.

3. Предсказуемость. Когда вы знаете финальный размер заранее, предаллокация всегда лучше любого growth-factor: ни одного resize. ArrayList(initialCapacity), vector::reserve(n), xs = [None] * N.

Реальный замер: память list vs numpy.array

import sys
import numpy as np

# Python list растёт по x1.125
N = 1_000_000
xs = []
for i in range(N):
    xs.append(i)

list_bytes = sys.getsizeof(xs)
list_per_elem = list_bytes / N

# numpy.array с pre-allocation
arr = np.empty(N, dtype='int64')
for i in range(N):
    arr[i] = i

# но это не main use case numpy
print(f"list:       size={list_bytes:>12,} bytes  per_elem={list_per_elem:.2f}")
print(f"numpy(int64): size={arr.nbytes:>12,} bytes  per_elem={arr.itemsize:.2f}")

Получится примерно:

list:         size=   8,448,728 bytes  per_elem=8.45
numpy(int64): size=   8,000,000 bytes  per_elem=8.00

list 8.45 байт/элемент vs numpy 8.00 — разница 5-6% (это та самая x1.125 в действии). На Java ArrayList аналогичный замер дал бы 12.0 байт/элемент при том же количестве (50% overhead в момент сразу после resize).

Попробуй сам

Напишите функцию, которая фиксирует все ступени capacity при append:

import sys

def capacity_steps(N):
    """Вернёт список (len, capacity) на каждой ступени."""
    xs = []
    prev_cap = -1
    steps = []
    for i in range(1, N + 1):
        xs.append(i)
        cap = (sys.getsizeof(xs) - 56) // 8
        if cap != prev_cap:
            steps.append((i, cap))
            prev_cap = cap
    return steps

for length, cap in capacity_steps(10_000):
    growth = cap / (length - 1) if length > 1 else 1
    print(f"len={length:>5}  cap={cap:>5}  ratio={growth:.3f}")

Посмотрите, как ratio (cap/length) колеблется около 1.0-1.125. Это график вашей «избыточности».