Supposing we have this dict:
d = {'a':1, 'b': {'c':{}}}
What would be the most straightforward way of knowing the nesting depth of it?
With recursion We can design a function that will recursively call itself to check the values of the dictionary. As long as the inner element is evaluated to be a dictionary, the function will call itself and we will get the result for the depth of the dictionary.
A dictionary can contain any object type except another dictionary. Items are accessed by their position in a dictionary. Items are accessed by their position in a dictionary. Dictionaries can be nested to any depth.
A dictionary can contain another dictionary. A dictionary can also contain a list, and vice versa.
You need to create a recursive function:
>>> 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
You'll have to traverse the dictionary. You could do so with a queue; the following should be safe from circular references:
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
Note that because we visit all dictionary values in breath-first order, the level
value only ever goes up. The memo
set is used to ensure we don't try to traverse a circular reference, endlessly.
Or you could traverse the tree with recursion (which effectively uses function calls as a stack). I've used functools.singledispatch()
for easy expansion to other container types:
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())
This is as depth-first search, so now max()
is needed to pick the greatest depth for the current object under scrutiny at each level. A dictionary with 3 keys of each different depths should reflect the greatest depth at that level.
The memo
set used in either version tracks object ids, so we don't run is circles if you did something like foo = {}; foo["bar"] = foo
.
Demo:
>>> 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
The recursive singledispatch
version can be expanded to cover more containers, such as lists:
@depth.register def _list_depth(l: list, _level=1, **kw): return max(depth(v, _level=_level + 1, **kw) for v in l)
Because I've augmented the standard .register
decorator to handle circular-reference testing, implementing additional container support is relatively trivial. Just remember to pass along any extra keyword arguments to the recursive call!
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With