efficient running median

Dave Angel davea at ieee.org
Tue Oct 13 19:27:22 CEST 2009

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
Since the previous window is sorted, it should just be a "case of delete 
one, add one" in the sorted list.  And if that isn't fast enough, 
consider some form of tree.


More information about the Python-list mailing list