CS Notes

dynamic-array

7 min read

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

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

← Массив | Связный список →

У массива есть два жёстких ограничения. Размер задаётся при создании и потом не меняется — а заранее известно, сколько элементов придёт, далеко не всегда. И даже когда массив выделен с запасом, добавление в конец упирается в его границу: за концом нет места, которое массив мог бы занять. Динамический массив снимает оба ограничения: элементы добавляются по одному, без заранее известного количества, а O(1) доступ по индексу при этом сохраняется.

Цена за это видна не сразу. Добавление в конец почти всегда стоит O(1), но изредка — O(n): в среднем по серии вставок всё равно выходит O(1) на операцию, и почему так — главный вопрос этой заметки. Остальные операции массив отдаёт без изменений:

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

Выделенное место и занятое место

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

Внутри динамического массива лежит обычный статический массив на capacity ячеек. Пока length < capacity, есть куда класть: новый элемент пишется в первую свободную ячейку, length увеличивается на единицу — O(1). Трудность начинается, когда length == capacity: свободных ячеек не осталось, а массив расширить нельзя — за его концом память уже может быть занята чем-то другим.

Что происходит, когда массив заполнен

Раз расширить текущий блок нельзя, единственный выход — выделить новый блок побольше, перенести в него всё старое и работать дальше уже с ним. Это перевыделение с копированием называют resize:

Было:   capacity=4, length=4
        [A][B][C][D]    — свободных ячеек нет

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

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

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

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

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

Почему append всё равно O(1) в среднем

Шаг 2 копирует все элементы — это O(n). Кажется, что append испорчен: одна вставка из многих внезапно стоит как полный проход по массиву.

Соберём стоимость серии явно. Пусть capacity стартует с 1 и удваивается при каждом заполнении; считаем стоимость каждой вставки как «запись элемента» плюс «копирования при resize, если он случился»:

Вставка 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 встречаются всё реже именно потому, что после каждого удвоения освободившихся ячеек ровно столько же, сколько уже лежит, — и следующий resize отодвигается вдвое дальше предыдущего.

Почему дешёвые вставки покрывают дорогой resize

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

После очередного удвоения свободных ячеек ровно столько, сколько занятых: если перед resize было занято m элементов, новый capacity равен 2m, и до следующего resize пройдёт ещё m вставок. Эти m дешёвых вставок и «оплачивают» одно копирование m элементов: на каждую из них приходится примерно по одному скопированному элементу сверх её собственной работы.

Просуммируем копирования за n вставок. Последний resize скопировал около n элементов, предыдущий — вдвое меньше, и так далее: n + n/2 + n/4 + ... < 2n. Это O(n) работы на копирование за всю серию из n вставок — то есть O(1) в среднем на одну вставку. Отдельная вставка по-прежнему может стоить O(n), но такая случается раз на удвоение размера.

Почему capacity умножают, а не прибавляют

Удвоение здесь не случайно. Что если при resize увеличивать capacity не вдвое, а на фиксированную единицу — например, на 1? Тогда массив заполнен после каждой вставки, и каждая вставка запускает resize. Перед вставкой номер k в массиве уже лежит k-1 элементов, и все они копируются. За n вставок копирований выйдет:

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

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

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

Умножение спасает потому, что запас ячеек после resize растёт вместе с размером: чем больше массив, тем дольше до следующего копирования. Дешёвых вставок между двумя resize всегда хватает, чтобы покрыть копирование, — при любом постоянном множителе больше единицы (×2, ×1.5, ×1.3).

Множитель роста в реальных реализациях

Конкретный множитель — деталь реализации, и они расходятся. Java ArrayList растёт примерно в 1.5 раза, std::vector в C++ растёт мультипликативно, но точный множитель стандарт не фиксирует. CPython (основная реализация Python) держит для list чуть больший запас, чем нужно прямо сейчас, чтобы реже копировать. Ruby Array растёт примерно в 1.8 раза. Подробности устройства Ruby Array — в заметке о внутренностях Ruby Array.

Выбор множителя — это размен: больший множитель копирует реже, но держит больше пустых ячеек и поднимает пик памяти; меньший экономит память, но копирует чаще.

Цена запаса: пустые ячейки

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

Память не возвращается при удалении

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

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

Где динамический массив перестаёт подходить

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

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

Sources

← Массив | Связный список →

Graph View

Backlinks