How to iterate a dict of dynamic "depths" in python?

Question

I have a dict data structure with various "depths". By "depths" I mean for example: When depth is 1, dict will be like:

{'str_key1':int_value1, 'str_key2:int_value2}

When depth is 2, dict will be like:

{'str_key1':
    {'str_key1_1':int_value1_1,
     'str_key1_2':int_value1_2},
 'str_key2':
    {'str_key2_1':int_value2_1, 
     'str_key2_2':int_value2_2} }

so on and so forth.

When I need to process the data, now I'm doing this:

def process(keys,value):
  #do sth with keys and value
  pass

def iterate(depth,dict_data):
  if depth == 1:
    for k,v in dict_data:
      process([k],v)
  if depth == 2:
    for k,v in dict_data:
      for kk,vv, in v:
        process([k,kk],v)
  if depth == 3:
    .........

So I need n for loops when depth is n. As depth can go up to 10, I'm wondering if there is a more dynamic way to do the iteration without having to write out all the if and for clauses.

Thanks.

Answer 1

The obvious answer is to use recursion. But, you can do something slick with Python here to flatten the dictionary. This is still fundamentally recursive --- we are just implementing our own stack.

def flatten(di):
     stack = [di]
     while stack:
         e = stack[-1]
         for k, v in e.items():
             if isinstance(v, dict):
                 stack.append(v)
             else:
                 yield k, v
         stack.remove(e)

Then, you can do something like:

for k, v in flatten(mycomplexdict):
     process(k, v)

Answer 2

Recursion is your friend:

def process(keys,value):
  #do sth with keys and value
  pass

def iterate(depth, dict_data):
  iterate_r(depth, dict_data, [])

def iterate_r(depth, data, keys):
  if depth == 0:
    process(keys, data)
  else:
    for k,v in dict_data.items():
      iterate_r(depth-1, v, keys+[k])

Answer 3

Recusive, just keep in mind python can only recurse 1000 times:

def process(key, value):
    print key, value

def process_dict(dict, callback):
    for k, v in dict.items():
        if hasattr(v, 'items'):
            process_dict(v, callback)
        else:
            callback(k, v)

d = {'a': 1, 'b':{'b1':1, 'b2':2, 'b3':{'bb1':1}}}
process_dict(d, process)

Prints:

a 1
b1 1
b2 2
bb1 1

Answer 4

I'm not sure why everybody's thinking in terms of recursion (or recursion elimination) -- I'd just do depth steps, each of which rebuilds a list by expanding it one further level down.

E.g.:

def itr(depth, d):
  cp = [([], d)]
  for _ in range(depth):
    cp = [(lk+[k], v) for lk, d in cp for k, v in d.items()]
  for lk, ad in cp:
    process(lk, ad)

easy to "expand" with longer identifiers and lower code density if it need to be made more readable for instructional purposes, but I think the logic is simple enough that it may not need such treatment (and, verbosity for its own sake has its drawbacks, too;-).

For example:

d = {'str_key1':
      {'str_key1_1':'int_value1_1',
       'str_key1_2':'int_value1_2'},
     'str_key2':
      {'str_key2_1':'int_value2_1', 
       'str_key2_2':'int_value2_2'} }

def process(lok, v):
  print lok, v

itr(2, d)

prints

['str_key2', 'str_key2_2'] int_value2_2
['str_key2', 'str_key2_1'] int_value2_1
['str_key1', 'str_key1_1'] int_value1_1
['str_key1', 'str_key1_2'] int_value1_2

(if some specific order is desired, appropriate sorting can of course be performed on cp).

Answer 5

Assuming you want a fixed depth (most other answers seem to assume you want to recurse to max depth), and you need to preserve the path as in your original question, here's the most straightforward solution:

def process_dict(d, depth, callback, path=()):
  for k, v in d.iteritems():
    if depth == 1:
      callback(path + (k,), v)
    else:
      process_dict(v, depth - 1, callback, path + (k,))

Here's an example of it in action:

>>> a_dict = {
...     'dog': {
...         'red': 5,
...         'blue': 6,
...     },
...     'cat': {
...         'green': 7,
...     },
... }
>>> def my_callback(k, v):
...   print (k, v)
...
>>> process_dict(a_dict, 1, my_callback)
(('dog',), {'blue': 6, 'red': 5})
(('cat',), {'green': 7})
>>> process_dict(a_dict, 2, my_callback)
(('dog', 'blue'), 6)
(('dog', 'red'), 5)
(('cat', 'green'), 7)