dictionary lookup table?

Francis Avila francisgavila at yahoo.com
Sun Nov 9 19:35:41 CET 2003


"John Mudd" <mudd at vex.net> wrote in message
news:mailman.581.1068399182.702.python-list at python.org...
> I must be missing something here.  It's clearly faster to lookup an item
> directly in a dictionary than to scan through a list.  So when I have a
> large lookup table I always load it in the form of a dictionary.  But it
> seems a waste.  I end up having to assign an artificial value to the
> dictionary entry.  Below I assign the value "None" to each dictionary
> entry.
>
> Is there a better way?  I feel like I'm misusing the dictionary.

You ARE misusing both dictionaries AND lists, but not in the way you think:

> dict = {}
> list = []

These lines obliterates the dict() and list() builtins!  Use different
names, like D, mydict, etc.

Now, to answer your question:
I don't think you are abusing the dictionary at all, but if you're using
Python 2.3, you can use the set module, which more closely matches the
semantics of your problem.  However, as of now the set module is implemented
with dictionaries anyway, so I don't see that you gain much.  (I think set
will be implemented as an extension later, though.)

Further, don't be too worried about "waste", because there's very little
waste here.  First of all, None is a singleton (hence the Python idiom
"something is None"), so there's no danger of Python possibly making
multiple copies of the item mapped to your key.  Secondly, dictionaries are
containers, like lists, so the key and item of a dictionary are just
references to an object.  You end up with (at most) twice as many references
in a dictionary as an equivalent list, but references are little more than
dressed-up pointers, and very cheap to store and use.  So what are you
worried about?

Finally, if you're worried about waste, why are you using Python? ;)  Python
saves your development time in exchange for the far cheaper resource of
memory and processor power.

If you want some more speed (although it looks plenty fast to me), try
experimenting with some other dictionary idioms.  Try "if key in
dictionary", "try: D[key]; except: print 'not found'", etc.  But I think
you'd be wasting more time than you'd gain, especially since optimization
obsessions can be hard to shake....
--
Francis Avila





More information about the Python-list mailing list