Массивы, списки и хеш-таблицы — Примеры

Пример 1 — Настоящая стоимость одной вставки

Сервис хранит недавние id заказов в динамическом массиве, и новое требование вставляет приоритетный заказ в самое начало. Трассировка ниже показывает, как идёт эта вставка на примере из пяти элементов. Скажите, сколько элементов при этом сдвигается и что меняется, когда массив уже полон.

ёмкость 5, длина 5,  [A][B][C][D][E]
вставка X по индексу 0
  шаг 1: массив полон -> выделить 10, копировать 5
  шаг 2: сдвинуть E,D,C,B,A вправо на один
  шаг 3: записать X по индексу 0
  итог: [X][A][B][C][D][E]  длина 6, ёмкость 10

Решение

сдвинуто элементов: 5 (весь хвост), плюс копия из 5 для роста
итог:              [X][A][B][C][D][E], ёмкость 10
стоимость:         вставка в начало O(n); добавление O(1) амортизированно

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

Пример 2 — Скан, которому место в хеш-таблице

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

orders = [ {id: 1, ...}, {id: 2, ...}, ... ]     # 10 000 записей
for item in line_items:                          # 10 000 позиций
    for order in orders:                         # скан каждый раз
        if order.id == item.order_id:
            item.order = order

Решение

by_id = {}
for order in orders:
    by_id[order.id] = order          # один проход, до цикла

for item in line_items:
    item.order = by_id[item.order_id]   # один шаг на позицию

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