Скользящее окно

Возьмём «Войну и мир» и пустим по ней окно из тысячи слов: сначала слова с первого по тысячное, потом со второго по 1001-е, и так до конца. Сколько в каждом окне разных слов? Окон 435 тысяч, и если каждое пересчитывать заново, это 435 миллионов действий. А если помнить, что в окне лежит, на каждый сдвиг хватает двух: одно слово вошло, одно вышло. Вот что получилось.

В окне из тысячи слов у Толстого бывает от 353 до 683 разных. Самое пёстрое место — в четвёртом томе, сцена, где Кутузов говорит с солдатами: повествование, описание, речь, всё вперемешку. Самое однообразное — вторая часть эпилога, рассуждение о свободе и необходимости: одни и те же слова «поступок», «причина», «время», «большему или меньшему» повторяются раз за разом. Длина окна влияет на числа, но не на картину: эпилог однообразен при любом окне.

Идея

Окно шириной w сдвигается на один элемент: справа один входит, слева один выходит. Если ответ для окна можно поправить по этим двум элементам — прибавить и вычесть, увеличить и уменьшить счётчик, — то на все окна уходит O(n) действий, а не O(n·w), как при пересчёте каждого окна заново.

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

Скользящее среднее

Самое частое окно в жизни — скользящее среднее: среднее за последние w дней, посчитанное для каждого дня. Ниже 85 лет среднесуточной температуры Алматы. Подвигайте ширину окна.

При окне в несколько дней линия повторяет погоду. При окне в месяц остаются времена года: волна от −4° в среднем за январь до +22° за июль. При окне в год сезоны исчезают — в окне всегда ровно по одному каждого месяца, — и видны медленные изменения от года к году. На каждое положение окна уходит одно сложение и одно вычитание, а без окна на десятилетнее среднее понадобилось бы сто миллионов сложений.

Реанализ — модельная оценка, и в его первых десятилетиях данных меньше, поэтому ранним годам ряда стоит доверять осторожнее: самый тёплый год в ряду выходит 1941-й, и это скорее особенность реанализа тех лет, чем погода.

Окна по времени

Окно не обязано мериться числом элементов. «Сколько запросов за последнюю минуту», «сколько событий за сутки» — это окно по времени: правый край — текущее событие, левый подтягивается, пока окно длиннее заданного срока. В окне может лежать то ноль событий, то тысяча — это те же два указателя, только граница считается в секундах.

Самые плотные сутки в каталоге землетрясений 2015–2025 годов начинаются 29 июля 2025 года с землетрясения магнитудой 8,8 у Камчатки: за следующие 24 часа — 166 толчков силой от пяти, за самый плотный час — 38. Ограничители частоты в веб-сервисах устроены так же: держат окно последних запросов и отказывают, когда в нём больше разрешённого. Это вторая задача статьи.

Код

Скользящие средние для окон в неделю, год и десятилетие: самые холодные и самые тёплые периоды и сколько сложений на это ушло.

Окна по времени на каталоге землетрясений: самые плотные час, сутки и неделя.

Разнообразие слов: окно со счётчиками в хеш-таблице.

Сколько это стоит

O(n) сдвигов, каждый — O(1) для суммы и среднего, O(1) в среднем для счётчиков в хеш-таблице, O(1) амортизированно для максимума в монотонной очереди. Память — O(1) для суммы, O(w) для того, что нужно помнить о содержимом окна.

Есть две тонкости. Первая — числа с плавающей точкой: если тысячи раз прибавлять и вычитать дробные значения, накапливается ошибка, и скользящая сумма понемногу уплывает. Её лечат целыми числами (как здесь: температура хранится в десятых долях градуса), периодическим пересчётом с нуля или суммированием Кэхэна. Вторая — граница окна по времени: входит ли событие, случившееся ровно T секунд назад, — от этого меняется ответ, и это нужно решить явно.

Если окна разной ширины и запросы о них приходят вразнобой, а не по порядку, скользящее окно не подходит: тогда нужны префиксные суммы для сумм или дерево отрезков для максимумов.

Задачи

В первой окно со счётчиками ищет самое пёстрое и самое однообразное место в тексте; тесты — тома «Войны и мира» и английский перевод. Во второй окно по времени ограничивает частоту оповещений о землетрясениях.