Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Know the depth of a dictionary

Supposing we have this dict:

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

What would be the most straightforward way of knowing the nesting depth of it?

like image 338
tutuca Avatar asked May 06 '14 15:05

tutuca


People also ask

How do you find the depth of a dictionary?

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.

Can dictionary be nested to any depth?

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.

Can a dictionary contain a list?

A dictionary can contain another dictionary. A dictionary can also contain a list, and vice versa.


2 Answers

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 
like image 144
falsetru Avatar answered Sep 28 '22 03:09

falsetru


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!

like image 20
Martijn Pieters Avatar answered Sep 28 '22 03:09

Martijn Pieters