Поиск рекурсивно ключа в словаре
Я пытаюсь написать очень простую функцию для рекурсивного поиска через возможно вложенный (в самых крайних случаях, десять уровней) словарь Python и вернуть первое значение, которое он находит из данного ключа.
Я не могу понять, почему мой код не работает для вложенных словарей.
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") Он возвращает None .
Однако он работает для _finditem({"B":1,"A":2},"A") , возвращая 2 .
Я уверен, что это простая ошибка, но я не могу ее найти. Я чувствую, что уже есть что-то для этого в стандартной библиотеке или collections , но я тоже не могу этого найти.
3 Solutions collect form web for “Поиск рекурсивно ключа в словаре”
когда вы рекурсируете, вам нужно return результат _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
Чтобы исправить фактический алгоритм, вам нужно понять, что _finditem возвращает None если он ничего не нашел, поэтому вам нужно явно проверить это, чтобы предотвратить ранний возврат:
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
Конечно, это не удастся, если у вас есть значения None в любом из ваших словарей. В этом случае вы можете настроить object() контролер object() для этой функции и вернуть это в случае, если вы ничего не нашли. Затем вы можете проверить против sentinel знаете ли вы что-то или нет.
Вот функция, которая ищет словарь, который содержит как вложенные словари, так и списки. Он создает список значений результатов.
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
Вот как это сделать, используя шаблон «stack» и «stack of iterators» (кредиты 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
print(search({"B": {"A": 2}}, "A")) будет печатать 2 .