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