How to iterate through two dicts efficiently

Peter Otten __peter__ at
Tue Jul 19 13:05:52 CEST 2011

J wrote:

> I am looking to improve the performance of the following piece of Python code:-
> for cc in StatusContainer:
>     for srv in StatusContainer[cc]:
>         for id in StatusContainer[cc][srv]['RECV']:
>             if id in StageContainer['13']:
>                 StatusContainer[cc][srv].setdefault('ACK', []).append(id)
>             elif id in StageContainer['14']:
>                 StatusContainer[cc][srv].setdefault('NACK', []).append(id)
>             else:
>                 if id in StageContainer['504'] or id in StageContainer['505']:
>                     StatusContainer[cc][srv].setdefault('RETRY', []).append(id)

> Someone in a different forum suggested that I use 'binary search' to
> iterate through the dictionaries but like I mentioned before, I am still
> very new to programming and 'binary search' sounds a bit to complicated to
> me.  I was wondering if someone here can have a look at my code above and
> maybe re-write it using 'binary search' or any other way you may see fit
> and re-post the code here with some comments on what each section is
> doing?

Python's hash-based dictionaries are usually very fast; I doubt that binary search will 
help. I'd try replacing the inner loop with set arithmetic:

# untested
stage_ack = set(StageContainer["13"])
stage_nack = set(StageContainer["14"])
stage_retry = set(StageContainer["504"]) | set(StageContainer["505"])

for servers in StatusContainer.itervalues():
    for server in servers.itervalues():
        recv = set(server["RECV"])

        ack = recv & stage_ack
        nack = recv & stage_nack
        retry = recv & stage_retry

        if ack:
            server.setdefault("ACK", []).extend(ack)
        if nack:
            server.setdefault("NACK", []).extend(nack)
        if retry:
            server.setdefault("RETRY", []).extend(retry)

More information about the Python-list mailing list