Алгоритмы с нуля
Сортировка и поиск: движок запросов
Читать про сортировку и binary search — не то же самое, что встроить их в систему, которая обязана отвечать на множество запросов быстро. Постройте небольшой движок запросов для чтения: он сортирует данные один раз, а затем обслуживает запросы наличия, диапазона, медианы и порога — и докажите корректность и скорость каждого алгоритма собственными тестами и замерами.
Превратите ментальную модель юнита в рабочий движок: отсортируйте один раз как препроцессинг, реализуйте merge sort и quicksort с нуля, отвечайте на запросы через binary search и его варианты, найдите медиану через quickselect и подкрепите каждое утверждение о корректности и сложности доказательствами.
Постройте движок запросов над набором записей (у каждой числовой ключ и полезная нагрузка), который сортирует данные один раз и затем отвечает на поток запросов — наличие, диапазон, медиана и «наименьший ключ, чья накопленная сумма превышает T» — с помощью алгоритмов юнита, доказывая каждый тестами и замерами.
- Все тесты проходят, включая граничные случаи (пустой, один, все равны, отсортированный, обратно отсортированный), каждый сверен с эталоном перебором.
- Продемонстрированная разница по stable-свойству: распечатка до/после, показывающая, что merge sort сохраняет порядок равных ключей, а ваш quicksort — нет.
- Таблица замеров, показывающая, что время сортировки растёт примерно как n log n, а каждый запрос — O(log n) или O(n) (медиана) — измеренное, а не оценённое — на 10^3, 10^5, 10^6.
- Краткое резюме: какую сортировку вы бы отгрузили для этого движка и почему (stable против in-place памяти против худшего случая), и почему binary search и quickselect бьют пересканирование или пересортировку на каждый запрос.
- Добавьте эксперимент с защитой quicksort от O(n²): подайте уже отсортированный вход на quicksort с фиксированным последним pivot и на ваш рандомизированный, и постройте график роста времени, чтобы показать, что худший случай реален.
- Поддержите обновления: при вставке записи держите массив отсортированным вставкой через insertion-sort splice (сдвиг O(n)) и обсудите, когда пересортировка с нуля становится дешевле инкрементальной вставки.
- Обобщите запрос по порогу в переиспользуемый хелпер бинарного поиска по ответу, принимающий любой монотонный предикат, и переиспользуйте его для второй задачи (например, минимальная вместимость, чтобы уложить все записи в D корзин).
- Добавьте защиту от вырожденного входа в quickselect (median-of-medians или рандомизированный pivot) и покажите, что входа худшего случая больше не замедляет его.
Это цикл за каждой read-heavy системой: заплатите O(n log n) сортировки один раз, а затем отвечайте на запросы дёшево — O(log n) через binary search и его варианты lower/upper_bound, O(n) для медианы через quickselect и O(log диапазона-ответов) для монотонных пороговых запросов. Выбор сортировки (stable merge против in-place quicksort), защита pivot у quicksort и доказательство каждого алгоритма тестами и замерами — это ровно та инженерия, которую вы повторите на реальных данных.