Поиск рекурсивно ключа в словаре

Я пытаюсь написать очень простую функцию для рекурсивного поиска через возможно вложенный (в самых крайних случаях, десять уровней) словарь 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 может быть что-то для этого, но я тоже не могу этого найти.

Ответ 1

когда вы рекурсируете, вам нужно 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() для этой функции и вернуть это в случае, если вы ничего не нашли. Затем вы можете проверить флажок sentinel, чтобы узнать, нашли ли вы что-то или нет.

Ответ 2

Здесь функция, которая ищет словарь, содержащий как вложенные словари, так и списки. Он создает список значений результатов.

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

Ответ 3

Вот как это сделать, используя шаблон "stack" и "stack of iterators" (кредиты Гарет Рис):

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.

Ответ 4

Я не мог добавить комментарий к принятому решению, предложенному @mgilston из-за отсутствия репутации. Решение не работает, если искомый ключ находится внутри списка.

Циклический просмотр элементов списков и вызов рекурсивной функции должны расширить функциональность для поиска элементов во вложенных списках:

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
        elif isinstance(v,list):
            for list_item in v:
                item = _finditem(list_item, key)
                if item is not None:
                    return item

print(_finditem({"C": {"B": [{"A":2}]}}, "A"))

Ответ 5

да, скажите, пожалуйста, любой ответ для этого набора вложенных списков !!!. Я не мог найти никакого ответа !!...

{"C": {"B": [{"A": 2}]}}