Программа курса Урок 136 из 148 · Победите своего Призрака
Победите своего Призрака

Без сортировки: отчёт о задержках

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

Сервис записывает, сколько занял каждый запрос, в целых миллисекундах. Запросы прерываются по тайм-ауту через 10 секунд, поэтому каждое значение от 0 до 10 000. Каждую минуту задача превращает около 20 000 значений в числа на дашборде дежурного: медиану, 90-й и 99-й процентили и худшее значение.

Процентиль по ближайшему рангу: p-й процентиль - наименьшее значение, такое что не меньше p% всех значений находятся на нём или ниже. При 20 значениях 90-й процентиль - 18-е по величине снизу.

Данные

values = [120, 85, 3000, 95, 110, 90, 100, 105, 80, 130]
# latency_report(values) -> {"p50": 100, "p90": 130, "p99": 3000, "max": 3000}

В этой задаче сортировка запрещена, вручную или библиотекой. Посмотрите, что вы знаете о значениях.

Твоя очередь

Напишите latency_report(values). values - непустой список целых чисел от 0 до 10 000 (около 20 000 штук). Верните {"p50", "p90", "p99", "max"}: 50-й, 90-й и 99-й процентили по ближайшему рангу (наименьшее значение, у которого не меньше p% значений находятся на нём или ниже) и наибольшее значение. Не меняйте список. Правило: никакой сортировки: никаких sorted(), .sort(), bisect.insort и никаких импортов heapq или statistics (они сортируют за вас).

Заметили проблему в этом уроке? Сообщите о ней · Спросить об этом уроке

Это упражнение откроется скоро

Закончи предыдущий урок, чтобы открылся этот. Весь курс бесплатный, аккаунт не нужен, и ты можешь прочитать этот урок прямо сейчас.