来自嵌套字典的完整地址

Question

我们有这样的数据

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

解决这个问题的正确算法是什么?

Answer 1

最好使用显式堆栈，而不是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

Answer 2

尝试:

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

def parse(d, path=None):
if path is None:
path = []
if isinstance(d, dict):
for k, v in d.items():
yield from parse(v, path + [k])
else:
yield "{}: {}".format(".".join(path), d)

for p in parse(dct):
print(p)

打印:

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