如何在没有递归的情况下展平嵌套字典？

Question

我遇到了这个可以压缩字典的功能:

def flatten(dictionnary, container=None):
    if container is None:
        container = []
    for k, v in dictionnary.items():
        container.append(k)
        if v:
            flatten(v, container)
    return container

为了测试它,我创建了一个嵌套n时间的字典,如下所示:

nesteddict = {}
for i in range(n, 0, -1):
    emptydict = {}
    emptydict[i] = nesteddict
    nesteddict = emptydict

该函数n小于999时工作,否则命中递归限制:

RecursionError: maximum recursion depth exceeded while calling a Python object

所以经过一点点搜索之后,似乎任何递归函数都可以重写为迭代,但是我无法看到如何为我必须产生相同结果的函数完成它.

我在玩这个游戏时遇到的另一个奇怪的问题是,如果我尝试下面的代码n >= 998:

nesteddict = {}
for i in range(n, 0, -1):
    emptydict = {}
    emptydict[i] = nesteddict
    nesteddict = emptydict
print(nesteddict)

我收到递归错误:

RecursionError: maximum recursion depth exceeded while getting the repr of an object

这很奇怪,因为我在这里看不到任何递归.

Answer 1

您应该将项目的迭代器保存在堆栈中,而不是将dict保存在堆栈中.

这样,您可以在命令中恢复迭代器.

另外,因为您按顺序暂停和恢复迭代器的执行,结果将始终根据dict的顺序.

顺便说一下,@ iBug,dicts是按照3.7的Python规范排序的

def flatten(dictionary, container=None):
    if container is None:
        container = []
    iterators = []
    iterator = iter(dictionary.items())
    while True:
        for k, v in iterator:
            container.append(k)
            if v:
                # Save the current iterator for later
                iterators.append(iterator)
                # Run on the new dict
                iterator = iter(v.items())
                break

        # Current iterator is done, fetch the next one
        else:
            try:
                iterator = iterators.pop()
            except IndexError:
                return container

print(flatten({1: None, 2: {3: None, 4: None}, 5: None}))
[1, 2, 3, 4, 5]

Answer 2

从逻辑上讲，嵌套字典（和列表）是一种递归，因此如果您想避免逻辑递归，那是不可能的。

但是，由于递归只是递归，您可以保留自己的堆栈并在循环中模拟它：

def flatten(dct, c=None):
    if c is None:
        c = []
    stack = [dct]
    while stack:  # non-empty
        d = stack.pop()
        for k, v in d.items():
            c.append(k)
            if v:
                stack.append(v)
    return c

这个函数很好地模拟了函数递归的行为，带有自定义堆栈。

有一个潜在的缺点：理论上，像这样的字典

{1: None, 2: {3: None, 4: None}, 5: None}

应该变平为[1, 2, 3, 4, 5]，而这种方法会给[1, 2, 5, 3, 4]. 这很像图上的 DFS 搜索与 BFS 搜索。

但是，由于字典是无序的，这应该不是什么大问题（除非您正在使用collections.OrderedDict），这就是为什么我说这是一个潜在的缺点。