Массивы

Прочитать миллионное значение массива можно за один шаг, а вставить новое значение в начало того же массива значит сдвинуть миллион значений.

Что такое структура данных

Программа, которая хранит список имён, очередь заданий на печать или таблицу цен, должна где-то держать эти данные и отвечать на вопросы о них: какой третий элемент, есть ли это имя в списке, какое задание следующее? Структура данных представляет собой способ хранить данные вместе с методами, которые отвечают на эти вопросы. Курс MIT 6.006 разделяет здесь две идеи. Интерфейс говорит, какие операции можно запросить, например «получить элемент на позиции i» или «добавить элемент в конец». Структура данных говорит, как эти операции на самом деле выполняются в памяти. За одним интерфейсом может стоять несколько структур данных, и по скорости они могут отличаться огромно.

Этот курс, как и курс об алгоритмах, считает шаги, чтобы сравнивать две структуры без секундомера. В этом уроке шагом считается чтение или запись одной ячейки памяти. Лаборатория ниже считает их за тебя.

Один блок ячеек, подряд

Массив хранит значения в одном сплошном блоке памяти, каждое значение в ячейке одинакового размера, с номерами от 0. Именно такое устройство делает чтение из массивов быстрым. Если блок начинается по адресу s и каждая ячейка занимает c байт, то a[i] лежит по адресу s + i × c. Компьютер вычисляет это одним умножением и одним сложением и сразу переходит туда, будь i равно 3 или 3 000 000. В конспектах MIT операции «get at(i)» и «set at(i, x)» для массива указаны как Θ(1): стоимость не растёт с длиной.

Из-за того же устройства изменения в середине медленные. Пусть в массиве 7, 3, 9, 4, 6, и нужно поставить 1 в начало. Перед 7 пустого места нет, поэтому сначала каждое значение должно сдвинуться на одну ячейку вправо, начиная с последнего, чтобы ничего не затереть. Это 5 сдвигов и 1 запись: 6 шагов. Удаление первого значения является зеркальным случаем: прочитать его, затем сдвинуть остальные 4 значения на одну ячейку влево. Вставка на позицию i в массив из n значений стоит n − i сдвигов плюс одну запись, поэтому начало является худшим местом, а конец лучшим.

Когда блок полон

У блока памяти фиксированный размер, так что же происходит, когда добавляешь значение, а все ячейки заняты? Массиву приходится запросить новый, больший блок и скопировать туда каждое значение, прежде чем записать новое. В лаборатории добавление в полный блок из 5 стоит 5 копирований и 1 запись. Если бы массив каждый раз рос всего на одну ячейку, каждое добавление копировало бы всё, и n добавлений стоили бы около n²/2 копирований.

Решение, описанное в конспектах MIT, состоит в том, чтобы расти сразу сильно, например удваиваться. Если начать с ёмкости 1, копирования происходят, когда в массиве 1, 2, 4, 8 и 16 значений, так что 17 добавлений стоят в сумме 1 + 2 + 4 + 8 + 16 = 31 копирование, меньше 2 на одно добавление. Отдельное добавление всё ещё может быть медленным, но в любой длинной серии добавлений в среднем выходит постоянная стоимость на добавление. Это называется амортизированным временем Θ(1). Массив JavaScript снаружи ведёт себя именно так: MDN описывает массивы как изменяемые по размеру, а push и pop работают с концом, то есть с дешёвой стороной.

const a = [7, 3, 9, 4, 6];
console.log(a[3]);      // 4, один шаг
a.push(8);              // дёшево: конец
a.unshift(1);           // каждое значение сдвигается на ячейку вправо
console.log(a.join(" ")); // 1 7 3 9 4 6 8