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

Providing type for chronological running median #2

Open
Enyium opened this issue Aug 11, 2024 · 1 comment
Open

Providing type for chronological running median #2

Enyium opened this issue Aug 11, 2024 · 1 comment

Comments

@Enyium
Copy link
Contributor

Enyium commented Aug 11, 2024

Crate base module docs:

A library to keep track of a running median of a sequence of numbers.

The library helps me with that. It's better suited for a chronological running median than:

However, if one wants a chronological running median with your crate, one still has to do extra work. To achieve this, I use your crate like this:

vec_deque.push_back(newest_value);
median_heap.push(newest_value);

if vec_deque.len() > MAX_SAMPLES {
    median_heap.delete(&vec_deque.pop_front().unwrap());
}

This crate's MedianHeap isn't really running as per my definition of it - like in "running average" or (which is the same) "moving average", which to me implies that old values automatically fall away, based on a maximum number of values.

So, would it be possible to provide a ready-made type for a running median, even if just implemented with a VecDeque and a MedianHeap? Or is there an efficient algorithm that doesn't involve data duplication that you have in mind?

@Vigintillionn
Copy link
Owner

You are indeed right, my wording in the crates description might be wrong. I've been doing some tinkering with some things that came to mind but I can't seem to avoid data duplication. I've tried some stuff with BTrees. I'll do some more tests. I would love to implement a ready made type using the VecDeque you used, but first I'll see if there's any way to avoid data duplication.

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

2 participants