Двухстековый алгоритм для скользящего окна: агрегация без обратной операции
Two-Stack Sliding-Window Aggregation
Автор рассказывает о двухстековом алгоритме для вычисления агрегатов в скользящем окне, который работает за амортизированное O(1) и не требует обратной операции. В отличие от наивного подхода, страдающего от NaN и потери точности, метод поддерживает минимум, квантили, HyperLogLog и даже сумму с плавающей точкой. Приводятся реализация на Python и визуализация работы.
Шесть лет назад я придумал алгоритм для поддержания минимума/максимума в скользящем окне и опубликовал его на cs.stackexchange. Теперь я считаю этот алгоритм бессмысленным, потому что оказалось, что существует простой и эффективный алгоритм, решающий эту задачу для очень широкого класса агрегаций.