search

haskell-streaming / streaming

An optimized general monad transformer for streaming applications, with a simple prelude of functions
BSD 3-Clause "New" or "Revised" License
158 stars 30 forks source link

Improve sliding window min/max #96

Open treeowl opened 4 years ago

treeowl commented 4 years ago

95 added sliding window min/max functions with big-O optimal amortized bounds. But a new minimum/maximum can force a pause proportional to the number of elements in the window. If we instead use a more careful sorted list representation, we should be able to cut the pauses to logarithmic time. A relatively simple approach would use a finger tree with a particular monoid described in the Hinze–Paterson paper on 2–3 finger trees, but we can probably tweak it a tad to do better without much difficulty. I don't know if there are more specialized structures that can do even better.

treeowl commented 4 years ago

@kccqzy, you may be interested in this, since you came up with the current implementation.

treeowl commented 4 years ago

One theoretical concern: with current processors, I estimate it will take on the order of a century to overflow the 64-bit counter. If computers get fast enough, that could get unacceptably short. If we want, we can check for overflow. When we detect it, we can subtract the oldest count from each one in the window (which we'll still assume has under 2^64 elements).