efficient running median
Janto Dreijer
jantod at gmail.com
Tue Oct 13 17:15:44 EDT 2009
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
More information about the Python-list
mailing list