fastest table lookup

Discussion in 'Python' started by Neal D. Becker, Oct 25, 2004.

  1. 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).
     
    Neal D. Becker, Oct 25, 2004
    #1
    1. Advertising

  2. In article <>,
    "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).


    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
     
    Michael J. Fromberger, Oct 25, 2004
    #2
    1. Advertising

  3. Neal D. Becker

    Peter Otten Guest

    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
     
    Peter Otten, Oct 25, 2004
    #3
  4. Neal D. Becker

    Jeff Shannon Guest

    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
     
    Jeff Shannon, Oct 25, 2004
    #4
  5. 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
     
    Scott David Daniels, Oct 25, 2004
    #5
  6. 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, 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
     
    Josiah Carlson, Oct 25, 2004
    #6
  7. Neal D. Becker

    Jeff Shannon Guest

    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.
     
    Jeff Shannon, Oct 25, 2004
    #7
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. gerry
    Replies:
    0
    Views:
    554
    gerry
    Apr 24, 2004
  2. Big Dave
    Replies:
    1
    Views:
    532
    =?Utf-8?B?Q293Ym95IChHcmVnb3J5IEEuIEJlYW1lcikgLSBN
    Oct 7, 2004
  3. Tales Mein

    form with a lookup table

    Tales Mein, Jan 16, 2006, in forum: ASP .Net
    Replies:
    0
    Views:
    346
    Tales Mein
    Jan 16, 2006
  4. s o
    Replies:
    0
    Views:
    505
  5. Gummy
    Replies:
    2
    Views:
    358
    Gummy
    Feb 8, 2007
Loading...

Share This Page