Home Original page

efficient running median

Ethan Furman ethan at stoneleaf.us
Wed Oct 14 18:53:24 EDT 2009 
Janto Dreijer wrote:
> 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

I'm afraid I can't help any further.  Going from your post, I thought a 
quicker list implementation might be useful, but beyond that I have no 
knowledge to share.

Who said ignorance is bliss?  *hangs head*

~Ethan~
More information about the Python-list mailing list