Ряд оценок, который хочется менять

У нас есть оценки за контрольные: 5, 3, 4, 5, 2. Пять чисел. Пока их три-четыре, можно было бы держать каждое в отдельной переменной. Хочется собрать их вместе, обращаться к нужной по номеру, менять, добавлять новые. Именно отсюда начинается разговор о массивах.

Однотипные элементы на позициях

Массив — это последовательность элементов, расположенных на позициях с номерами от 0 до n − 1. Номер позиции называют индексом. В нашем примере с оценками все элементы — целые числа, и именно это делает модель простой: каждый элемент занимает ровно одну позицию, позиции идут одна за другой без пропусков, а количество позиций заранее известно. Плотное хранение здесь означает, что между соседними элементами нет свободного места: если в массиве пять оценок, то под них отведено ровно пять позиций подряд.

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

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

Посмотрим на примере.

using System;

int[] grades = { 5, 3, 4, 5, 2 };
Console.WriteLine(grades[0]);
Console.WriteLine(grades[4]);
Console.WriteLine(grades.Length);
int sum = 0;
for (int i = 0; i < grades.Length; i++)
{
    sum += grades[i];
}
Console.WriteLine(sum);
grades[1] = 4;
Console.WriteLine(grades[1]);

Вывод:

5
2
5
19
4

Здесь grades[0] — первый элемент, grades[4] — последний при длине пять. grades.Length возвращает число позиций. Цикл обходит все элементы и складывает их в сумму — это O(n) работы. А присваивание grades[1] = 4 заменяет значение во второй позиции: слот остаётся тем же, меняется только содержимое. Такая замена — операция фиксированной стоимости, потому что мы знаем индекс и сразу обращаемся к нужному слоту.

Изменить элемент или вставить в последовательность

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

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

Похожая история с удалением. Убрать элемент из середины — значит сдвинуть весь правый хвост на одну позицию влево, чтобы закрыть образовавшуюся дыру. И снова стоимость зависит от длины хвоста.

Вставка со сдвигом вправо

Разберём вставку руками. Пусть у нас есть буфер — заранее выделенное место под некоторое число элементов. Длина буфера, скажем, восемь, а логических элементов в нём пока пять: 5, 3, 4, 5, 2. Оставшиеся три слота — резерв, они пока пусты, но место под них уже есть. Хотим вставить значение 4 на позицию 1, между пятёркой и тройкой.

using System;

int[] buffer = new int[8];
int size = 5;
buffer[0] = 5;
buffer[1] = 3;
buffer[2] = 4;
buffer[3] = 5;
buffer[4] = 2;

int position = 1;
int value = 4;

for (int i = size; i > position; i--)
{
    buffer[i] = buffer[i - 1];
}
buffer[position] = value;
size++;

for (int i = 0; i < size; i++)
{
    Console.Write(buffer[i]);
    if (i < size - 1) Console.Write(", ");
}
Console.WriteLine();
Console.WriteLine(size);

Вывод:

5, 4, 3, 4, 5, 2
6

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

Удаление со сдвигом влево

Удаление устроено зеркально. Чтобы убрать элемент из позиции, надо сдвинуть весь правый хвост на одну позицию влево, начиная с самой позиции. На этот раз сдвиг идёт слева направо: берём элемент из позиции справа и кладём его на текущую, постепенно закрывая дыру.

Снова берём 5, 3, 4, 5, 2 и удаляем элемент на позиции 2.

using System;

int[] buffer = new int[8];
int size = 5;
buffer[0] = 5;
buffer[1] = 3;
buffer[2] = 4;
buffer[3] = 5;
buffer[4] = 2;

int position = 2;
for (int i = position; i < size - 1; i++)
{
    buffer[i] = buffer[i + 1];
}
size--;

for (int i = 0; i < size; i++)
{
    Console.Write(buffer[i]);
    if (i < size - 1) Console.Write(", ");
}
Console.WriteLine();
Console.WriteLine(size);

Вывод:

5, 3, 5, 2
4

Результат отличается от замены. При замене на позиции 2 осталась бы четвёрка или другое значение, но длина не изменилась бы. При удалении четвёрка исчезла, длина уменьшилась, а всё, что было правее, сдвинулось влево.

Границы и пустой случай

У операций над массивом есть границы, за которые выходить нельзя. При чтении или удалении индекс должен быть в пределах от 0 до size − 1: если size равно нулю, допустимых индексов нет вовсе. При вставке позиция может быть от 0 до size включительно: вставка в конец — нормальная ситуация, она означает «добавить после последнего элемента». А ещё вставка возможна только тогда, когда в буфере есть свободное место, то есть size меньше длины буфера. Если резерва нет, придётся расширять буфер — об этом дальше.

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

using System;

int[] buffer = new int[4];
int size = 0;
int position = 0;
int value = 7;

for (int i = size; i > position; i--)
{
    buffer[i] = buffer[i - 1];
}
buffer[position] = value;
size++;

Console.WriteLine(buffer[0]);
Console.WriteLine(size);

Вывод:

7
1

Вставка в пустую последовательность на позицию 0 не требует сдвигов: цикл не выполняет ни одной итерации, потому что size равно нулю, а условие i > position сразу ложно. Значение просто записывается в нулевую позицию, и длина становится единицей.

Динамический массив: буфер с запасом

