Implement SortMedian in a different, simple interface

[paulharris]

Hi,

I am thinking of utilising the SortMedian algorithm (looks great!), but would need it shoe-horned into a different interface. I can either do it myself, or I can do it in collaboration, if you are interested.

For me, my requirements are:

• C++, templated
• percentile-orientated rather than pure median (50%ile)
• ability to push and pop items on, rather than feed the whole vector
• able to use indexes rather than numbers (or numbers directly - use template to achieve this)
• return the percentile as an index
• return the percentile as a pair of weighted indexes

for the weighted result, in the case of the median, its for the situation where the median is half way between two items. so each item would be weighted 50%. For a different percentile, the weighting would be something else, eg 20% and 80% (0.2 and 0.8) for example.

I imagine an interface like this:

template <typename T, class Compare>
class RollingPercentile {
  Compare compare;
public:
   RollingPercentile( double percentile, size_t estimated_window_size, Compare compare );
   void push( T new_value );
   void pop( T old_value );
   T result() const;

    struct Weighted {
       T a_value; double a_weight;
       T b_value; double b_weight;
    };
    Weighted weighted_result() const;
};

Compare could either be a lessthan function, or a compare --> -1, 0,+1 kind of function, depending on what is required for the internal algorithm.

So T can be (eg) an integer index, and compare can do the comparision as required, meaning the result will be the index of the percentile item, so can be used to identify the actual item in question, rather than just the percentile value.

estimated_window_size helps for reserve()ing space for vectors, but window size may grow to be bigger. Could instead be max_window_size in my particular case.

So, would anyone else have a need for such a class? Would be cool if it could be added to boost as well.

Oh and I'd probably also try and port it to Javascript.

cheers, Paul

[suomela]

Hello Paul,

Thanks for your interest in this algorithm!

You are absolutely right, to use this algorithm in a general-purpose library, you will need a better interface. The current implementation & interface are designed primarily with ease of testing and benchmarking in mind.

I don't think I will have time in near future to implement a better interface, but if you have time to work on it, it would be great! I would be happy to e.g. advertise your implementation here and elsewhere, and I can also try to help with testing and debugging your implementation if needed.

Regarding the interface that you proposed: I think I would remove the pop function, and use "window_size" instead of "estimated_window_size" in the constructor.

Regarding a JavaScript port: one already exists, I will put it online soon, but again the interface is similar to the C++ version, so some adaptation will be needed to suit your needs.

Kind regards, Jukka

[suomela]

You can now find the JavaScript implementation here: https://github.com/suomela/median-filter-js

[paulharris]

Hi Jukka,

I appreciate whatever little time you can give me 😊

My window is of variable and unknown length, so the estimate is in there to help reserve memory up front,

The items in the window are added and removed as data goes in and out of the window,

Perhaps push, pop, should be add, remove. But will need to remove items... That is possible, right?

Cheers, Paul On 8 Nov 2014 03:46, "Jukka Suomela" notifications@github.com wrote:

Hello Paul,

Thanks for your interest in this algorithm!

You are absolutely right, to use this algorithm in a general-purpose library, you will need a better interface. The current implementation & interface are designed primarily with ease of testing and benchmarking in mind.

I don't think I will have time in near future to implement a better interface, but if you have time to work on it, it would be great! I would be happy to e.g. advertise your implementation here and elsewhere, and I can also try to help with testing and debugging your implementation if needed.

Regarding the interface that you proposed: I think I would remove the pop function, and use "window_size" instead of "estimated_window_size" in the constructor.

Regarding a JavaScript port: one already exists, I will put it online soon, but again the interface is similar to the C++ version, so some adaptation will be needed to suit your needs.

Kind regards, Jukka

— Reply to this email directly or view it on GitHub https://github.com/suomela/median-filter/issues/1#issuecomment-62201256.

[suomela]

Hello Paul,

I am sorry but I do not think this algorithm is a good choice if you need a variable-length window. I do not know any easy way to achieve that. Maybe you might consider a heap-based algorithm instead? For example, https://gist.github.com/ashelly/5665911 and https://github.com/craffel/median-filter ?

[paulharris]

Sorry to hear it :( Yes I guess heap-based is the next best.

Thanks! Paul

On 5 December 2014 at 04:44, Jukka Suomela notifications@github.com wrote:

Hello Paul,

I am sorry but I do not think this algorithm is a good choice if you need a variable-length window. I do not know any easy way to achieve that. Maybe you might consider a heap-based algorithm instead? For example, https://gist.github.com/ashelly/5665911 and https://github.com/craffel/median-filter ?

— Reply to this email directly or view it on GitHub https://github.com/suomela/median-filter/issues/1#issuecomment-65700378.