Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Python > fastest table lookup

Reply
Thread Tools

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

 
Reply With Quote
 
 
 
 
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
 
Reply With Quote
 
 
 
 
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

 
Reply With Quote
 
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

 
Reply With Quote
 
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)
 
Reply With Quote
 
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

 
Reply With Quote
 
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.

 
Reply With Quote
 
 
 
Reply

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 Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
What is the fastest way to pull data from an Oracle table? Gummy ASP .Net 2 02-08-2007 01:21 PM
form with a lookup table Tales Mein ASP .Net 0 01-16-2006 09:39 PM
Fastest 5 mp Digital Camera ? Fastest 4 mp Digital Camera? photoguysept102004@yahoo.com Digital Photography 6 10-28-2004 11:33 AM
Databinding to a lookup table in an edititemtemplate class Big Dave ASP .Net 1 10-07-2004 01:45 PM
populating an asp list box from a simple access lookup list (single column not a table) gerry ASP .Net 0 04-24-2004 09:21 AM



Advertisments