Recursive độ sâu từ điển python

Question

G'day,

Tôi cố gắng để tìm ra độ sâu đệ quy của một hàm mà lưới kéo một cuốn từ điển và tôi là một chút mất ... Hiện nay tôi có một cái gì đó như:

myDict = {'leve1_key1': {'level2_key1': {'level3_key1': {'level4_key_1': {'level5_key1': 'level5_value1'}}}}} 

Và tôi muốn biết chỉ cách lồng điển lồng nhau nhất là ... vì vậy tôi thực hiện như sau ...

def dict_depth(d, depth): 

    for i in d.keys(): 
     if type(d[i]) is dict: 
      newDict = d[i] 
      dict_depth(newDict, depth+1) 
    return depth 

print dict_depth(myDict, 0) 

chỉ có vấn đề là, vòng lặp đệ quy chỉ trả về sự trở lại của giá trị cuối cùng (0). nếu tôi đặt trong một tuyên bố in for i in d.keys(): thì tôi ít nhất có thể in giá trị cao nhất của đệ quy, nhưng trả lại giá trị là một vấn đề khác ...

Tôi chắc chắn điều này là đơn giản - Tôi vừa có jellybrain.

Cheers

Answer 1

Hãy chắc chắn để gán kết quả của các cuộc gọi đệ quy để sâu. Ngoài ra, như @amit cho biết, hãy xem xét sử dụng tối đa để bạn có thể xử lý các dicts với nhiều cặp khóa giá trị (cấu trúc treelike).

def dict_depth(d, depth=0): 
    if not isinstance(d, dict) or not d: 
     return depth 
    return max(dict_depth(v, depth+1) for k, v in d.iteritems()) 

>>> myDict = {'leve1_key1': {'level2_key1': 
       {'level3_key1': {'level4_key_1': 
        {'level5_key1': 'level5_value1'}}}}} 
>>> dict_depth(myDict) 
5 

Answer 2

Bạn nên lưu trữ các giá trị retured từ cuộc gọi đệ quy, và trả về giá trị max tìm thấy, nếu không - bạn đang gọi hàm đệ quy mà không làm bất cứ điều gì với giá trị trả về! [Và trở về 0 như mong đợi, vì nó không bao giờ được thay đổi]

def dict_depth(d, depth): 
    ret = depth 
    for i in d.keys(): 
     if type(d[i]) is dict: 
      newDict = d[i] 
      ret = max(dict_depth(newDict, depth+1),ret) #finding max and storing it 
    return ret #returning the max found 

Answer 3

tôi có thể không thể thực hiện nhịp Raymond hettinger, nếu ông là THE R.H. ;-) Nhưng tôi đến một giải pháp tương tự với một số báo cáo in để minh họa cho những gì đang xảy ra!

d = {1: 2, 2: {3: {5: 6}}, 3: {4: 4}, 7: 8} 
def recursion_depth(dict_, depth): 
    for k in dict_: 
     print "key{0}:value{1} = depth:{2}".format(k, dict_[k], depth) 
    if type(dict_[k]) == dict: 
     actual_depth = recursion_depth(dict_[k], depth+1) 
     if actual_depth > depth: depth += 1 
    return depth 

>>>recursion_depth(d,0) 
key1:value2 = depth:0 
key2:value{3: {5: 6}} = depth:0 
key3:value{5: 6} = depth:1 
key5:value6 = depth:2 
key3:value{4: 4} = depth:1 
key4:value4 = depth:2 
key7:value8 = depth:2 
2 

Answer 4

Một phiên bản không đệ quy:

def depth(d): 

    depth=0 
    q = [(i, depth+1) for i in d.values() if isinstance(i, dict)] 
    max_depth = 0 
    while (q): 
     print 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 5

MyDict = {'a': {'a1': {'a11': 5, 'a12':[{2:'a22'}], 'a13':{'a14':'a11'}}, 'a2': 6}, 'b':{7:{8:{9:{10:{11:'11'}}}}}, 'c': {'c1': 18, 'c2': 1}} 

def find_depth(dep,val): 
    if isinstance(val,dict): 
     dep=dep+1 
     for j in val: 
      find_depth(dep,val[j]) 
     temp_depth.append(dep) 
     dep=0 
     return max(temp_depth) 
    elif isinstance(val,list): 
     for k in val: 
      find_depth(dep,k) 


max_depth={} 
for i in MyDict: 
    dep=0 
    temp_depth=[] 
    max_depth.update({i:(find_depth(dep,MyDict[i]))}) 
    print max_depth 

Đây là mã hoạt động tốt nếu ngay cả danh sách cũng bao gồm.