4 ms·
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 si
by farazbabar 2y ago
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.
- packetlost 2y agoI've implemented something similar! Except it was persistent and intended for non-volatile flash media. Was a lot of fun to implement.
- gotoeleven 2y agoHow does this work for max rather than sum?
- throwaway_1more 2y agoMax is not like sum, you can just maintain one value over the window and update from new ones arriving immediately?
- BoiledCabbage 2y agoYes, but how do you update your max when you drop old values. That's the issue with max forming a monoid and not a group. The whole point of the post is that this is easy to implement for sum, but is difficult for max. Posting how someone solves the problem for sum isn't really addressing anything new here.
- throwaway_1more 2y agoIf the value you dropped wasn't the max, no problem, if it was, you recompute over the window. It is amortized.