Finding a key recursively in a dictionary
Solution 1
when you recurse, you need to return
the result of _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
To fix the actual algorithm, you need to realize that _finditem
returns None
if it didn't find anything, so you need to check that explicitly to prevent an early return:
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
Of course, that will fail if you have None
values in any of your dictionaries. In that case, you could set up a sentinel object()
for this function and return that in the case that you don't find anything -- Then you can check against the sentinel
to know if you found something or not.
Solution 2
Here's a function that searches a dictionary that contains both nested dictionaries and lists. It creates a list of the values of the results.
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
Solution 3
Here is a way to do this using a "stack" and the "stack of iterators" pattern (credits to 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
The print(search({"B": {"A": 2}}, "A"))
would print 2
.
Solution 4
Just trying to make it shorter:
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
Fredrick Brennan
Updated on July 09, 2022Comments
-
Fredrick Brennan almost 2 years
I'm trying to write a very simple function to recursively search through a possibly nested (in the most extreme cases ten levels deep) Python dictionary and return the first value it finds from the given key.
I cannot understand why my code doesn't work for nested dictionaries.
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")
It returns
None
.It does work, however, for
_finditem({"B":1,"A":2},"A")
, returning2
.I'm sure it's a simple mistake but I cannot find it. I feel like there already might be something for this in the standard library or
collections
, but I can't find that either. -
Daniel Roseman about 11 yearsThis seems to be the most common mistake when writing recursive functions.
-
mgilson about 11 years@DanielRoseman -- shrugs -- I've made this mistake myself a few times. But it is a hint when your function returns
None
and you have no idea why ;-) -
Fredrick Brennan about 11 yearsThank you, that should have been obvious. I was looking at this for a good hour!
-
mgilson about 11 years@frb -- No problem. Stuff like this happens to everyone.
-
Fredrick Brennan about 11 years@mgilson Actually, I just realized that this doesn't work when the needed key is second in the dictionary. Any clues about that? It's because it's returning after the first key, value in obj.items().
-
Freddie about 5 yearsreplace iteritems() with items() to get this working in python3: docs.buildbot.net/0.9.4/developer/py3-compat.html
-
cabbi almost 5 yearswith isinstance(value, (list, tuple)) it will search in nested tuples as well