删除递归

Question

我有一个遍历键的所有组合到一个特定的深度嵌套的字典发电机：

def iter_dict(levels, input_dict, items=[], sort=False, **sort_args): 
    for dict_key, val in (sorted(input_dict.items(), **sort_args) if 
          sort else input_dict.items()): 
     if levels == 1: 
      yield items + [(dict_key, val)] 
     else: 
      yield from iter_dict(levels - 1, val, items + [(dict_key, val)]) 

所以它就像这样：

>>> d = {'a': 1, 'b': 2} 
>>> list(iter_dict(1, d)) 
[[('a', 1)], [('b', 2)]] 

并且

>>> d = {'a': {'c': 1}, 'b': {'d' : 2}} 
>>> list(iter_dict(1, d)) 
[[('a', {'c': 1})], [('b', {'d': 2})]] 
>>> list(iter_dict(2, d)) 
[[('a', {'c': 1}), ('c', 1)], [('b', {'d': 2}), ('d', 2)]] 

生成器的每次迭代都返回一个元组列表，第n个元组为(key, value)在深度为n的嵌套字典中。

但我正在巨大的字典上实现这个功能，并担心达到最大递归深度级别。

如何重写生成器以删除递归？

Answer 1

但是我在执行上巨大的字典此功能，并很担心达到最大递归深度水平

除非你的字典居然有1000+级别的嵌套，这不应该是一个问题。最大递归深度实际上只是大约深度;分支因素不是问题。也就是说，它可以是一个相当大的问题w.r.t.运行时间，但是你不会从中得到最大递归深度误差（并且运行时间不会递归）。

如何重写生成器以删除递归？

我想这可以使用堆栈和存储堆栈序列（当前子字典的所有键）来完成。这样的解决方案可能会更复杂一些，而且不像递归算法那样优雅，所以鉴于上述情况，我认为这不值得。

但不管，在这里你去（稍作简化，不排序）：

from functools import reduce 
def iter_dict(levels, input_dict): 
    def get_nested(keys): 
     return reduce(lambda d, k: d[k], keys, input_dict) 
    stack = [[k] for k in input_dict] 
    while stack: 
     keys = stack.pop() 
     if len(keys) == levels: 
      yield [(k, get_nested(keys[:i])) for i, k in enumerate(keys, 1)] 
     else: 
      stack.extend(keys + [k] for k in get_nested(keys)) 

例子：

>>> d = {'a': {'c': 1, "e": 2}, 'b': {'d' : 3, "f": 4}} 
>>> list(iter_dict(2, d)) 
[[('a', {'c': 1, 'e': 2}), ('e', 2)], 
[('a', {'c': 1, 'e': 2}), ('c', 1)], 
[('b', {'d': 3, 'f': 4}), ('f', 4)], 
[('b', {'d': 3, 'f': 4}), ('d', 3)]]