efficient running median

[Janto Dreijer]

On Oct 13, 9:59 pm, Paul Rubin <http://phr...@NOSPAM.invalid> wrote:
> sturlamolden <sturlamol... at yahoo.no> writes:
> > > The obvious way to compute a running median involves a tree structure
> > > so you can quickly insert and delete elements, and find the median.
> > > That would be asymtotically O(n log n) but messy to implement.
>
> > QuickSelect will find the median in O(log n) time.
>
> That makes no sense, you can't even examine the input in O(log n) time.

True. I think he means O(n).
I've tried wrapping the lesser-known nth_element function from the C++
STL (http://www.cppreference.com/wiki/stl/algorithm/nth_element).
Unfortunately it seems the conversion to std::vector<double> is quite
slow...I'll have a look again. Will probably have to rewrite my whole
median_filter function in C++ to avoid unnecessary conversions.

> Anyway, the problem isn't to find the median of n elements.  It's to
> find n different medians of n different sets.  You might be able to
> get close to linear time though, depending on how the data acts.

Yes, that's what I've been hoping for. If I want it reeeeaaally fast
I'll have to figure out how to do that.

Thanks
Janto