Алгоритмы и данные: сортировки, поиск, агрегации

Правильность — не единственная мера качества программы: два решения могут давать одинаковый ответ на маленьком журнале и разваливаться на большом. Цена перебора списка — до n сравнений: поиск записи в журнале из 10 000 строк в худшем случае просматривает все 10 000. Поиск по словарю из модуля 5 устроен иначе: внутри у него хэш-таблица — структура, которая по самому ключу вычисляет, где лежит значение, поэтому словарю всё равно, 10 в нём записей или 10 000, — и то и другое считается за несколько операций. Столько же даёт отсортированный список: бинарный поиск держит окно ещё возможных элементов и каждым сравнением режет его пополам — сверили середину с целью, и половина, где цели быть не может, отброшена. Окно из 1000 записей схлопывается цепочкой 1000 → 500 → 250 → 125 → 63 → 32 → 16 → 8 → 4 → 2 → 1 — десять сравнений вместо тысячи: 2 ** 10 — это 1024, десяти делений пополам хватает на тысячу. Сортировка сама стоит усилий, но делается один раз, а каждый дальнейший поиск по отсортированным данным обходится в десяток сравнений вместо тысяч: для одного поиска по короткому списку сортировать невыгодно, для многих поисков по большому журналу — обязательно.

Сортирует функция sorted из модуля 4: по умолчанию — по возрастанию, reverse=True переворачивает порядок. Правило сортировки сложных значений задаёт параметр key: это функция, которую Python применяет к каждому элементу, а расставляет элементы по результатам. Именовать функцию ради одного вызова громоздко, и для коротких одноразовых правил есть lambda — функция без имени, объявленная на месте: после слова lambda стоят параметры, двоеточие и одно выражение — его значение и возвращается, return не нужен. lambda f: f["duration_min"] получает запись полёта f и отдаёт её длительность. Именованная функция из def — для длинных правил и повторного использования, lambda — для коротких правил, живущих в одном вызове. Составной ключ — кортеж: кортежи сравниваются поэлементно, сначала первые элементы, при равенстве — вторые. Число с минусом меняет свой порядок на убывание: key=lambda f: (-f["duration_min"], f["date"]) ставит длинные полёты выше коротких, а при равной длительности — более раннюю дату выше: ISO-даты сравниваются как строки уже правильно, "2026-05-01" меньше "2026-05-02". Минус-трюк работает только с числами: у строки отрицательного значения нет.

Цена тупого перебора считается на пальцах. Сколько существует порядков облёта пяти путевых точек? Первой идёт любая из 5, второй — любая из оставшихся 4, дальше 3, 2 и 1: 5 × 4 × 3 × 2 × 1 = 120. Такое произведение называется факториалом и пишется 5!; для десяти точек это уже 10! = 3 628 800 — данных стало вдвое больше, а вариантов — в тридцать тысяч раз больше. Фиксация старта срезает перебор: 4! = 24. Перебор перестановок — крайняя мера, и этот модуль про инструменты, которые решают задачи без него: сортировку с ключом, группировку словарём, бинарный поиск и готовые пары из itertools.

Группировка — постоянная работа со списком словарей: из плоского журнала собрать словарь «значение поля → список записей с этим значением». Шаблон на одну строку держит метод setdefault: groups.setdefault(rec[key], []) возвращает список, лежащий под ключом, а если ключа ещё нет — сначала кладёт под него пустой список и возвращает его; append дописывает запись в возвращённый список. Это родня метода .get из модуля 5: get при чтении только подставляет запасное значение, setdefault ещё и сохраняет его в словарь. Порядок записей внутри каждой группы — порядок входа: цикл идёт по списку и дописывает в конец.

Серии — значения одного смысла подряд: отсчёты здоровья True через False, высоты выше порога. Длину серии измеряют одним проходом с двумя переменными: счётчик текущей серии и лучший результат. Очередной True удлиняет текущую серию на единицу и, если она стала длиннейшей, обновляет максимум; False обнуляет текущую серию — это разрыв. В модуле 10 так считалось число серий (FlightStats.climb_periods ловил переходы False → True); теперь измеряем длины и берём наибольшую. Ловушка шаблона: серия, дотянувшая до конца списка, никогда не встретит False — поэтому максимум обновляется на ходу, при каждом удлинении, а не «один раз после цикла».

Пары «каждая с каждой» даёт модуль itertools — ещё один инструмент стандартной библиотеки, новый для курса (json и random в модуле 9 были из неё же): itertools.combinations(range(len(points)), 2) перебирает все сочетания по два индекса из range(len(points)), каждый раз в порядке возрастания: для четырёх точек это пары (0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3) — зеркальных и повторных нет. Всего пар n × (n − 1) / 2: пять точек — десять пар. Расстояние между точками-кортежами считает math.dist(a, b) — та же теорема Пифагора, что с math.sqrt в модуле 3, но готовой функцией: math.dist((0, 0), (60, 80)) — это 100.0. Отсортировать пары по расстоянию — key=lambda t: t[2]: ключ берёт третий элемент кортежа.

Списковое включение из модуля 4 — стенография «цикл с append» — в полной форме выглядит так: [f(x) for x in xs if p(x)]. Читается по порядку: for перебирает xs, if фильтрует исходные x (те, у которых p(x) истинно), выражение слева превращает каждый прошедший в f(x). Это ровно цикл result = [], внутри for x in xs:, внутри if p(x): result.append(f(x)). Проверка: [d * 2 for d in [10, 25, 40] if d > 15] — это [50, 80]: фильтр оставил 25 и 40, удвоение их превратило. Включение уместно, когда внутри одна трансформация и один фильтр; вложенные условия, вложенные циклы и побочные эффекты (print, изменение внешних переменных) — повод вернуться к явному циклу: включение читается как формула, а формула в три этажа хуже явного цикла.