Why is if a in dict.keys() so slow.....

Fredrik Lundh effbot at telia.com
Thu Apr 13 06:33:56 EDT 2000


Martin Franklin <martin.franklin at waii.com> wrote:
> Just thought i'd throw this out there....
>
> This is very slow:-
>
> if split[0] in map_dict.keys():
>     print 'found it!', map_dict[split[0]]
> else:
>     print 'not found'
>
> Compared to:-
>
> try:
>     print 'found it!',map_dict[split[0]]
>
> except:
>     print 'Not found'
>
> The dictionary had about 40000 key:value pairs and I needed to
> look through it 250000 times.....
>
> Question is why?

any special reason you couldn't figure this out from
the documentation? ;-)

if you read up on dictionaries and the "in" operator,
you'll find that:

    keys() creates a list of 40,000 items, and "in"
    does a linear search in that list...

    ...while [key] looks the key up in a data structure
    which is carefully designed for fast lookups.

(btw, the try/except version is faster only if you have
more hits than misses.  otherwise, you may get better
performance by using "if dict.has_key(key)".)

</F>





More information about the Python-list mailing list