roly: double heap implementation tweaks
Keith Goodman
heap implementation:
1. As suggested by David, don't calculate whether the window is odd or
even at each step through the data. That's a waste. An int can be
added to the struct, perhaps called odd whose value can be set at
initialization. Same can be done for the linked list. It will be
interesting to see how much difference it makes in speed.
2. To initialize the data in the struct I currently pass in a pointer
to the first element of the numpy array. The init function (C code)
then grabs as many elements as the window is wide. That's not
convenient when the input array is more than 1d. So I'd like to copy
the interface that David uses. Initialize the structure but then make
a function that fills the structure with one element at a time. We can
then fill the initial window by looping through the data on the cython
side instead of the C side.
If anyone would like to work on any of this either alone or together
or if you have ideas, let me know. It may take me a while to get to
it.
Or is it too early to optimize? Is there another algorithm that would be faster?
Keith Goodman
> There are two changes that would be nice to make to the current double
> heap implementation:
>
> 1. As suggested by David, don't calculate whether the window is odd or
> even at each step through the data. That's a waste. An int can be
> added to the struct, perhaps called odd whose value can be set at
> initialization. Same can be done for the linked list. It will be
> interesting to see how much difference it makes in speed.
>
> 2. To initialize the data in the struct I currently pass in a pointer
> to the first element of the numpy array. The init function (C code)
> then grabs as many elements as the window is wide. That's not
> convenient when the input array is more than 1d. So I'd like to copy
> the interface that David uses. Initialize the structure but then make
> a function that fills the structure with one element at a time. We can
> then fill the initial window by looping through the data on the cython
> side instead of the C side.
I made both of the changes above and pushed to the repo.
I think I'm pretty much done.
Wes, do you have plans to work on a skiplist-based moving median? How
do you think its performance will compare to a double heap?
Wes McKinney
> runtime, so there may not be much point for the moment-- I might get
> to it sometime this summer but unlikely in the coming weeks.
>
> - Wes
Hey all,
Wow, it's been a long time. I had a tinker with the skiplist-based
moving median in pandas today and wrote a C implementation of the
skiplist data structure:
https://github.com/wesm/pandas/blob/master/pandas/src/skiplist.h
There is a also a Cython header (skiplist.pxd) in there so it can be
used in Cython
There's probably a better way to implement this since I'm no C expert,
but I was curious about the performance. It appears that the double
heap implementation in bottleneck is about 6 times or so faster.
arr is a length-10000 float64 array
In [5]: timeit bn.move_median(arr, 1000)
1000 loops, best of 3: 781 us per loop
In [6]: import pandas._sandbox as sbx
In [8]: timeit sbx.roll_median(arr, 100, 100)
100 loops, best of 3: 5.1 ms per loop
The C version is in turn about 7-8x faster than the current pure
Cython one (which has a "too much Python" problem).
- Wes
Wes McKinney
(just sent this to keith-only by accident)
Pardon me, the double-heap is about *10x* faster:
In [12]: timeit sbx.roll_median(arr, 1000, 1000)
100 loops, best of 3: 7.83 ms per loop
Keith Goodman
> Wow, it's been a long time. I had a tinker with the skiplist-based
> moving median in pandas today and wrote a C implementation of the
> skiplist data structure:
>
> https://github.com/wesm/pandas/blob/master/pandas/src/skiplist.h
Nice. Now we have 4 different moving window medians: skip list, linked
list, double heap, python for loop.