On Oct 13, 9:59 pm, Paul Rubin <http://phr...@nospam.invalid> wrote: > sturlamolden <sturlamol...@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 -- http://mail.python.org/mailman/listinfo/python-list
