dictionary lookup table?

[John Mudd]

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.



#! /usr/bin/env python
import random
import time

dict = {}
list = []

n = 10000
n = 10000
for i in range(n):
str = '%s' % random.random()
list.append(str )
dict[str] = None # <-- seems a waste

sortedList = list[:]
sortedList.sort ()

t1 = time.time()
for i in range(n):
if sortedList[i] not in list:
print 'not found'
print 'List lookups: %.3f sec' % (time.time() - t1)

t1 = time.time()
for i in range(n):
if not dict.has_key(so rtedList[i]):
print 'not found'
print 'List lookups: %.3f sec' % (time.time() - t1)
~
~
~
~
~
:!lookup.py
List lookups: 28.848 sec
List lookups: 0.041 sec

Hit ENTER or type command to continue

[Francis Avila]

Re: dictionary lookup table?

"John Mudd" <mudd@vex.net > wrote in message
news:mailman.58 1.1068399182.70 2.python-list@python.org ...[color=blue]
> 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.[/color]

You ARE misusing both dictionaries AND lists, but not in the way you think:
[color=blue]
> dict = {}
> list = [][/color]

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

[David Eppstein]

Re: dictionary lookup table?

In article <vqt288ck2mgkd8 @corp.supernews .com>,
"Francis Avila" <francisgavila@ yahoo.com> wrote:
[color=blue]
> 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.[/color]

You gain in expressing more clearly the intent of your code.

--
David Eppstein http://www.ics.uci.edu/~eppstein/
Univ. of California, Irvine, School of Information & Computer Science