Знать глубину словаря

Question

Предположим, у нас есть этот дикт:

d = {'a':1, 'b': {'c':{}}}

Какой самый простой способ узнать глубину его вложения?

Answer 1

Вам придется возвращаться:

def depth(d, level=1):
    if not isinstance(d, dict) or not d:
        return level
    return max(depth(d[k], level + 1) for k in d)

max() необходимо выбрать наибольшую глубину для текущего словаря, находящегося под пристальным вниманием на каждом уровне, словарь с 3 ключами каждой различной глубины должен отражать наибольшую глубину на этом уровне.

Демо-версия:

>>> d = {'a':1, 'b': {'c':{}}}
>>> depth(d)
3
>>> d = {'foo': {'bar': {'baz': 0}, 'spam': {'ham': {'monty': 1}, 'eric': 'idle'}}, 'john': 'cleese'}
>>> depth(d)
5

Answer 2

Вам нужно создать рекурсивную функцию:

>>> def depth(d):
...     if isinstance(d, dict):
...         return 1 + (max(map(depth, d.values())) if d else 0)
...     return 0
...
>>> d = {'a':1, 'b': {'c':{}}}
>>> depth(d)
3

Answer 3

Нерекурсивное решение:

def depth(d):

    depth=0
    q = [(i, depth+1) for i in d.values() if isinstance(i, dict)]
    max_depth = 0
    while (q):
        n, depth = q.pop()
        max_depth = max(max_depth, depth)
        q = q + [(i, depth+1) for i in n.values() if isinstance(i, dict)]

    print max_depth

Answer 4

Итеративное решение:

from collections import deque


def depth(d):
    q = deque([d])
    q2 = deque()
    max_depth = 0
    while q:
        curr_dict = q.popleft()
        if isinstance(curr_dict, dict):
            for di in curr_dict.itervalues():
                q2.append(di)
        if not q:
            q, q2 = q2, q
            max_depth += 1
    return max_depth

print depth(None)
print depth({})
print depth({"a": "b"})
print depth({"a": "b", "c": {"d": "e"}, "f": {"g": "h"}, "i": {"j": "k"}, "x": {}, "z": {} })
print depth({'a':1, 'b': {'c':{}}})
print depth({'foo': {'bar': {'baz': 0}, 'spam': {'ham': {'monty': 1}, 'eric': 'idle'}}, 'john': 'cleese'})