By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
440,905 Members | 900 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 440,905 IT Pros & Developers. It's quick & easy.

dictionary lookup table?

P: n/a
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(sortedList[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


Jul 18 '05 #1
Share this Question
Share on Google+
2 Replies


P: n/a
"John Mudd" <mu**@vex.net> wrote in message
news:ma************************************@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

Jul 18 '05 #2

P: n/a
In article <vq************@corp.supernews.com>,
"Francis Avila" <fr***********@yahoo.com> wrote:
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.


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
Jul 18 '05 #3

This discussion thread is closed

Replies have been disabled for this discussion.