bisect с key в Python: почему искомое значение уже должно быть ключом

В памяти хранится отсортированный список событий. Нужно быстро найти все записи с временем 20. После добавления key функция bisect падает на сравнении числа с объектом события. Разработчик ожидал, что key одинаково обработает элементы списка и искомый объект. Для bisect это ожидание неверно.

Искать готовый ключ

bisect_left и bisect_right ищут границу вставки готового значения x среди ключей элементов. Функция key применяется к элементам коллекции при сравнении. К самому x она не применяется. Поэтому при key=lambda event: event.time аргументом поиска будет число 20, а не Event(20). Это позволяет искать по ключу без создания фиктивной записи с ненужными полями.

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

У insort_left и insort_right другая задача: они вставляют настоящий объект. Для поиска позиции key применяется и к вставляемому объекту, после чего в список помещается сам объект. Различие разумно по назначению API, но его легко перепутать при рефакторинге. Пример проверяет оба вызова рядом и показывает, что исходные записи сохраняют свой тип.

Получить диапазон и вставить объект

from bisect import bisect_left, bisect_right, insort_right
from dataclasses import dataclass
from operator import attrgetter

@dataclass(frozen=True)
class Event:
    time: int
    name: str

events = [Event(10, "a"), Event(20, "b"), Event(20, "c"), Event(30, "d")]
key = attrgetter("time")
left = bisect_left(events, 20, key=key)
right = bisect_right(events, 20, key=key)
assert [event.name for event in events[left:right]] == ["b", "c"]
insort_right(events, Event(20, "new"), key=key)
assert [event.name for event in events] == ["a", "b", "c", "new", "d"]
assert [event.time for event in events] == [10, 20, 20, 20, 30]
print(left, right)
print([event.name for event in events])

Параметр key у этих функций доступен начиная с Python 3.10. Сохраните пример в файл и запустите: границы равны 1 и 3, новая запись появляется после существующих событий с временем 20. Замена insort_right на insort_left поменяет правило для равных ключей. Выберите его по требованиям, а если нужен полный порядок, включите в ключ дополнительный устойчивый идентификатор.

Сохранить порядок коллекции

Двоичный поиск полезен только пока список отсортирован по тому же ключу. Если изменить event.time на месте, позиция объекта может стать неправильной, и последующие поиски перестанут иметь смысл. В примере dataclass заморожен, чтобы подсветить это правило. Для обновления создайте новый объект, удалите старый и вставьте новый в правильное место либо перестройте индекс.

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

Если вычисление key дорогое, повторяющийся поиск снова вычисляет ключи посещённых элементов. Можно хранить отдельный список готовых ключей, но тогда два массива должны изменяться согласованно. Более простой вариант — включить нужное значение в структуру записи при загрузке. Не вводите дополнительный индекс без ответа, кто обновляет его вместе с данными.

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

Продолжить практику

Перед переходом к сложным индексам полезно закрепить модели данных и их тесты. В бесплатном курсе по ООП, типизации и тестированию есть dataclass и pytest: откройте программу и оформите проверки границ как отдельные сценарии. Затем разделы стандартной библиотеки в «Python для профессионалов» помогут расширить набор подходящих инструментов.