fastest table lookup

[Josiah Carlson]

Jeff Shannon <jeff at ccvcorp.com> wrote:
> 
> Neal D. Becker wrote:
> 
> >I need a fairly small lookup table, and I'm wondering which data python data
> >structure would be fastest.  I could use a list, tuple, dictionary, numeric
> >array, or maybe plain python array.  The table would be indexed by simple
> >integers and would be dense (filled).
> >  
> >
> 
> Which data structure will be fastest depends to some degree on the exact 
> usage that it's being put to, but in most cases I expect that a 
> dictionary will be the best bet.  IIRC, list (and tuple) indexing is 
> O(n) (with n=len(list)), while dictionary references are O(1).  In some 
> circumstances, it may (or may not) be possible to achieve further 
> speedup by using a python array or numarray, but unless you're already 
> planning on using numarray for other things, I'd consider its usage for 
> a lookup table to be a premature optimization.

Goodness, read the docs and source.  Lists and tuples are implemented as
arrays. They are /truely/ O(1) on read (they are not linked lists, as
you seem to imply).

Dictionaries, on the other hand, are hash tables that while not being
/truely/ O(1) on read, generally do pretty well, and are implemented
based on theoretical research in the area (again, read the source).

Do some reading.


 - Josiah