fastest table lookup

[Neal D. Becker]

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).

[Peter Otten]

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).

Here are some 2.3 timings to give you a head start:

$ python timeit.py -s"a = [1]" "a[0]"
1000000 loops, best of 3: 0.177 usec per loop
$ python timeit.py -s"a = 1," "a[0]"
1000000 loops, best of 3: 0.196 usec per loop
$ python timeit.py -s"a = {0:1}" "a[0]"
1000000 loops, best of 3: 0.21 usec per loop

Peter

[Jeff Shannon]

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.

Jeff Shannon
Technician/Programmer
Credit International

[Michael J. Fromberger]

In article <ma**************************************@python.o rg>,
"Neal D. Becker" <nd*******@verizon.net> 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).

My recommendation is that you implement the table, and test your
implementation on some representative cases. My sense is that for a
small, dense table indexed by integers, it would be difficult to beat
array indexing. But rather than taking my suppositions for it, why not
try it out and see?

-M

--
Michael J. Fromberger | Lecturer, Dept. of Computer Science
http://www.dartmouth.edu/~sting/ | Dartmouth College, Hanover, NH, USA

[Scott David Daniels]

Jeff Shannon wrote:

... IIRC, list (and tuple) indexing is O(n) (with n=len(list)), ...

Nope, that may be LISPish knowledge or some other linked list
implementation.
Python's tuple, list, and array (and Numeric array) indexing is O(1).

-Scott David Daniels
Sc***********@Acm.Org

[Josiah Carlson]

Jeff Shannon <je**@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

[Jeff Shannon]

Jeff Shannon 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, [...]

So it seems that I *didn't* remember correctly. Nevermind what I said
there. (I suspect I may have been thinking of insertions rather than
accesses...)

Anyhow, it's still true that the best option depends on the exact
usage. Make a test harness that will fairly closely mimic your
lookup-table usage, and test the performance of each type of data
structure. It should be a relatively easy and straightforward experiment...

Jeff Shannon
Technician/Programmer
Credit International.