在字典中递归地查找密钥

Question

我正在尝试编写一个非常简单的函数来递归搜索可能嵌套的(在最极端情况下十层深度)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,但我也找不到.

Answer 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是否找到了某些内容.

Answer 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

Answer 3

这是一种使用“堆栈”和“迭代器堆栈”模式（归功于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。