roly: horse race between linked list and double heap

[Keith Goodman]

We now have three moving median algorithms:

1. Slow python for loop (to make sure faster algorithms give the right output)
2. Linked list
3. Double heap

Which is fastest?

>> 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.

I used odd windows because the double heap does not yet average when
the window width is even. Next step is to add that feature.

For comparison, here's how long the moving window max takes (Richard
Harter's algorithm but ported to cython instead of wrapping the C code
as was done with the moving median double heap):

>> import bottlneck as bn
>> timeit bn.move_max(a, 10001)
1000 loops, best of 3: 1.67 ms per loop