Providing type for chronological running median

[Enyium]

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:

• https://docs.rs/medianheap

  • Has maximum size, but doesn't remove chronologically. push() docs:

    /// When max_size is set and the heap is full, this will remove /// - the smallest item if the pushed item is greater than (>) the current median, /// - the largest item, if the pushed item is less than (<) the current median, or /// - both the smallest and the largest item, if the pushed item is equal (==) to the current median.

• https://docs.rs/median-accumulator

  • Can't delete single values.

• https://docs.rs/medians

  • Seems to do the work every time you need the median.

• https://docs.rs/yata/latest/yata/methods/struct.SMM.html

  • Only allows floats as values and requires an initial value.

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]

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.