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

Guido van Rossum guido@digicool.com
Fri, 18 May 2001 14:23:55 -0400

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