2012-03-02 32 views
6

G'day,ricorsiva profondità di dizionario Python

Sto cercando di trovare la profondità ricorsiva di una funzione che strascico un dizionario e io sono un po 'perso ... Attualmente ho qualcosa di simile:

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

E voglio sapere quanto annidato il dizionario più nidificato è ... così ho effettuare le seguenti ...

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) 

l'unico problema è, il ciclo ricorsivo restituisce solo il ritorno del valore finale (0). se ho messo in un comunicato stampa for i in d.keys(): quindi posso almeno stampare il valore più alto della ricorsione, ma restituendo il valore è una questione diversa ...

Sono sicuro che questo è semplice - ho appena ricevuto jellybrain.

Acclamazioni

+0

Qui non troverete alcun limite (eccetto per la memoria disponibile). Ogni dizionario annidato è un nuovo oggetto che non conosce nulla del suo genitore. – usr

+0

Ma il tuo codice potrebbe imbattersi in un overflow dello stack. Questo non ha nulla a che fare con i limiti del dizionario. – usr

risposta

10

Assicurarsi di assegnare il risultato della chiamata ricorsiva a profondità. Inoltre, come dice @amit, prendi in considerazione l'utilizzo di max in modo da poter gestire dict con più coppie di valori chiave (una struttura simile a un albero).

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 
+1

si noti che senza usare 'max()' in profondità, si potrebbe sovrascrivere 'profondità' con un valore minore, se il dizionario ha più di 1 tasto. – amit

+0

@amit Sono d'accordo. È sempre pericoloso iniziare con il codice OP :-) –

1

è necessario memorizzare il valore retured dalla chiamata ricorsiva, e restituire il valore massimo scoperto, altrimenti - si sta chiamando la funzione ricorsiva senza fare nulla con il valore restituito! [E tornando 0 come previsto, dal momento che non è mai stata cambiata]

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 
+0

@RaymondHettinger: funziona perfettamente per me e stampa '4'. Presumo che l'OP volesse che il dizionario esterno fosse "0". – amit

0

non posso possibile battere Raymond Hettinger, se è IL R.H. ;-) Ma sono arrivato a una soluzione simile con alcune dichiarazioni di stampa per illustrare quello che sta succedendo!

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 
0

Una versione non ricorsiva:

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 
2
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 

Ecco codice funziona bene se anche la lista comprendeva anche.

Problemi correlati