Python dictionary: iterating and adding

2010-03-05

On one of my earlier articles about Python dictionaries Jay asks (I paraphrase): What if you want to add items to a dictionary whilst iterating? And what if you want those items to appear in the iteration? Python’s standard dictionary iterators won’t help you.

Here’s a plan:

  1. keep a set, visited of keys that you have already visited;
  2. get the set of keys from the dictionary and subtract visited, leaving you with a set of keys not yet visited, todo;
  3. visit each of the keys in todo;
  4. now we have visited each of the keys in todo, add those keys to visited;
  5. during the iteration the set of keys in the dictionary may have changed, so repeat from (2), stopping when todo is empty.
def iterall(adict):
    """Iterate over all the items in a dictionary,
    including ones which are added during the iteration.
    """
    visited = set()
    while True:
        todo = set(adict.keys()) - visited
        if not todo:
            break
        for k in todo:
            if k in adict:
                yield k, adict[k]
        visited |= todo

Here it is in use:

>>> d=dict(a=1,b=2)
>>> for k,v in iterall(d):
...     print k,v
...     d['c'+k[0]] = 'new'
... 
a 1
b 2
cb new
ca new
cc new

Python’s set datatype makes this easy to program and it has reasonable performance.

Obligatory Python whinge: The function implemented above, iterall, is effectively a new method that I’ve implemented for the dict class. But I can’t add a new method to a class that someone else implemented. Unlike, say, Common Lisp, Dylan, Smalltalk, and Objective-C, where I can.

3 Responses to “Python dictionary: iterating and adding”

  1. Nick Barnes Says:

    meh, keep a grey list; pop items from it to visit them, push items onto it as it suits you.

  2. Aaron Says:

    Congrats, nice N^2 algorithm.

    • drj11 Says:

      It is indeed O(n**2); I don’t think congratulations are necessary. Do you think it’s possible to do better without modifying the dict class itself?

      I don’t think it is, and the fact that it’s only possible to do something more efficient by changing the implementation of dict is a great reason for putting an iterator like this into the the builtin class dict in the first place.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: