Purely Functional Sliding Window Aggregation Algorithm

[agnishom]

https://byorgey.github.io/blog/posts/2024/11/27/stacks-queues.html

[farazbabar]

This is similar to an approach I use but instead of a queue, I accomplish this using a ring buffer that wraps around and overwrites entries older than window size. We maintain a global window aggregate, subtract ring buffer slot aggregate for entries dropping out and accumulate new entries into new slot aggregate while adding it to the global aggregate. Everything is o(1) including reads, which just returns the global window aggregate.

[agnishom]

This is a very interesting algorithm which is more or less known in the folklore, but is still relatively obscure. I have used it as a part of temporal logic monitoring procedure: https://github.com/Agnishom/lattice-mtl/blob/master/src/Moni...

[Groxx → agnishom]

Not sure I'd call it obscure: https://leetcode.com/problems/maximum-subarray/

I've seen it in tech interviews for years.