События
во временном окне

Категория

Алгоритм

Уровень

Средний

Опирается на

Главы 9.2–9.4; модуль 8: монотонность указателей

Зачем это знать

Так считают запросы и ошибки «за последние N секунд»

§1Условие задачи

Сервер записывает момент каждого запроса в секундах от начала суток. Нужно узнать, сколько запросов в самый нагруженный промежуток длиной w секунд, — например, чтобы сравнить с лимитом «не больше 100 запросов за минуту». Вопросы к условию разобраны в главе 9.2, §7; здесь условие записано в окончательном виде.

§2Окно на оси времени

В задачах глав 9.3 и 9.4 окно — это k соседних элементов списка. Здесь окно — отрезок времени: в нём может оказаться и одно событие, и десять, в зависимости от того, как плотно они идут. Блок ниже показывает события примера на оси времени и окно длиной w. Кнопки переставляют начало окна на следующее событие, длину окна можно менять.

Начало окна достаточно ставить только на моменты событий. Если окно начинается в момент, где события нет, его можно сдвинуть вправо до первого события внутри. Слева от нового начала событий в окне не было, поэтому ни одно не теряется. Правая граница сдвигается вместе с началом, и в окно могут только добавиться события. Поэтому лучшее окно всегда начинается с какого-то события, и окон для проверки не больше n.

При w = 5 переставьте окно на момент 10: в него попадают 10, 12, 13 и 14. Момент 15 уже не входит — правая граница открытая. Поставьте w = 9 и окно на момент 1: событие 10 оказывается ровно на границе 1 + 9 = 10 и в окно не попадает.

§3Решение перебором

Перебор следует из §2 напрямую: для каждого события i поставить окно началом на times[i] и посчитать события, которые в него попадают. Список отсортирован, поэтому достаточно смотреть события с индекса i и дальше.

def max_events_brute(times, w):
    if w <= 0:
        raise ValueError("w должно быть больше 0")
    best = 0
    for i in range(len(times)):
        count = 0
        for j in range(i, len(times)):
            if times[j] < times[i] + w:
                count += 1
        best = max(best, count)
    return best

Внутренний цикл для события i делает n − i проверок, всего n·(n + 1) / 2, время O(n²). При ста тысячах запросов за сутки это около 5·10⁹ проверок. Перебор можно ускорить: внутренний цикл прерывать на первом событии за окном, но в худшем случае, когда все события попадают в одно окно, проверок столько же.

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

§4Два указателя по времени

Окно можно описать двумя указателями на события: l — первое событие в окне, r — последнее. Окно — [times[l], times[l] + w), событий в нём r − l + 1. Правый указатель проходит все события по одному. Левый двигается, когда событие times[l] уже не помещается в одно окно с times[r], то есть когда times[r] − times[l] ≥ w.

1. Старт. l = 0, best = 0.
2. Новое событие. Для каждого r по порядку событие times[r] добавляется в окно справа.
3. Сжатие слева. Пока times[r] − times[l] ≥ w, событие times[l] слишком старое: сдвинуть l. Это цикл while, потому что старых событий может быть несколько.
4. Подсчёт. Теперь все события с l по r помещаются в окно, их r − l + 1. Обновить best.

Отличие от глав 9.3 и 9.4 — в шаге 3. Там при сдвиге уходил ровно один элемент, и вместо цикла хватало одного вычитания. Здесь длина окна постоянна по времени, а число событий в нём меняется: после паузы из окна уходит сразу несколько событий.

§5Сборка функции и песочница

Правило из §4 записывается функцией из десяти строк. Расставьте их по порядку. Обратите внимание на отступы: l += 1 стоит внутри while, а обновление best — после него, на уровне тела for.

>>> l = 0
>>> for r in range(4):
...     while r - l >= 2:
...         l += 1
...     print(r, l)
...
0 0
1 0
2 1
3 2

Напишите функцию сами. Восемь тестов: пример, событие на правой границе, одинаковые моменты, пустой список, одно событие, неверное w, неизменность входа и сравнение с перебором окон на трёхстах случайных списках.

§6Код и пошаговый прогон

def max_events(times, w):
    if w <= 0:
        raise ValueError("w должно быть больше 0")
    best = 0
    l = 0
    for r in range(len(times)):
        while times[r] - times[l] >= w:
            l += 1
        best = max(best, r - l + 1)
    return best

Прогон на примере из §1. Голубые ячейки — события окна, бледные — события, которые из окна уже ушли. На шагах 14–19 видно, чем это окно отличается от окна по элементам: событие 10 приходит после паузы, и цикл while трижды сдвигает l, убирая события 1, 3 и 4. На шагах 32–39 то же повторяется для события 30.

§7Две ошибки границы

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

Ошибку границы из тестов ловят test_right_edge и сравнение с перебором. На примере из §1 обе версии сравнения дают 4, и без отдельного примера на границу ошибка была бы незаметна. Поэтому вопрос «[s, s + w) или [s, s + w]?» задают до кода и сразу записывают пример на эту границу.

§8Проверьте себя