How much slower is dict indexing vs. list indexing?

[Steve Holden]

Emin wrote:
> Dear Experts,
> 
> How much slower is dict indexing vs. list indexing (or indexing into a
> numpy array)? I realize that looking up a value in a dict should be
> constant time, but does anyone have a sense of what the overhead will
> be in doing a dict lookup vs. indexing into a list? Some ad hoc tests
> I've done indicate that the overhead is less than 15% (i.e., dict
> lookups seem to take no more than 15% longer than indexing into a list
> and there doesn't seem to be much difference in indexing into a list
> vs. a numpy array).
> 
> The reason I ask is because I'm wondering how hard I should work to
> compute and store an index into a list to avoid repeated hash table
> lookups. From my tests, it looks like the answer is basically "don't
> bother". Does anyone have information, thoughts, or comments on this?
> 
I think "don't bother" is a good conclusion. Tim Peters has led the 
charge to (as he might put it) "optimize the snot" out of the dict 
implementation. Anything you do in Python to speed up access is likely 
to add more to execution time than you might save by not exercising the 
C-based dict lookup code.

What technique were you thinking of to look up the cached index values 
in Python, just as a matter of curiosity? Storing them in a dict? It 
would be hard to think of a faster way ... ;-)

regards
  Steve
-- 
Steve Holden       +44 150 684 7255  +1 800 494 3119
Holden Web LLC/Ltd          http://www.holdenweb.com
Skype: holdenweb     http://del.icio.us/steve.holden
Blog of Note:          http://holdenweb.blogspot.com