[Python-Dev] PyBench DictCreation (was Re: Performance compares)

[Guido van Rossum]

> Guido van Rossum wrote:
> > What's an association table?
> 
> A table of keys and values.  Values are looked up by looping over
> the table comparing each key until the correct one is found (ie.
> its O(n) where n is the size of the table).  For Python, the cost
> of doing compares probably outweighs the cost of doing the
> hashing, even for small tables.
> 
> Its not clear to me though if it would be a win.  Assuming that
> interned strings are the most common key, a assocation table with
> four entries would take on average two pointer compares to look
> up a value.
> 
>   Neil

I see.  At the cost of yet another algorithm, of course.

--Guido van Rossum (home page: http://www.python.org/~guido/)