Любители временных рядов, это для вас.

Часто вижу кошмарно неэффективные подсчёты rolling-признаков при обработке time series данных.
Например, использование rolling mean в pandas без доработок, std, корреляции, медианы и прочее туда же.

Почему?
Обычно соседние окна почти полностью пересекаются, отличаясь на 1 шаг. Пример: мы считаем суточное среднее какого-то ряда каждую минуту → тогда на первом шаге мы проанализируем промежуток [0:1440], на втором шаге — [1:1441], итого 1438 повторений вычисления. Таким образом, сложность подсчёта признака будет O(N*K), где N — количество точек в наборе данных, а K — количество наблюдений для подсчёта одной итерации фичи.

Как делать хорошо?
Решить простенькое уравнение рекурсии, в котором каждое последующее значение признака зависит от предыдущего.
То есть по-честному расписываем X_t - X_{t-1}.

Для rolling mean за k наблюдений тогда получится: mean(X)t = mean(X){t-1} + 1/n (X_t - X_{t-k})
Тогда первое значение мы по-прежнему считаем честно полным проходом, а все последующие стоят O(1).
Тогда посчитать статистику на всю историю будет стоить всего O(N), то есть в K раз дешевле.

Нюанс: накапливается ошибка, особенно с fp16 или fp32.
Чинится либо использованием fp128, если память позволяет, либо чекпоинтами, на которых мы пересчитываем значение «честно»
(в примере размер окна 1000)

Хорошо описано тут: https://laurentrdc.xyz/posts/rolling-stats.html