Теперь можно перейти к главной идее, ради которой всё это затевалось. Массив фиксированной длины неудобен тем, что его размер надо знать заранее. А если мы не знаем, сколько элементов придёт? Держать запас на десять позиций, а потом оказаться с сотней? Хочется, чтобы структура сама подстраивалась под количество элементов.

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

Когда буфер заполнен и добавляется ещё один элемент, деваться некуда: надо выделить новый буфер, перенести в него всё содержимое старого и только потом положить новый элемент. Перенос стоит O(n) — надо скопировать все текущие элементы. Само по себе расширение дорого.

Зачем растить буфер в постоянное число раз

Здесь легко сделать неверный вывод: раз расширение дорого, может, расти на одну позицию за раз? Тогда каждое добавление в момент заполнения будет требовать переноса n элементов, и суммарно n добавлений превратятся в квадратичную работу. Плохо.

Поэтому буфер увеличивают не на один, а сразу в несколько раз — например, в два. Это и есть геометрический рост: каждый раз новый размер примерно в постоянное число раз больше прежнего. Что это даёт? Расширения становятся всё реже. Если буфер уже вмещает n элементов, следующее расширение наступит примерно через n добавлений. А до этого все добавления шли за фиксированное время.

Если сложить работу по всем расширениям за серию из n добавлений в изначально пустую структуру, получится линейная сумма. Интуиция такая: расширения происходят на размерах примерно 1, 2, 4, 8, 16, и так далее. Сумма переносов 1 + 2 + 4 + 8 + ... не превышает удвоенного последнего размера, то есть примерно 2n. Значит, все n добавлений вместе стоят O(n), хотя отдельное добавление в момент расширения может стоить O(n).

Точный коэффициент роста — деталь реализации. Конкретные библиотеки могут выбирать разные множители, и на API это не влияет. Важен сам принцип: рост в постоянное число раз больше единицы даёт линейную суммарную работу. Если бы рост был на одну позицию, сумма была бы квадратичной.

Готовая реализация: List

В C# динамический массив уже реализован — это List<T>, где T обозначает тип элементов. Нам не нужно писать свой буфер и вручную расширять его: у готового типа есть операции, соответствующие разобранным выше действиям. Добавление в конец — Add, вставка в позицию — Insert, удаление по позиции — RemoveAt. Число логических элементов доступно через Count, а размер внутреннего буфера — через Capacity. Резерв — это разница между ними: место под будущие добавления, ещё не занятое логическими элементами.

using System;

using System.Collections.Generic;

List<int> grades = new List<int> { 5, 3, 4, 5, 2 };
grades.Add(4);
Console.WriteLine(string.Join(", ", grades));
Console.WriteLine(grades.Count);
grades.Insert(1, 4);
Console.WriteLine(string.Join(", ", grades));
grades.RemoveAt(2);
Console.WriteLine(string.Join(", ", grades));
Console.WriteLine(grades.Count);

Вывод:

5, 3, 4, 5, 2, 4
6
5, 4, 3, 4, 5, 2, 4
5, 4, 4, 5, 2, 4
6

Add добавил четвёрку в конец: длина стала шесть. Insert(1, 4) вставил четвёрку на позицию 1, сдвинув правый хвост вправо: получилась последовательность из семи элементов. RemoveAt(2) удалил элемент с позиции 2 — это была тройка, — и правый хвост сдвинулся влево. Снова шесть элементов, но состав другой.

Что стоит каждая операция

Полезно свести всё разобранное в одну картину. Затраты ниже — про худший случай, то есть про ситуацию, когда сдвиг или поиск идут по всей длине.

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

Вставка в середину сдвигает правый хвост вправо — чем он длиннее, тем дороже операция. Удаление из середины сдвигает правый хвост влево — та же зависимость. Поиск без знания позиции просматривает элементы один за другим. Во всех этих случаях в худшем случае мы имеем дело с O(n). Если же позиция близка к концу, хвост короткий, и операция обходится дешевле; именно поэтому таблица даёт верхнюю границу, а не точную цену на каждом конкретном входе.

Память

В оценке памяти удобно различать две величины. Пусть n — число логических элементов, то есть сколько значений реально хранится. А c — ёмкость буфера, то есть сколько слотов под них отведено. Память под буфер — это O(c), потому что резерв тоже занимает место, даже если логических элементов в нём меньше. Если c ограничена сверху постоянным множителем от n, то есть c ≤ const · n при n > 0, оценка упрощается до O(n). Если же резерв задан большим запасом и растёт не вместе с числом логических элементов, следует учитывать фактическую ёмкость, а не только численность. И отдельно стоит помнить: пустая структура может иметь ненулевой резерв — логических элементов ноль, а память под буфер уже выделена.

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

Граница применимости

И напоследок — о том, где плотное хранение перестаёт быть удобным. Массив и динамический массив хороши, когда элементы заполняют пространство индексов более или менее плотно. Если нужны позиции 0, 1000000 и 2000000, а между ними почти ничего, буфер придётся заводить под весь диапазон, и почти всё это пространство останется пустым. Плотное хранение плохо подходит для разреженных номеров: там нужны другие подходы. Но пока мы работаем с оценками, заказами и другими последовательностями, которые заполняют свои позиции плотно, массив и динамический массив — естественный и удобный инструмент.