如何在Python中迭代动态“深度”的字典？

Question

我有一个字典这种数据结构，它的“深度”各不相同。

这里的“深度”是什么意思呢？举个例子：

当深度为1时，字典的样子是：

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

当深度为2时，字典的样子是：

{'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(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:
    .........

所以，当深度是时，我需要写个循环。因为深度最多可以到10，我在想有没有更灵活的方法来进行循环，而不需要写那么多的if和for语句。

谢谢。

Answer 1

递归，简单来说就是一个函数自己调用自己。不过要记住，Python最多只能递归1000次，也就是说如果你调用的次数超过1000次，程序就会出错。

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)

输出结果是：

a 1
b1 1
b2 2
bb1 1

Answer 2

显而易见的答案是使用递归。不过，在这里你可以用Python做一些巧妙的事情来扁平化字典。其实这还是本质上在用递归——我们只是在实现自己的栈。

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)

接着，你可以这样做：

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

Answer 3

我不太明白大家为什么都在考虑递归（或者递归的替代方法）——我会直接做depth步，每一步都通过向下扩展一层来重建一个列表。

比如：

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)

如果需要为了教学目的让代码更易读，可以用更长的标识符和更低的代码密度来“扩展”，但我觉得逻辑已经简单到不需要这样处理（而且，单纯为了冗长而冗长也有它的缺点;-）。

举个例子：

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)

输出

['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

（如果需要特定的顺序，当然可以对cp进行适当的排序）。