[SciPy-User] Moving median code

[Keith Goodman]

On Mon, Apr 25, 2011 at 9:01 AM, Keith Goodman <kwgoodman at gmail.com> wrote:
> On Mon, Apr 25, 2011 at 8:31 AM, J. David Lee <johnl at cs.wisc.edu> wrote:

>> In working on a project recently, I wrote a moving median code that is
>> about 10x faster than scipy.ndimage.median_filter. It utilizes a linked
>> list structure to store values and track the median value. If anyone is
>> interested, I've posted the code here (about 150 lines):
>>
>> http://pages.cs.wisc.edu/~johnl/median_code/median_code.c
>
> Does anyone have a feel for how the speed of a linked list approach
> would compare to a double heap?

Here's the speed comparison between using a link list and a double
heap for a moving window median:

    >> a = np.random.rand(1e5)
    >>
    >> window = 11
    >> timeit roly.slow.move_median(a, window)
    1 loops, best of 3: 2.57 s per loop
    >> timeit roly.linkedlist.move_median(a, window)
    100 loops, best of 3: 4.57 ms per loop
    >> timeit roly.doubleheap.move_median(a, window)
    100 loops, best of 3: 4.87 ms per loop
    >>
    >> window = 101
    >> timeit roly.linkedlist.move_median(a, window)
    10 loops, best of 3: 19.4 ms per loop
    >> timeit roly.doubleheap.move_median(a, window)
    100 loops, best of 3: 6.55 ms per loop
    >>
    >> window = 1001
    >> timeit roly.linkedlist.move_median(a, window)
    1 loops, best of 3: 206 ms per loop
    >> timeit roly.doubleheap.move_median(a, window)
    100 loops, best of 3: 7.76 ms per loop
    >>
    >> window = 10001
    >> timeit roly.linkedlist.move_median(a, window)
    1 loops, best of 3: 4.56 s per loop
    >> timeit roly.doubleheap.move_median(a, window)
    100 loops, best of 3: 10.2 ms per loop

The double heap is much faster except at small window widths. And even
then it is not far behind.

The code can be found here: https://github.com/kwgoodman/roly
and discussed here: http://groups.google.com/group/bottle-neck