Re: Efficient Running Median

Very nice. I have added a comment at the bottom, using a circular queue instead of a deque may be faster. Bye, bearophile -- http://mail.python.org/mailman/listinfo/python-list

Re: Efficient Running Median

In article <497af344-31b5-4d1a-9b1a-c3d82feb3...@j5g2000yqm.googlegroups.com>, Raymond Hettinger wrote: > >The performance of an IndexableSkiplist is similar to a B+tree but the >implementation in pure python is much simpler. Nice! Can you summarize why IndexableSkipList is simpler? -- Aahz (a

Efficient Running Median

I've updated the running median recipe to use a new algorithm with O (log n) updates for a large sliding window traversing a data stream. See http://code.activestate.com/recipes/576930/ The engine is a new collection class called IndexableSkiplist. It is like a regular skiplist as detailed at htt

Re: efficient running median

Based on Perreault + Hebert, here's python code for a rather different algorithm: - for quantized e.g. 8-bit data - runs faster for wider windows / slowly changing medians - no heaps, no trees: the only import is numpy, and even that's not essential http://stackoverflow.com/questions/1309263/rolli

Re: efficient running median

Yet another link: http://en.wikipedia.org/wiki/Median_filter --> Perreault + Hebert, Median Filtering in Constant Time, nice 6-page paper + 400 lines well-documented C code: http://nomis80.org/ctmf.html (for 2d images, dropping to 1d must be possible :) They're also in opencv, which I haven't trie

Re: efficient running median

Folks, approximate medians -- would you settle for 49 - 51 % ? -- open up new possibilities, and there's quite a lot of work on that, for huuuge datasets. A class of problems: from a data stream X1 X2 ... you want, every so often, a histogram / quantile summary / distribution estimator such tha

Re: efficient running median

On Oct 15, 12:41 pm, Raymond Hettinger wrote: > [Janto Dreijer] > > > I found a PDF by Soumya D. Mohanty entitled "Efficient Algorithm for > > computing a Running Median" (2003) by Googling. It has code snippets > > at the end, but it's not going to be a simple cut-and-paste job. It > > will take

Re: efficient running median

[Janto Dreijer] > I found a PDF by Soumya D. Mohanty entitled "Efficient Algorithm for > computing a Running Median" (2003) by Googling. It has code snippets > at the end, but it's not going to be a simple cut-and-paste job. It > will take some work figuring out the missing parts. See http://code.

Re: efficient running median

Janto Dreijer wrote: On Oct 13, 7:37 pm, Ethan Furman 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 me

Re: efficient running median

On Oct 14, 4:53 pm, Peter Otten <__pete...@web.de> wrote: > Some numbers: > > 10.197 seconds for running_median_scipy_medfilt > 25.043 seconds for running_median_python > 13.040 seconds for running_median_python_msort > 14.280 seconds for running_median_python_scipy_median > 4.024 seconds for runni

Re: efficient running median

Janto Dreijer wrote: > On Oct 13, 6:12 pm, Peter Otten <__pete...@web.de> 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). >>

Re: efficient running median

On Oct 14, 12:13 am, Paul Rubin wrote: > Janto Dreijer writes: > > Well, I don't have a lot of theoretical reasoning behind wanting to > > use a median filter. I have some experience applying it to images with > > very good results, so that was the first thing I trie

Re: efficient running median

On Oct 13, 7:37 pm, Ethan Furman 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

Re: efficient running median

On Oct 13, 6:33 pm, Paul Rubin wrote: > Janto Dreijer writes: > > 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). > > Is that a kno

Re: efficient running median

On 14 Okt, 00:03, Steven D'Aprano wrote: > Obviously to run in O(log n) you must have already built the tree. You don't need a tree. Quickselect is a partial quicksort. But my memory served me badly, quickselect is O(n). -- http://mail.python.org/mailman/listinfo/python-list

Re: efficient running median

On Tuesday, 13 October 2009 17:22:55 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

Re: efficient running median

On Oct 13, 6:12 pm, Peter Otten <__pete...@web.de> 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

Re: efficient running median

On Oct 13, 11:57 am, sturlamolden wrote: > On 13 Okt, 18:33, Paul Rubin 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

Re: efficient running median

Janto Dreijer writes: > Well, I don't have a lot of theoretical reasoning behind wanting to > use a median filter. I have some experience applying it to images with > very good results, so that was the first thing I tried. It felt right > at the time and the results looked good. If this is image

Re: efficient running median

On Tue, 13 Oct 2009 12:59:47 -0700, Paul Rubin wrote: > sturlamolden writes: >> > 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. >>

Re: efficient running median

On Oct 13, 8:29 pm, Dale Dalrymple wrote: > On Oct 13, 8:22 am, 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). > > ... > >  Any sugge

Re: efficient running median

On Oct 13, 9:59 pm, Paul Rubin wrote: > sturlamolden writes: > > > 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 t

Re: efficient running median

On 13 Okt, 18:33, Paul Rubin 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 t

Re: efficient running median

Janto Dreijer writes: > 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). Is that a known and valid technique of correcting for drift? Maybe what you really want is a

Re: efficient running median

sturlamolden writes: > > 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. That ma

Re: efficient running median

On Tue, Oct 13, 2009 at 10:22 AM, 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). > In the past, I've used the following algorithm which appr

Re: efficient running median

On Oct 13, 8:22 am, 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). > ... > Any suggestions? For a reference try: Comparison of algorithms

Re: efficient running median

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 wi

Re: efficient running median

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 wi

Re: efficient running median

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

efficient running median

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 (