fastest table lookup
jcarlson at uci.edu
Mon Oct 25 22:07:41 CEST 2004
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.
More information about the Python-list