CS Notes

array

6 min read

Массив

Предпосылки: абстрактный тип данных, указатели/ссылки, оценка сложности O(…), базовое чтение Ruby (методы, блоки, массивы и хеши), иерархия памяти (память как последовательность адресуемых байт, кеш).

← ADT | Динамический массив →

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

Массив устроен по тому же принципу. Элементы одного типа лежат в памяти подряд, без промежутков, и каждый занимает одинаковое место. Тогда, чтобы добраться до элемента по его номеру, не нужно идти по очереди от начала: позицию любого элемента можно вычислить сразу, за фиксированное число шагов — то есть за O(1).

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

Базовый набор операций над массивом — взять элемент по номеру, записать элемент по номеру, узнать число элементов. Номер элемента называют индексом; нумерация идёт с нуля, так что у массива из n элементов индексы — от 0 до n-1. Каждая из этих операций стоит O(1):

ОперацияЧто делаетСложность
Взять по индексу iвернуть элемент на позиции iO(1)
Записать по индексу iположить значение на позицию iO(1)
Узнать размервернуть число элементов nO(1)

Размер массива фиксирован при создании — почему именно так и чем за это платят, видно из той же раскладки.

Формула позиции

Память — последовательность ячеек, у каждой свой адрес, и размер любого блока измеряется в байтах. Пусть массив начинается с адреса base (адрес самого первого элемента), и каждый элемент занимает size байт. Раз элементы одинакового размера и между ними нет промежутков, элемент с индексом i начинается через i целых элементов после начала — то есть по адресу:

address(i) = base + i × size

Одно умножение, одно сложение — число действий не зависит от того, сколько в массиве элементов. Поэтому доступ по индексу и стоит O(1): добраться до тысячного элемента не дороже, чем до первого.

Так массив целиком описывается тремя величинами: адресом начала base, размером одного элемента size и количеством элементов n. На схеме:

+-----------------------------------------------------+
|  base                                               |
|   v                                                 |
|  [elem 0][elem 1][elem 2][elem 3]...[elem n-1]      |
|   <-size-><-size-><-size->                          |
+-----------------------------------------------------+

Здесь elem i — элемент с индексом i, а <-size-> показывает, что каждый занимает одинаковую ширину size.

Что массив гарантирует всегда

Из этих величин вытекают три свойства, которые массив поддерживает на протяжении всей жизни. Из решения «элементы рядом» — непрерывность: они занимают адреса от base до base + n × size - 1 без пропусков (последний занятый байт на единицу меньше первого свободного, отсюда - 1). Из решения «одинаковый размер» — однородность: каждый элемент занимает ровно size байт. Третье свойство — границы: обращаться можно только по индексам от 0 до n-1.

Обращение по индексу вне этого диапазона — выход за границы массива: формула честно посчитает адрес, но он указывает на чужую память. Что произойдёт дальше — зависит от языка: одни читают/пишут чужую память (опасно и непредсказуемо), другие останавливают программу с ошибкой. В Ruby, например, arr[i] за границей возвращает nil, а arr.fetch(i) поднимает ошибку IndexError:

arr = [10, 20, 30]
arr[5]        # => nil
arr.fetch(5)  # => IndexError: index 5 outside of array bounds

Элементы разного размера

Формула address(i) = base + i × size держится на том, что size одинаков для всех. Если элементы занимают разное число байт, позиция i-го зависит уже от размеров всех элементов перед ним, и чтобы её узнать, придётся сложить их все — а это проход по i элементам, то есть O(n). Быстрый доступ по индексу теряется. Сохранить его можно двумя способами, и оба возвращаются к одинаковому шагу.

Первый — выровнять размер: добить элементы поменьше пустыми байтами, чтобы все занимали одинаковое место. Шаг снова постоянен, формула работает; платим памятью за пустоты.

Второй — массив указателей: в самом массиве лежат не сами элементы, а указатели на них — а указатель имеет фиксированный размер независимо от того, на что показывает. Данные при этом живут отдельно, где придётся. Формула работает для массива указателей, но за неё приходится платить иначе: чтобы добраться до самих данных, нужно сделать ещё один шаг по указателю — прыгнуть в произвольное место памяти. Так устроены массивы во многих языках с динамическими объектами (например, Array в Ruby): внутри — непрерывный ряд ссылок, а объекты разбросаны по памяти. И вот этот прыжок дорог по причине, которую видно только на уровне иерархии памяти.

Цена прыжков по памяти

Процессор читает память не по байту, а кеш-линиями — блоками фиксированного размера (часто 64 байта). Прочитал один байт — соседние из той же линии уже подтянулись в быстрый кеш. На этом и держится локальность данных: данные, лежащие рядом, читаются почти бесплатно после первого обращения.

Когда элементы массива лежат подряд, обход — это последовательное чтение: следующий элемент почти наверняка уже в кеше, подтянутый вместе с предыдущим. В массиве указателей каждый прыжок к данным ведёт в случайное место, которого в кеше скорее всего нет, — промах кеша. А чтение из кеша и чтение из основной памяти отличаются по стоимости на порядки: разница так велика, что на практике «прыжки по памяти» легко перевешивают любую разницу в асимптотике. Непрерывная раскладка массива — это и есть способ её избежать.

Цена непрерывности

Раскладка, давшая 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)Нужно проверить каждый элемент
Вставка в позицию iO(n)Сдвиг элементов
Удаление из позиции iO(n)Сдвиг элементов

Где это бьёт на практике: текстовый редактор, хранящий строку из 10 000 символов как массив символов, платит за каждое нажатие клавиши. Вставка символа в позицию курсора посреди строки — сдвиг ~5 000 элементов; при 60 нажатиях в секунду это 300 000 перемещений только ради набора текста.

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

Когда размер заранее неизвестен

Остаётся слабое место: размер фиксирован при создании. Массив реализует контракт ADT Array, но если заранее неизвестно, сколько будет элементов, выбор плохой в обе стороны — выделить «с запасом» значит тратить память, выделить «впритык» значит упереться в потолок на следующем элементе. Динамический массив снимает это ограничение, сохраняя при этом O(1)-доступ по индексу.

Sources

← ADT | Динамический массив →

Graph View

Backlinks