知道字典

Question

假定的深度，我們有這個字典：

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

什麼是知道的嵌套深度它的最簡單的方法是什麼？

Answer 1

你將不得不改乘：

def depth(d, level=1): 
    if not isinstance(d, dict) or not d: 
     return level 
    return max(depth(d[k], level + 1) for k in d) 

max()是需要挑選備受矚目，在每個級別的當前字典中的最大深度，每個不同深度的3個鍵的字典應該反映在那個級別最大的深度。

演示：

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

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 

Answer 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'})