efficient running median

[Janto Dreijer]

On Oct 13, 7:37 pm, Ethan Furman <et... at stoneleaf.us> wrote:
> Janto Dreijer wrote:
> > I'm looking for code that will calculate the running median of a
> > sequence, efficiently. (I'm trying to subtract the running median from
> > a signal to correct for gradual drift).
>
> > My naive attempt (taking the median of a sliding window) is
> > unfortunately too slow as my sliding windows are quite large (~1k) and
> > so are my sequences (~50k). On my PC it takes about 18 seconds per
> > sequence. 17 of those seconds is spent in sorting the sliding windows.
>
> > I've googled around and it looks like there are some recent journal
> > articles on it, but no code. Any suggestions?
>
> > Thanks
> > Janto
>
> You might look athttp://pypi.python.org/pypi/blist/0.9.4
>
> ~Ethan~

Very nice! I assume you mean I can use it to quickly insert items into
the sliding window?

Thanks
Janto