efficient running median
Raymond Hettinger
python at rcn.com
Tue Oct 13 19:40:35 EDT 2009
On Oct 13, 11:57 am, sturlamolden <sturlamol... at yahoo.no> wrote:
> On 13 Okt, 18:33, Paul Rubin <http://phr...@NOSPAM.invalid> wrote:
>
> > 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.
Right. See http://code.activestate.com/recipes/269554/ for a sample
implementation in Python.
Raymond
More information about the Python-list
mailing list