Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Python > search multiple dictionaries efficiently?

Reply
Thread Tools

search multiple dictionaries efficiently?

 
 
Livin
Guest
Posts: n/a
 
      01-18-2006
I'm a noobie so please be easy on me. I have searched a ton and did not find
anything I could understand.

I'm using py2.3

I've been using Try/Except but this gets long with multiple dictionaries.

I found some code on web pages and such but cannot get them to work. Any
help is appreciated as I need to search multiple dictionaries for keys.



here's the code I found but cannot get to work...

dict_set = (self.dictHSdevices, self.dictHSevents, self.dictHSbtnDevices)
<-- /creates set of dictionaries/

/code to search the set/-->

val = [ d for d in dict_set if d[value] in dict_set ]
OR
for key, value in dict.iteritems(): pass




 
Reply With Quote
 
 
 
 
Paul McGuire
Guest
Posts: n/a
 
      01-18-2006
"Livin" <(E-Mail Removed)> wrote in message news:A3izf.418$MJ.192@fed1read07...
> I'm a noobie so please be easy on me. I have searched a ton and did not

find
> anything I could understand.
>
> I'm using py2.3
>
> I've been using Try/Except but this gets long with multiple dictionaries.
>
> I found some code on web pages and such but cannot get them to work. Any
> help is appreciated as I need to search multiple dictionaries for keys.
>
>
>
> here's the code I found but cannot get to work...
>
> dict_set = (self.dictHSdevices, self.dictHSevents, self.dictHSbtnDevices)
> <-- /creates set of dictionaries/
>
> /code to search the set/-->
>
> val = [ d for d in dict_set if d[value] in dict_set ]
> OR
> for key, value in dict.iteritems(): pass
>



>>> dict_set = [ {1:'a'}, {2:'b',3:'c'} ]
>>> def lookup(value):

.... for d in dict_set:
.... try:
.... return d[value]
.... except KeyError:
.... pass
.... raise KeyError(value)
....
>>> lookup(1)

'a'
>>> lookup(2)

'b'
>>> lookup(3)

'c'
>>> lookup(4)

Traceback (most recent call last):
File "<stdin>", line 1, in ?
File "<stdin>", line 7, in lookup
KeyError: 4
>>>



 
Reply With Quote
 
 
 
 
George Sakkis
Guest
Posts: n/a
 
      01-18-2006
Livin wrote:

> I'm a noobie so please be easy on me. I have searched a ton and did not find
> anything I could understand.
>
> I'm using py2.3
>
> I've been using Try/Except but this gets long with multiple dictionaries.
>
> I found some code on web pages and such but cannot get them to work. Any
> help is appreciated as I need to search multiple dictionaries for keys.
>
>
>
> here's the code I found but cannot get to work...
>
> dict_set = (self.dictHSdevices, self.dictHSevents, self.dictHSbtnDevices)
> <-- /creates set of dictionaries/
>
> /code to search the set/-->
>
> val = [ d for d in dict_set if d[value] in dict_set ]
> OR
> for key, value in dict.iteritems(): pass



If I understood correctly what you want to do, here's a one-liner that
does it:

def lookup(value, *dicts):
return [d.get(value) for d in dicts if value in d]

>>> a = {'x':1, 'y':2}
>>> b = {'y':4, 'z':7}
>>> lookup('y', a, b)

[2, 4]

It's not the *most* efficient way because value is looked up twice if
it is contained in the dictionary; if you absolutely need it to be as
efficient as possible and can't figure it out on your own, ask again
and someone will help you out.

George

 
Reply With Quote
 
gene tani
Guest
Posts: n/a
 
      01-18-2006

Livin wrote:
> I'm a noobie so please be easy on me. I have searched a ton and did not find
> anything I could understand.
>
> I'm using py2.3
>
> I've been using Try/Except but this gets long with multiple dictionaries.
>
> I found some code on web pages and such but cannot get them to work. Any
> help is appreciated as I need to search multiple dictionaries for keys.
>
>
>
> here's the code I found but cannot get to work...
>
> dict_set = (self.dictHSdevices, self.dictHSevents, self.dictHSbtnDevices)
> <-- /creates set of dictionaries/
>
> /code to search the set/-->
>
> val = [ d for d in dict_set if d[value] in dict_set ]
> OR
> for key, value in dict.iteritems(): pass


http://aspn.activestate.com/ASPN/Coo.../Recipe/305268
http://mail.python.org/pipermail/pyt...st/294519.html

(I think these may be a little different from what you're asking above,
since they search dicts sequentially and return 1st hit)

 
Reply With Quote
 
Duncan Booth
Guest
Posts: n/a
 
      01-18-2006
George Sakkis wrote:

> It's not the *most* efficient way because value is looked up twice if
> it is contained in the dictionary; if you absolutely need it to be as
> efficient as possible and can't figure it out on your own, ask again
> and someone will help you out.
>

How do you *know* it is not the *most* efficient way? Have you tried timing
different ways of approaching this problem and found that looking up the
value twice is slow?

I've tried timing dictionary lookups in the past, and the three obvious
solutions roughly come out as follows:

try/except is fastest when the value is in the dictionary, but it is a
*lot* slower if the exception gets thrown. If missing values are a very
rare occurrence this might be a good way to do it, but usually the code
doesn't read as well so its best to avoid. [0.26/4.11]

Test with the 'in' operator and then retrieving the value is the fastest
solution when the value isn't in the dictionary (it only does a single
lookup then), and is still fast when it is. [0.36/0.2]

Using the get method of the dictionary with a default value to be retrieved
if the key is not present is slower than using the 'in' operator in all
cases (it does beat try/except when an exception is thrown) [0.49/0.54]

The numbers above are the times produced in each case for a key present/key
missing using a simple test with timeit.py.

Part of the reason, BTW, that calling d.get(key,default) is slow is that is
also requires two dictionary lookups: one to find the get method and then
another to access the key in the dictionary, plus it has other overheads (a
method call) which test&get avoids.

These figures could of course be invalidated if the actual use is too far
from the simple string lookup I tried. For example if the key has a slow
hash function saving the second lookup would be worthwhile.
 
Reply With Quote
 
Ben Sizer
Guest
Posts: n/a
 
      01-18-2006
Duncan Booth wrote:
> Test with the 'in' operator and then retrieving the value is the fastest
> solution when the value isn't in the dictionary (it only does a single
> lookup then), and is still fast when it is. [0.36/0.2]
>
> Using the get method of the dictionary with a default value to be retrieved
> if the key is not present is slower than using the 'in' operator in all
> cases (it does beat try/except when an exception is thrown) [0.49/0.54]


Assuming those statistics are replicatable, it's quite unfortunate that
the obvious and concise way to do things works out more slowly than the
approach that you'd expect to take twice as long. Thankfully there
doesn't seem to be too many of these problems in Python.

--
Ben Sizer

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
updating dictionaries from/to dictionaries Brandon Python 12 08-15-2008 12:35 AM
Pickling dictionaries containing dictionaries: failing,recursion-style! lysdexia Python 6 12-02-2007 12:03 AM
pickling multiple dictionaries manstey Python 3 05-24-2006 11:38 PM
Store multiple dictionaries in a file Philipp H. Mohr Python 7 06-30-2005 02:26 PM
Pythonic search of list of dictionaries Bulba! Python 19 01-10-2005 08:51 PM



Advertisments