Comment itérer une dictée de "profondeurs" dynamiques en python?

Question

J'ai une structure de données dict avec différentes "profondeurs". par "profondeurs" je veux dire par exemple: Lorsque la profondeur est 1, dict sera comme:

{'str_key1':int_value1, 'str_key2:int_value2} 

Lorsque la profondeur est 2, dict sera comme:

{'str_key1': 
    {'str_key1_1':int_value1_1, 
    'str_key1_2':int_value1_2}, 
'str_key2': 
    {'str_key2_1':int_value2_1, 
    'str_key2_2':int_value2_2} } 

ainsi de suite et ainsi de suite .

Quand j'ai besoin pour traiter les données, maintenant je fais ceci:

def process(keys,value): 
    #do sth with keys and value 
    pass 

def iterate(depth,dict_data): 
    if depth == 1: 
    for k,v in dict_data: 
     process([k],v) 
    if depth == 2: 
    for k,v in dict_data: 
     for kk,vv, in v: 
     process([k,kk],v) 
    if depth == 3: 
    ......... 

donc j'ai besoin n pour les boucles quand profondeur est n. Comme la profondeur peut aller jusqu'à 10, je me demande s'il existe une façon plus dynamique de faire l'itération sans avoir à écrire toutes les clauses if et for.

Merci.

Answer 1

La réponse évidente est d'utiliser la récursivité. Mais, vous pouvez faire quelque chose de lisse avec Python ici pour aplatir le dictionnaire. Ceci est encore fondamentalement récursif --- nous sommes en train d'implémenter notre propre pile.

def flatten(di): 
    stack = [di] 
    while stack: 
     e = stack[-1] 
     for k, v in e.items(): 
      if isinstance(v, dict): 
       stack.append(v) 
      else: 
       yield k, v 
     stack.remove(e) 

Ensuite, vous pouvez faire quelque chose comme:

for k, v in flatten(mycomplexdict): 
    process(k, v) 

Answer 2

récursivité est votre ami:

def process(keys,value): 
    #do sth with keys and value 
    pass 

def iterate(depth, dict_data): 
    iterate_r(depth, dict_data, []) 

def iterate_r(depth, data, keys): 
    if depth == 0: 
    process(keys, data) 
    else: 
    for k,v in dict_data.items(): 
     iterate_r(depth-1, v, keys+[k]) 

Answer 3

Recusive, juste garder à l'python esprit ne peut recurse 1000 fois:

def process(key, value): 
    print key, value 

def process_dict(dict, callback): 
    for k, v in dict.items(): 
     if hasattr(v, 'items'): 
      process_dict(v, callback) 
     else: 
      callback(k, v) 

d = {'a': 1, 'b':{'b1':1, 'b2':2, 'b3':{'bb1':1}}} 
process_dict(d, process) 

Impressions:

a 1 
b1 1 
b2 2 
bb1 1 

Answer 4

Je ne sais pas pourquoi la pensée de tout le monde en termes de récursion (ou l'élimination de récursivité) - Je venais de faire depth étapes, dont chacune Reconstruit une liste en l'élargissant un niveau plus bas.

Par exemple:

def itr(depth, d): 
    cp = [([], d)] 
    for _ in range(depth): 
    cp = [(lk+[k], v) for lk, d in cp for k, v in d.items()] 
    for lk, ad in cp: 
    process(lk, ad) 

facile à « développer » avec des identificateurs plus longs et plus faible densité de code s'il faut être plus facile à lire à des fins pédagogiques, mais je pense que la logique est assez simple qu'il n'a pas besoin un tel traitement (et, la verbosité en soi a ses inconvénients, aussi ;-).

Par exemple:

d = {'str_key1': 
     {'str_key1_1':'int_value1_1', 
     'str_key1_2':'int_value1_2'}, 
    'str_key2': 
     {'str_key2_1':'int_value2_1', 
     'str_key2_2':'int_value2_2'} } 

def process(lok, v): 
    print lok, v 

itr(2, d) 

impressions

['str_key2', 'str_key2_2'] int_value2_2 
['str_key2', 'str_key2_1'] int_value2_1 
['str_key1', 'str_key1_1'] int_value1_1 
['str_key1', 'str_key1_2'] int_value1_2 

(si un ordre spécifique est souhaité, le tri approprié peut naturellement être effectuée sur cp).

Answer 5

En supposant que vous voulez une profondeur fixe (la plupart des autres réponses semblent supposer que vous voulez récursif à la profondeur maximum), et vous devez préserver le chemin que dans votre question initiale, voici la solution la plus simple:

def process_dict(d, depth, callback, path=()): 
    for k, v in d.iteritems(): 
    if depth == 1: 
     callback(path + (k,), v) 
    else: 
     process_dict(v, depth - 1, callback, path + (k,)) 

Voici un exemple en action:

>>> a_dict = { 
...  'dog': { 
...   'red': 5, 
...   'blue': 6, 
...  }, 
...  'cat': { 
...   'green': 7, 
...  }, 
... } 
>>> def my_callback(k, v): 
... print (k, v) 
... 
>>> process_dict(a_dict, 1, my_callback) 
(('dog',), {'blue': 6, 'red': 5}) 
(('cat',), {'green': 7}) 
>>> process_dict(a_dict, 2, my_callback) 
(('dog', 'blue'), 6) 
(('dog', 'red'), 5) 
(('cat', 'green'), 7)