Python3.x 来自嵌套字典的完整地址

发布于12月05日

我们有这样的数据

input = {
    'a': 3,
    'b': {'g': {'l': 12}},
    'c': {
        'q': 3,
        'w': {'v': 3},
        'r': 8,
        'g': 4
    },
    'd': 4
}

事先不知道将有多少个嵌套级别我们需要获取最终值的完整地址，所有点都用点或另一个特殊字符分隔就像这样:

a:3
b.g.l: 12
c.q: 3
c.w.v: 3
etc

我试着用递归函数来解决这个问题.

def recursive_parse(data: dict, cache: Optional[list]=None):
    if cache is None:
        cache = []
    for k in data:
        cache.append(k)
        if not isinstance(data[k], dict):
            print(f"{'.'.join(cache) } :{data[k]}")
            cache.clear()
        else:
            recursive_parse(data[k], cache)

但我在"记住"嵌套词典的前一个关键字时遇到了问题.

a :3
b.g.l :12
c.q :3
w.v :3
r :8
g :4
d :4

解决此问题的正确算法是什么？

推荐答案

对于这一点，使用显式堆栈可能比使用Python调用堆栈更好.由于较高的函数调用开销，在Python中递归速度很慢，并且递归限制相当保守.

def dotted(data):
    result = {}
    stack = list(data.items())
    while stack:
        k0, v0 = stack.pop()
        if isinstance(v0, dict):
            for k1, v1 in v0.items():
                item = ".".join([k0, k1]), v1
                stack.append(item)
        else:
            result[k0] = v0
    return result

演示:

>>> data
{'a': 3,
 'b': {'g': {'l': 12}},
 'c': {'q': 3, 'w': {'v': 3}, 'r': 8, 'g': 4},
 'd': 4}
>>> for k, v in reversed(dotted(data).items()):
...     print(k, v)
... 
a 3
b.g.l 12
c.q 3
c.w.v 3
c.r 8
c.g 4
d 4