Dictionary vs binary search lookups [was: Populating a dictionary, fast [SOLVED]]

[Francesc Altet]

A Tuesday 20 November 2007, Istvan Albert escrigué:
> On Nov 19, 2:33 pm, Francesc Altet <fal... at carabos.com> wrote:
> > Just for the record.  I was unable to stop thinking about this, and
> > after some investigation, I guess that my rememberings were
> > gathered from some benchmarks with code in Pyrex (i.e. pretty near
> > to C speed).
>
> Pretty interesting and quite unexpected.

Yeah, and also bogus :(

It turned out that in my previous benchmark, I've used plain numpy int 
arrays to do measurements, and when you extract an element out of a 
numpy array what you obtain is a *numpy scalar*, which is a different 
beast than a python (long) integer.  Unfortunately, pyrex does swallow 
it and happily converted to a long long C, but produces a wrong result.  
This looks like a pyrex fault, and I should report it to the pyrex 
list.

At any rate, with the corrected benchmarks using plain python lists 
instead (attached), the numbers are:

Calibrating loop...
Calibrating time: 1.458
Creating the dictionary...
Time for dict creation: 15.305
Timing queries with a dict...
Time for dict query: 11.632
Creating BinarySearch object...
Time for BinarySearch creation: 8.648
Timing queries with a BinarySearch...
Time for BinarySearch queries: 19.393

That is, dictionaries do lookups 1.7x faster than a binary lookup (1.42 
us/lookup vs 2.37 us/lookup), which is, I suppose, what is expected.  
Well, this seems the end of my 'peculiar' theory, but at least served 
to uncover what it seems a bug in pyrex :P

-- 
>0,0<   Francesc Altet     http://www.carabos.com/
V   V   Cárabos Coop. V.   Enjoy Data
 "-"
-------------- next part --------------
A non-text attachment was scrubbed...
Name: query_ext.pyx
Type: text/x-c++src
Size: 1217 bytes
Desc: not available
URL: <http://mail.python.org/pipermail/python-list/attachments/20071121/1902d7c7/attachment.c>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: gq-binary-search.py
Type: application/x-python
Size: 1736 bytes
Desc: not available
URL: <http://mail.python.org/pipermail/python-list/attachments/20071121/1902d7c7/attachment.bin>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: setup.py
Type: application/x-python
Size: 360 bytes
Desc: not available
URL: <http://mail.python.org/pipermail/python-list/attachments/20071121/1902d7c7/attachment-0001.bin>