logo标签列表

如何在不使用递归的情况下展开嵌套字典？

pythonpython-3.x
5

我发现了一个可以将字典扁平化的函数:

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

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

我认为你应该看一下这个答案，可能是一个不错的选择。 - Arthur Julião
5个回答
6

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

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

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]。这很像在图上进行深度优先搜索和广度优先搜索。
但是，由于字典是无序的，这不应该是一个大问题（除非你正在使用collections.OrderedDict），这就是为什么我说这是一个潜在的缺点。
6

不要将字典保存在堆栈中，而应该将项目的迭代器保存在堆栈中。

这样，您可以随时恢复迭代器。

另外，因为您按顺序暂停和恢复迭代器的执行，所以结果将始终按照字典的顺序。

顺便说一下，@iBug，从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]
非常完美的答案，谢谢。如果您不介意，我还有另一个函数需要您的帮助，该函数名为 del_key(dictionary, key)，其主体是 return {k: del_key(v, key) for k, v in dictionary.items() if k != key}，它接受一个字典和需要从嵌套字典中删除的键，再次感谢。 - user9721253
0

“Flattening” 可以有不同的解释；如果您想将一个字典压缩成具有点分隔键的字典，这种方法可能有效：

def flatten(it=None, sep="."):

    ot = {}

    if isinstance(it, dict):
        stack = list(it.items())[::-1]
    elif isinstance(it, list):
        stack = list(enumerate(it))[::-1]

    while stack:

        head = stack.pop()

        if isinstance(head[1], dict):
            stack = stack + [(f'{head[0]}{sep}{item[0]}', item[1]) for item in head[1].items()][::-1]
        elif isinstance(head[1], list):
            stack = stack + [(f'{head[0]}{sep}{item[0]}', item[1]) for item in enumerate(head[1])][::-1]
        else:
            ot[head[0]] = head[1]

    return ot

给定输入：{'b': 2, 'a': 1, 'c': {'a': 1, 'b': [1, 2, 3]}, 'd': [1, 2, {'b': 1, 'a': 2}]}

输出结果为：

{'b': 2,
 'a': 1,
 'c.a': 1,
 'c.b.0': 1,
 'c.b.1': 2,
 'c.b.2': 3,
 'd.0': 1,
 'd.1': 2,
 'd.2.b': 1,
 'd.2.a': 2}
0
-1

如果你想不使用递归来完成它，那是不可能的。

所以这里提供了递归错误的解决方案。

根据Python文档，你可以使用sys.getrecursionlimit()来查看递归限制。你也可以使用sys.setrecursionlimit()来增加递归限制。

1
第一段看起来和我的答案相反。你确定吗？ - iBug
1
此外，不建议将 sys.setrecursionlimit 设置为任意高的值，因为它严重依赖于系统资源。 - iBug
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接