> I will post any new insights as I continue to work on this...
>
OK, I save isolated a sample of my data that illustrates the terrible
performance with the binarysearch. I have uploaded it as a pytables file
to http://astraw.com/framenumbers.h5 in case anyone wants to have a look
themselves. Here's an example of the type of benchmark I've been running:
import fastsearch.downsamp
import fastsearch.binarysearch
import tables
h5=tables.openFile('framenumbers.h5',mode='r')
framenumbers=h5.root.framenumbers.read()
keys=h5.root.keys.read()
h5.close()
def bench( implementation ):
for key in keys:
implementation.index( key )
downsamp = fastsearch.downsamp.DownSampledPreSearcher( framenumbers )
binary = fastsearch.binarysearch.BinarySearcher( framenumbers )
# The next two lines are IPython-specific, and the 2nd takes a looong time:
%timeit bench(downsamp)
%timeit bench(binary)
Running the above gives:
In [14]: %timeit bench(downsamp)
10 loops, best of 3: 64 ms per loop
In [15]: %timeit bench(binary)
10 loops, best of 3: 184 s per loop
Quite a difference (a factor of about 3000)! At this point, I haven't
delved into the dataset to see what makes it so pathological --
performance is nowhere near this bad for the binary search algorithm
with other sets of keys.
_______________________________________________
Numpy-discussion mailing list
Numpy-discussion@scipy.org
http://projects.scipy.org/mailman/listinfo/numpy-discussion
