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

Ответ 1

Вам придется пройти через словарь. Вы можете сделать это с помощью очереди; следующее должно быть защищено от циклических ссылок:

from collections import deque

def depth(d):
    queue = deque([(id(d), d, 1)])
    memo = set()
    while queue:
        id_, o, level = queue.popleft()
        if id_ in memo:
            continue
        memo.add(id_)
        if isinstance(o, dict):
            queue += ((id(v), v, level + 1) for v in o.values())
    return level

Обратите внимание, что, поскольку мы обращаемся ко всем значениям словаря в порядке дыхания, значение level только увеличивается. Набор memo используется для того, чтобы мы не пытались бесконечно обходить круговую ссылку.

Или вы можете пройти по дереву с помощью рекурсии (которая эффективно использует вызовы функций в качестве стека). Я использовал functools.singledispatch() для простого расширения на другие типы контейнеров:

from functools import singledispatch, wraps

@singledispatch
def depth(_, _level=1, _memo=None):
    return _level

def _protect(f):
    """Protect against circular references"""
    @wraps(f)
    def wrapper(o, _level=1, _memo=None, **kwargs):
        _memo, id_ = _memo or set(), id(o)
        if id_ in _memo: return _level
        _memo.add(id_)
        return f(o, _level=_level, _memo=_memo, **kwargs)
    return wrapper

def _protected_register(cls, func=None, _orig=depth.register):
    """Include the _protect decorator when registering"""
    if func is None and isinstance(cls, type):
        return lambda f: _orig(cls, _protect(f))
    return _orig(cls, _protect(func)) if func else _protect(_orig(cls))
depth.register = _protected_register

@depth.register
def _dict_depth(d: dict, _level=1, **kw):
    return max(depth(v, _level=_level + 1, **kw) for v in d.values())

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

Набор memo используемый в любой из версий, отслеживает идентификаторы объектов, поэтому мы не запускаем круги, если вы сделали что-то вроде foo = {}; foo["bar"] = foo foo = {}; foo["bar"] = foo.

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

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

Рекурсивная версия singledispatch может быть расширена, чтобы охватить больше контейнеров, таких как списки:

@depth.register
def _list_depth(l: list, _level=1, **kw):
    return max(depth(v, _level=_level + 1, **kw) for v in l)

Поскольку я дополнил стандартный декоратор .register для обработки циклических ссылок, реализовать дополнительную поддержку контейнеров относительно тривиально. Просто не забудьте передать дополнительные аргументы ключевого слова в рекурсивный вызов!

Ответ 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

Ответ 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

Ответ 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'})