search multiple dictionaries efficiently?

[Duncan Booth]

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.