知道字典的深度

知道字典的深度

您将不得不遍历字典。您可以排队。以下内容应免受循环引用的影响：

from collections import dequedef 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@singledispatchdef depth(_, _level=1, _memo=None):    return _leveldef _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 wrapperdef _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.registerdef _dict_depth(d: dict, _level=1, **kw):    return max(depth(v, _level=_level + 1, **kw) for v in d.values())

这是深度优先搜索，因此现在

max()

需要在每个级别上仔细检查 当前 对象的最大深度。具有3个不同深度的键的字典应反映该级别的最大深度。

memo

任一版本中使用的集合都会跟踪对象ID，因此，如果您执行了类似的 *** 作，则我们不会运行圆圈

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.registerdef _list_depth(l: list, _level=1, **kw):    return max(depth(v, _level=_level + 1, **kw) for v in l)

因为我已经增强了标准

.register

装饰器来处理循环引用测试，所以实现额外的容器支持相对来说是微不足道的。只要记住将任何其他关键字参数传递给递归调用即可！