Вектор. Функциональная спецификация: восемь операций и главный компромисс
Что это такое
Вектор - последовательность переменной длины: количество элементов не фиксировано и может меняться. Вектор без единого элемента называется пустым. Но, в отличие от файла с его строго последовательным доступом, вектор дает доступ к любому элементу за постоянное время: сотый элемент читается так же быстро, как первый.
Почему индексация с нуля
Множество допустимых индексов вектора длины n - это {0, ..., n - 1}. Ноль в качестве первого индекса выбран не случайно: адрес элемента вычисляется по формуле адрес начала блока + индекс × размер компоненты. Если бы индексация шла с единицы, к каждому обращению добавлялось бы лишнее вычитание смещения - а это замедление самой частой операции.
Длина вектора - важная характеристика: многие математические операции (сложение векторов, скалярное произведение) определены только для векторов равной длины.
Восемь операций спецификации
Вектор. Функциональная спецификация в деталях
- СОЗДАТЬ - порождает вектор заданной длины N.
- ПУСТО - проверяет, что длина равна нулю.
- ДЛИНА - возвращает текущее количество элементов.
- ЗАГРУЗИТЬ - читает элемент по индексу. O(1).
- СОХРАНИТЬ - записывает значение по индексу. O(1).
- ИЗМЕНИТЬ_ДЛИНУ - меняет длину вектора. O(N): может потребовать копирования всех элементов.
- РАВНЫ - векторы равны, если равны длины и попарно равны компоненты.
- УНИЧТОЖИТЬ - возвращает память системе.
Главный компромисс
Почему изменение длины такое дорогое? Постоянное время доступа требует, чтобы элементы лежали в памяти сплошным блоком (иначе формула адреса не работает). Но операционная система не всегда может выделить дополнительную память ровно за концом этого блока. Тогда приходится выделять новый блок нужного размера и переносить туда все элементы - отсюда O(N).
Правила сохранности при изменении длины:
- Уменьшение с n до m: элементы с индексами 0 ... m - 1 сохраняют значения.
- Увеличение с n до p: элементы 0 ... n - 1 сохраняются, новые (n ... p - 1) не определены или инициализируются по умолчанию.
Тренажер: операции вектора по шагам
Создадим вектор длины 3,
запишем в него 5, 3, 8, прочитаем по индексу
и дважды поменяем длину: сначала на 5, потом
на 2. Знак ? - неопределенное значение.
list внутри CPython -
именно вектор: сплошной динамический массив указателей, а не связный список.
Поэтому L[i] работает за O(1). А когда при append()
резерв памяти кончается, Python выполняет ту самую ИЗМЕНИТЬ_ДЛИНУ: выделяет
блок побольше и копирует туда все элементы.
Коротко: главное
- Вектор - последовательность переменной длины с доступом по индексу за O(1).
- Индексация с 0: адрес = база + индекс × размер, без лишнего смещения.
- Восемь операций: СОЗДАТЬ, ПУСТО, ДЛИНА, ЗАГРУЗИТЬ, СОХРАНИТЬ, ИЗМЕНИТЬ_ДЛИНУ, РАВНЫ, УНИЧТОЖИТЬ.
- Компромисс: мгновенный доступ оплачен дорогим изменением длины - O(N).
- При изменении длины старые элементы сохраняются, новые - не определены.
Проверьте себя
Почему операция ИЗМЕНИТЬ_ДЛИНУ у вектора работает за O(N), а не за O(1)?