知道字典的深度

Question

假设我们有这个词:

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

了解它的嵌套深度最简单的方法是什么？

Answer 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需要在每个级别的详细审查下为当前字典选择最大深度,每个不同深度的3个键的字典应该反映该级别的最大深度.

演示:

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 is not None else _orig(_protect(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())

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