dynamic-array

Динамический массив

Предпосылки: массив (формула адреса, непрерывность, O(1) доступ по индексу, фиксированный размер).

Массив даёт O(1) доступ по индексу, но размер фиксирован при создании. Динамический массив (dynamic array, от греч. dynamis — способность к изменению) снимает это ограничение: элементы добавляются без заранее известного количества, а O(1) доступ по индексу сохраняется.

Операция	Сигнатура	Сложность
Получить элемент	get(i) → value	O(1)
Записать элемент	set(i, value)	O(1)
Добавить в конец	append(value)	O(1)*
Узнать размер	size() → n	O(1)

* — амортизированно: большинство операций O(1), редкие — O(n), но в среднем по серии — O(1). Механизм объясняется ниже.

В отличие от обычного массива, размер может расти.

Два параметра вместо одного

Внутри динамического массива — обычный статический массив, но с двумя величинами вместо одной: capacity (сколько места выделено) и length (сколько элементов реально используется).

Пока length < capacity, вставка в конец — O(1). Когда length == capacity — делаем resize.

Resize: механизм

Было:   capacity=4, length=4
        [A][B][C][D]    — массив полон

Хотим добавить E.

Шаг 1: Выделяем новый массив (обычно × 2)
        [_][_][_][_][_][_][_][_]   — capacity=8

Шаг 2: Копируем старые элементы
        [A][B][C][D][_][_][_][_]

Шаг 3: Освобождаем старый массив

Шаг 4: Добавляем новый элемент
        [A][B][C][D][E][_][_][_]   — length=5, capacity=8

Амортизация: почему append всё равно O(1)

Resize копирует все элементы — это O(n). Но если capacity удваивается при каждом resize, дорогие копирования случаются всё реже.

Шаг за шагом: 8 вставок с capacity=1

Вставка 1:  capacity=1, есть место.  Кладём.                         Стоимость: 1
Вставка 2:  capacity=1, полон.       Resize → 2, копируем 1. Кладём. Стоимость: 1+1 = 2
Вставка 3:  capacity=2, полон.       Resize → 4, копируем 2. Кладём. Стоимость: 2+1 = 3
Вставка 4:  capacity=4, есть место.  Кладём.                         Стоимость: 1
Вставка 5:  capacity=4, полон.       Resize → 8, копируем 4. Кладём. Стоимость: 4+1 = 5
Вставка 6:  capacity=8, есть место.  Кладём.                         Стоимость: 1
Вставка 7:  capacity=8, есть место.  Кладём.                         Стоимость: 1
Вставка 8:  capacity=8, есть место.  Кладём.                         Стоимость: 1

Итого за 8 вставок: 1 + 2 + 3 + 1 + 5 + 1 + 1 + 1 = 15. В среднем: 15/8 < 2 на операцию.

Баланс расходов и доходов

Амортизация — термин из финансов: большой разовый расход «растягивается» на много маленьких платежей. После resize с удвоением появляется n свободных слотов — следующий resize случится только через n вставок. Стоимость копирования «оплачена» серией дешёвых вставок до и после.

После n вставок суммарные копирования: 1 + 2 + 4 + 8 + ... < 2n. На n операций — O(n) работы на копирование. В среднем на одну вставку — O(1).

Почему мультипликативный, а не аддитивный рост

Что если при resize увеличивать capacity на 1? Тогда каждая вставка вызывает resize. На вставку номер k копируем k-1 элементов. Суммарно за n вставок:

0 + 1 + 2 + ... + (n-1) = n(n-1)/2 ≈ n²/2

Это O(n²) — append становится таким же дорогим, как вставка в начало обычного массива. Весь смысл динамического массива теряется.

Увеличение на фиксированную величину (+100, +1000) — лучше, но проблема та же: число свободных слотов после resize постоянное, а стоимость копирования растёт линейно. Resize через каждые 100 вставок, но каждый копирует всё больше элементов — суммарно всё равно O(n²).

Мультипликативный рост (×2, ×1.5, ×1.3) решает проблему: число свободных слотов после resize пропорционально текущему размеру. Расходы и доходы сбалансированы при любом постоянном множителе > 1.

Коэффициент роста в реализациях

Конкретный коэффициент — деталь реализации. Java ArrayList растёт примерно на 50% (≈ 1.5×). CPython list использует over-allocation — выделяет чуть больше, чем нужно (порядка n + n/8 + const). std::vector растёт мультипликативно, но стандарт не фиксирует точный коэффициент. Ruby Array растёт примерно в 1.8 раза (формула зависит от текущего размера), но добавляет ещё одно измерение: маленькие массивы хранят элементы прямо внутри объекта (embedded-режим), без отдельного буфера, а при росте переключаются на heap-режим с классическим динамическим массивом; подробности — в заметке о внутренностях Ruby Array.

Больший рост реже копирует, но увеличивает пик памяти. Меньший — чаще копирует, но экономит память.

Накладные расходы памяти

В худшем случае после resize массив заполнен наполовину: до 50% памяти — пустые слоты. Для небольших массивов это незаметно, но для массива на гигабайт — полгигабайта впустую, что может вызвать давление на память процесса или ошибку нехватки памяти.

Уменьшение: shrink

При добавлении length растёт, и capacity растёт вместе с ним. При удалении length уменьшается, но capacity обычно остаётся прежним — массив, из которого удалили большинство элементов, продолжает занимать память под пиковый размер.

Некоторые реализации (Java ArrayList) не уменьшают capacity автоматически — нужен явный вызов trimToSize(). Другие уменьшают буфер, когда заполненность падает ниже порога.

Проблема: O(n) вставка в начало

Доступ по индексу — O(1). Добавление в конец — O(1) амортизированно. Но вставка в начало — по-прежнему O(n): нужно сдвинуть все элементы. Динамический массив решил проблему фиксированного размера, но асимметрия «конец дешёвый, начало дорогое» осталась.

Если задача — часто вставлять в начало или середину, нужна другая организация данных. Связный список отказывается от непрерывности и этим убирает сдвиги.

Sources

• OpenJDK ArrayList (JDK 21+, grow и trimToSize()): https://github.com/openjdk/jdk/blob/master/src/java.base/share/classes/java/util/ArrayList.java
• CPython list (Python 3.x, overallocation в list_resize): https://github.com/python/cpython/blob/main/Objects/listobject.c
• std::vector (C++11+) — политика роста capacity не стандартизирована (зависит от реализации): https://en.cppreference.com/w/cpp/container/vector