Encontrar una clave recursivamente en un diccionario.

Estoy tratando de escribir una función muy simple para buscar recursivamente a través de un diccionario de Python posiblemente nested (en los casos más extremos, con diez niveles de profundidad) y devolver el primer valor que encuentre en la clave dada.

No puedo entender por qué mi código no funciona para los diccionarios nesteds.

def _finditem(obj, key): if key in obj: return obj[key] for k, v in obj.items(): if isinstance(v,dict): _finditem(v, key) print _finditem({"B":{"A":2}},"A") 

Devuelve None .

Sin embargo, funciona para _finditem({"B":1,"A":2},"A") , devolviendo 2 .

Estoy seguro de que es un simple error, pero no puedo encontrarlo. Siento que ya podría haber algo para esto en la biblioteca estándar o en las collections , pero tampoco lo encuentro.

cuando se recupera, debe return el resultado de _finditem

 def _finditem(obj, key): if key in obj: return obj[key] for k, v in obj.items(): if isinstance(v,dict): return _finditem(v, key) #added return statement 

Para corregir el algoritmo real, debe darse cuenta de que _finditem devuelve None si no encontró nada, por lo que debe verificarlo explícitamente para evitar una devolución anticipada:

 def _finditem(obj, key): if key in obj: return obj[key] for k, v in obj.items(): if isinstance(v,dict): item = _finditem(v, key) if item is not None: return item 

Por supuesto, eso fallará si tiene valores de None en cualquiera de sus diccionarios. En ese caso, puede configurar un object() centinela object() para esta función y devolverlo en el caso de que no encuentre nada. Luego, puede verificar con el sentinel para saber si encontró algo o no.

Aquí hay una función que busca un diccionario que contiene tanto diccionarios nesteds como listas. Crea una lista de los valores de los resultados.

 def get_recursively(search_dict, field): """ Takes a dict with nested lists and dicts, and searches all dicts for a key of the field provided. """ fields_found = [] for key, value in search_dict.iteritems(): if key == field: fields_found.append(value) elif isinstance(value, dict): results = get_recursively(value, field) for result in results: fields_found.append(result) elif isinstance(value, list): for item in value: if isinstance(item, dict): more_results = get_recursively(item, field) for another_result in more_results: fields_found.append(another_result) return fields_found 

Aquí hay una manera de hacer esto usando un patrón de “stack” y “stack de iteradores” (créditos para Gareth Rees):

 def search(d, key, default=None): """Return a value corresponding to the specified key in the (possibly nested) dictionary d. If there is no item with that key, return default. """ stack = [iter(d.items())] while stack: for k, v in stack[-1]: if isinstance(v, dict): stack.append(iter(v.items())) break elif k == key: return v else: stack.pop() return default 

La print(search({"B": {"A": 2}}, "A")) se imprimiría 2 .