Velocity Reviews > fastest table lookup

# fastest table lookup

Neal D. Becker
Guest
Posts: n/a

 10-25-2004
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).

Michael J. Fromberger
Guest
Posts: n/a

 10-25-2004
In article <(E-Mail Removed)>,
"Neal D. Becker" <(E-Mail Removed)> 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

Peter Otten
Guest
Posts: n/a

 10-25-2004
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
Guest
Posts: n/a

 10-25-2004
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

Scott David Daniels
Guest
Posts: n/a

 10-25-2004
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
http://www.velocityreviews.com/forums/(E-Mail Removed)

Josiah Carlson
Guest
Posts: n/a

 10-25-2004

Jeff Shannon <(E-Mail Removed)> 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
Guest
Posts: n/a

 10-25-2004
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.

 Thread Tools

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is OffTrackbacks are On Pingbacks are On Refbacks are Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post Gummy ASP .Net 2 02-08-2007 01:21 PM Tales Mein ASP .Net 0 01-16-2006 09:39 PM photoguysept102004@yahoo.com Digital Photography 6 10-28-2004 11:33 AM Big Dave ASP .Net 1 10-07-2004 01:45 PM gerry ASP .Net 0 04-24-2004 09:21 AM

Advertisments