<br><br><div class="gmail_quote">On Wed, May 14, 2008 at 8:09 AM, Andrew Straw <<a href="mailto:strawman@astraw.com">strawman@astraw.com</a>> wrote:<br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
<div class="Ih2E3d"><br>
> I will post any new insights as I continue to work on this...<br>
><br>
</div>OK, I save isolated a sample of my data that illustrates the terrible<br>
performance with the binarysearch. I have uploaded it as a pytables file<br>
to <a href="http://astraw.com/framenumbers.h5" target="_blank">http://astraw.com/framenumbers.h5</a> in case anyone wants to have a look<br>
themselves. Here's an example of the type of benchmark I've been running:<br>
<br>
import fastsearch.downsamp<br>
import fastsearch.binarysearch<br>
import tables<br>
<br>
h5=tables.openFile('framenumbers.h5',mode='r')<br>
framenumbers=h5.root.framenumbers.read()<br>
keys=h5.root.keys.read()<br>
h5.close()<br>
<br>
def bench( implementation ):<br>
    for key in keys:<br>
        implementation.index( key )<br>
<br>
downsamp = fastsearch.downsamp.DownSampledPreSearcher( framenumbers )<br>
binary = fastsearch.binarysearch.BinarySearcher( framenumbers )<br>
<br>
# The next two lines are IPython-specific, and the 2nd takes a looong time:<br>
<br>
%timeit bench(downsamp)<br>
%timeit bench(binary)<br>
<br>
<br>
<br>
Running the above gives:<br>
<br>
In [14]: %timeit bench(downsamp)<br>
10 loops, best of 3: 64 ms per loop<br>
<br>
In [15]: %timeit bench(binary)<br>
<br>
10 loops, best of 3: 184 s per loop<br>
<br>
Quite a difference (a factor of about 3000)! At this point, I haven't<br>
delved into the dataset to see what makes it so pathological --<br>
performance is nowhere near this bad for the binary search algorithm<br>
with other sets of keys.<br>
<div><div></div><div class="Wj3C7c"></div></div></blockquote><div><br>It can't be that bad Andrew, something else is going on. And 191 MB isn's *that* big, I expect it should bit in memory with no problem.<br><br>
Chuck <br></div><br></div><br>