Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Improve sliding window min/max #96

Open
treeowl opened this issue May 24, 2020 · 2 comments
Open

Improve sliding window min/max #96

treeowl opened this issue May 24, 2020 · 2 comments

Comments

@treeowl
Copy link
Contributor

treeowl commented May 24, 2020

#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
Copy link
Contributor Author

treeowl commented May 25, 2020

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

@treeowl
Copy link
Contributor Author

treeowl commented May 25, 2020

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).

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant