Encontrar una clave de forma recursiva en un diccionario
Estoy intentando escribir una función muy simple para buscar recursivamente en un diccionario Python posiblemente anidado (en los casos más extremos, 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 con diccionarios anidados.
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")
Vuelve None.
Sin embargo, funciona para _finditem({"B":1,"A":2},"A")regresar 2.
Estoy seguro de que es un simple error pero no puedo encontrarlo. Siento que es posible que ya haya algo para esto en la biblioteca estándar o collections, pero tampoco puedo encontrarlo.
Si está buscando una explicación general de lo que está mal con un código como este, el canónico es ¿ Por qué mi función recursiva devuelve Ninguno? . Las respuestas aquí son en su mayoría específicas de la tarea de buscar en un diccionario anidado.
cuando recurres, necesitas returnel 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 _finditemregresa Nonesi no encuentra 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 Nonevalores en alguno de sus diccionarios. En ese caso, puede configurar un centinela object()para esta función y devolverlo en caso de que no encuentre nada. Luego puede verificarlo para sentinelsaber si encontró algo o no.
Aquí hay una función que busca en un diccionario que contiene listas y diccionarios anidados. 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.items():
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 "pila" y "pila de iteradores" (créditos a 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
El print(search({"B": {"A": 2}}, "A"))imprimiría 2.
Sólo intento hacerlo más corto:
def get_recursively(search_dict, field):
if isinstance(search_dict, dict):
if field in search_dict:
return search_dict[field]
for key in search_dict:
item = get_recursively(search_dict[key], field)
if item is not None:
return item
elif isinstance(search_dict, list):
for element in search_dict:
item = get_recursively(element, field)
if item is not None:
return item
return None
