刪除遞歸

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)]]