CS
Задачник Базовый курс EN

Задача

Устойчивая оценка времени

замеры сортировка аналитика

Замер повторили n раз и получили n чисел — время каждого запуска в миллисекундах. Как в статье о честных замерах, посчитайте по ним:

  1. минимум;
  2. медиану;
  3. среднее арифметическое всех замеров;
  4. среднее без выбросов: среднее тех замеров x, для которых Q₁ − 1,5·(Q₃ − Q₁) ≤ x ≤ Q₃ + 1,5·(Q₃ − Q₁);
  5. сколько замеров выброшено как выбросы.

Квантиль уровня p определяется так: отсортируем замеры по возрастанию, v₀ ≤ v₁ ≤ … ≤ vn−1, возьмём позицию i = p·(n − 1), её целую часть ⌊i⌋ и дробную f. Квантиль равен v⌊i⌋ + (v⌊i⌋+1 − v⌊i⌋)·f (если ⌊i⌋ — последний индекс, то просто v⌊i⌋). Медиана — квантиль уровня 0,5, Q₁ и Q₃ — уровней 0,25 и 0,75. Так же считает numpy.quantile по умолчанию.

Вход

В первой строке n (1 ≤ n ≤ 200 000), во второй — n положительных чисел, не больше 10⁴, с шестью знаками после точки.

Выход

Пять строк: минимум, медиана, среднее, среднее без выбросов — с погрешностью не больше 10⁻⁶ — и целое число выброшенных замеров.

Примеры

Пример 1

Вход
10
1.280000 1.310000 1.270000 4.170000 1.300000 1.290000 1.330000 1.280000 2.950000 1.320000
Выход
1.270000
1.305000
1.750000
1.297500
2

Ограничения

Время · Python
4000 мс
Время · Go
1000 мс
Память
256 МБ
Проверка
8 тестов

Разбор

Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.

1Подсказка 1

Минимум и среднее считаются за один проход. Для медианы и квартилей нужен порядок. Сколько стоит его получить?

2Идея

Сортируем копию замеров один раз — и все квантили берутся из отсортированного массива по формуле из условия. Дальше один проход по замерам: оставляем те, что внутри «ограды» [Q₁ − 1,5·IQR, Q₃ + 1,5·IQR], где IQR = Q₃ − Q₁ — межквартильный размах. Это правило Тьюки, тот же критерий, по которому рисуют «усы» в ящичковых диаграммах.

3Разбор

Функция квантиля: позиция i = p·(n − 1), берём два соседних элемента и интерполируем. При n = 1 обе позиции — нулевой элемент, и все квантили равны единственному замеру. При чётном n медиана оказывается полусуммой двух средних элементов — формула даёт это сама, без особого случая.

Деления на ноль не будет: хотя бы один замер всегда остаётся внутри ограды. При n ≥ 3 это элемент v⌊(n−1)/2⌋: его позиция не левее позиции Q₁ и не правее медианы, поэтому Q₁ ≤ v⌊(n−1)/2⌋ ≤ Q₃. При n ≤ 2 ограда содержит наименьший замер — проверьте подстановкой.

Посмотрите на первый пример: среднее 1,75 мс, а без выбросов — 1,30. Два медленных запуска из десяти утянули среднее на треть вверх. Минимум и медиана к ним почти не чувствительны.

3+Решение
4Сложность

Сортировка O(n log n), остальное O(n). Можно обойтись и без полной сортировки: квантиль находится за O(n) в среднем быстрым выбором. Для 200 000 чисел разница незаметна, для миллиардов — существенна.

5Типичные ошибки
  • Медиана как v[n // 2]. При чётном n это верхний из двух средних, а нужна их полусумма.
  • Квартили по индексу n // 4. Другое определение квантиля даёт другие числа. Определений в статистике около десятка; в задаче — одно конкретное, то же, что в numpy по умолчанию.
  • Отбрасывание по среднему ± 3 сигмы. Распространённое правило, но для несимметричного распределения замеров оно плохо работает: хвост раздувает сигму и прячет сам себя.

Алгоритмы задачи

TEC Приём Как честно измерить скорость Повторы, прогрев, медиана и минимум, timeit и testing.Benchmark — и типичные способы обмануть себя замером. повторов столько, чтобы замер шёл хотя бы десятую долю секунды 1 задача SRT Алгоритм Быстрый выбор k-й по величине без сортировки: разбиение и одна ветка вместо двух — O(n) в среднем, медиана медиан — всегда. O(n) в среднем 1 задача
Каталог алгоритмов