Массив
Предпосылки: абстрактный тип данных, указатели/ссылки.
Array — буквально «ряд», «строй». Военный термин: солдаты в шеренге стоят на фиксированных позициях, плечом к плечу, без промежутков. До любого можно дойти, зная его номер и расстояние между бойцами. Массив устроен по тому же принципу: фиксированное количество элементов одного типа в непрерывном блоке памяти, адрес любого вычисляется за O(1).
O(1) доступ — не магическое свойство, а следствие двух конкретных решений: элементы лежат рядом без дыр, и каждый занимает одинаковое количество байт. Из этих решений формула адреса следует автоматически.
| Операция | Сигнатура | Сложность |
|---|---|---|
| Получить элемент | get(i) → value | O(1) |
| Записать элемент | set(i, value) | O(1) |
| Узнать размер | size() → n | O(1) |
Допустимые индексы — от 0 до n-1, размер фиксирован при создании.
Формула адреса
Пусть массив начинается с адреса base, каждый элемент занимает size байт. Раз элементы одинакового размера и между ними нет промежутков, элемент с индексом i лежит по адресу:
address(i) = base + i × size
Одно умножение, одно сложение — количество операций не зависит от n. Отсюда O(1).
Представление в памяти
┌─────────────────────────────────────────────────────┐
│ base │
│ ↓ │
│ [elem 0][elem 1][elem 2][elem 3]...[elem n-1] │
│ ←size→ ←size→ ←size→ │
└─────────────────────────────────────────────────────┘
Массив определяется тремя параметрами: адресом начала base, размером одного элемента size и количеством элементов n.
Инварианты
Из решения «элементы рядом» следует непрерывность: они занимают адреса от base до base + n × size - 1 без пропусков. Из решения «одинаковый размер» — однородность: каждый элемент занимает ровно size байт. Третий инвариант — границы: допустимые индексы от 0 до n-1.
Нарушение инварианта границ — выход за границы массива. В C это неопределённое поведение (чтение/запись чужой памяти). В Rust/Java/Python — паника или исключение. В Ruby arr[i] возвращает nil, а arr.fetch(i) поднимает IndexError.
Что если элементы разного размера?
Формула address(i) = base + i × size опирается на постоянный size. Если элементы занимают разное количество байт, адрес элемента i зависит от размеров всех предыдущих: address(i) = base + size_0 + size_1 + ... + size_{i-1}. Это O(n) — формула сломана.
Первое решение — padding (выравнивание): добить маленькие элементы пустыми байтами, чтобы все занимали одинаковое место. Так работают структуры в C: компилятор добавляет padding, чтобы массив структур имел фиксированный шаг. Формула работает, платим памятью за пустоты.
Второе — массив указателей: сам массив хранит указатели одинакового размера (8 байт на 64-bit), а данные лежат отдельно. Так устроены Ruby Array, CPython list, Java Object[]: внутри — непрерывный массив ссылок, а объекты живут в куче. Формула работает для указателей, но каждое обращение к данным — прыжок в произвольное место памяти, и кэш-локальность теряется.
Указатель — адрес в памяти, не обязательно в куче: он может указывать на стек, статическую память, куда угодно. «Куча» — типичный случай для динамически создаваемых объектов.
Локальность данных
Процессор читает память кэш-линиями — блоками фиксированного размера (часто 64 байта; зависит от CPU). Когда читаешь один байт, загружается вся линия вокруг него.
В «честном» массиве (элементы подряд) обход — последовательное чтение, следующий элемент почти наверняка уже в кэше. В массиве указателей каждый прыжок ведёт в произвольное место — потенциальный cache miss. Попадание в кэш стоит единицы циклов, промах до оперативной памяти — сотни. Поэтому «прыжки по указателям» часто доминируют над асимптотикой.
Цена непрерывности
Раскладка, давшая O(1) доступ по индексу, делает вставку и удаление дорогими. Чтобы вставить элемент в позицию i, нужно сдвинуть все элементы от i до n-1 на одну позицию вправо — иначе непрерывность нарушится:
До: [A][B][C][D][_] (вставка X в позицию 1)
Сдвиг: [A][_][B][C][D] (B, C, D сдвинулись вправо)
После: [A][X][B][C][D]
Удаление — обратная операция: элементы после удалённого сдвигаются влево.
Ключевая асимметрия: конец дешёвый, начало дорогое. Вставка после последнего элемента — O(1), ничего не сдвигается. Вставка в позицию 0 — O(n), сдвигаются все n элементов. То же с удалением: с конца O(1), из начала O(n).
| Операция | Время | Почему |
|---|---|---|
| Чтение по индексу | O(1) | Формула адреса |
| Запись по индексу | O(1) | Формула адреса |
| Поиск по значению | O(n) | Нужно проверить каждый элемент |
| Вставка в позицию i | O(n) | Сдвиг элементов |
| Удаление из позиции i | O(n) | Сдвиг элементов |
Текстовый редактор, хранящий строку из 10 000 символов как массив, платит за каждое нажатие клавиши: вставка символа в позицию курсора в середине строки — сдвиг ~5 000 элементов. При 60 нажатиях в секунду — 300 000 перемещений элементов только ради набора текста.
Проблема: фиксированный размер
Массив реализует ADT Array, но размер фиксирован при создании. Если заранее неизвестно сколько элементов будет — выделять «с запасом» значит тратить память, выделять «впритык» — не влезет следующий элемент. Динамический массив решает эту проблему, сохраняя O(1) доступ по индексу.
Sources
- Ulrich Drepper (2007), What Every Programmer Should Know About Memory — кэш-линии, локальность и порядок величин задержек памяти: https://people.redhat.com/drepper/cpumemory.pdf
- CPython 3.x source,
Objects/listobject.c— реализацияlistкак массива ссылок: https://github.com/python/cpython/blob/main/Objects/listobject.c - Ruby (MRI) 3.x source,
array.c— реализацияArrayкак массиваVALUE: https://github.com/ruby/ruby/blob/master/array.c - Java Language Specification (Java SE 21), §10 Arrays — массив ссылочного типа хранит ссылки (
Object[]и т.п.): https://docs.oracle.com/javase/specs/jls/se21/html/jls-10.html