Find all occurrences of a key in nested dictionaries and lists

Question

I have a dictionary like this:

{
    "id": "abcde",
    "key1": "blah",
    "key2": "blah blah",
    "nestedlist": [
        {
            "id": "qwerty",
            "nestednestedlist": [
                {
                    "id": "xyz",
                    "keyA": "blah blah blah"
                },
                {
                    "id": "fghi",
                    "keyZ": "blah blah blah"
                }
            ],
            "anothernestednestedlist": [
                {
                    "id": "asdf",
                    "keyQ": "blah blah"
                },
                {
                    "id": "yuiop",
                    "keyW": "blah"
                }
            ]
        }
    ]
}

Basically a dictionary with nested lists, dictionaries, and strings, of arbitrary depth.

What is the best way of traversing this to extract the values of every "id" key? I want to achieve the equivalent of an XPath query like "//id". The value of "id" is always a string.

So from my example, the output I need is basically:

["abcde", "qwerty", "xyz", "fghi", "asdf", "yuiop"]

Order is not important.

Answer 1

I found this Q/A very interesting, since it provides several different solutions for the same problem. I took all these functions and tested them with a complex dictionary object. I had to take two functions out of the test, because they had to many fail results and they did not support returning lists or dicts as values, which i find essential, since a function should be prepared for almost any data to come.

So i pumped the other functions in 100.000 iterations through the timeit module and output came to following result:

0.11 usec/pass on gen_dict_extract(k,o)
- - - - - - - - - - - - - - - - - - - - - - - - - - - - -
6.03 usec/pass on find_all_items(k,o)
- - - - - - - - - - - - - - - - - - - - - - - - - - - - -
0.15 usec/pass on findkeys(k,o)
- - - - - - - - - - - - - - - - - - - - - - - - - - - - -
1.79 usec/pass on get_recursively(k,o)
- - - - - - - - - - - - - - - - - - - - - - - - - - - - -
0.14 usec/pass on find(k,o)
- - - - - - - - - - - - - - - - - - - - - - - - - - - - -
0.36 usec/pass on dict_extract(k,o)
- - - - - - - - - - - - - - - - - - - - - - - - - - - - -

All functions had the same needle to search for ('logging') and the same dictionary object, which is constructed like this:

o = { 'temparature': '50', 
      'logging': {
        'handlers': {
          'console': {
            'formatter': 'simple', 
            'class': 'logging.StreamHandler', 
            'stream': 'ext://sys.stdout', 
            'level': 'DEBUG'
          }
        },
        'loggers': {
          'simpleExample': {
            'handlers': ['console'], 
            'propagate': 'no', 
            'level': 'INFO'
          },
         'root': {
           'handlers': ['console'], 
           'level': 'DEBUG'
         }
       }, 
       'version': '1', 
       'formatters': {
         'simple': {
           'datefmt': "'%Y-%m-%d %H:%M:%S'", 
           'format': '%(asctime)s - %(name)s - %(levelname)s - %(message)s'
         }
       }
     }, 
     'treatment': {'second': 5, 'last': 4, 'first': 4},   
     'treatment_plan': [[4, 5, 4], [4, 5, 4], [5, 5, 5]]
}

All functions delivered the same result, but the time differences are dramatic! The function gen_dict_extract(k,o) is my function adapted from the functions here, actually it is pretty much like the find function from Alfe, with the main difference, that i am checking if the given object has iteritems function, in case strings are passed during recursion:

# python 2
def gen_dict_extract(key, var):
    if hasattr(var,'iteritems'): # hasattr(var,'items') for python 3
        for k, v in var.iteritems(): # var.items() for python 3
            if k == key:
                yield v
            if isinstance(v, dict):
                for result in gen_dict_extract(key, v):
                    yield result
            elif isinstance(v, list):
                for d in v:
                    for result in gen_dict_extract(key, d):
                        yield result

So this variant is the fastest and safest of the functions here. And find_all_items is incredibly slow and far off the second slowest get_recursivley while the rest, except dict_extract, is close to each other. The functions fun and keyHole only work if you are looking for strings.

Interesting learning aspect here :)

Answer 2

d = { "id" : "abcde",
    "key1" : "blah",
    "key2" : "blah blah",
    "nestedlist" : [ 
    { "id" : "qwerty",
        "nestednestedlist" : [ 
        { "id" : "xyz", "keyA" : "blah blah blah" },
        { "id" : "fghi", "keyZ" : "blah blah blah" }],
        "anothernestednestedlist" : [ 
        { "id" : "asdf", "keyQ" : "blah blah" },
        { "id" : "yuiop", "keyW" : "blah" }] } ] } 


def fun(d):
    if 'id' in d:
        yield d['id']
    for k in d:
        if isinstance(d[k], list):
            for i in d[k]:
                for j in fun(i):
                    yield j

---

>>> list(fun(d))
['abcde', 'qwerty', 'xyz', 'fghi', 'asdf', 'yuiop']

Answer 3

d = { "id" : "abcde",
    "key1" : "blah",
    "key2" : "blah blah",
    "nestedlist" : [
    { "id" : "qwerty",
        "nestednestedlist" : [
        { "id" : "xyz", "keyA" : "blah blah blah" },
        { "id" : "fghi", "keyZ" : "blah blah blah" }],
        "anothernestednestedlist" : [
        { "id" : "asdf", "keyQ" : "blah blah" },
        { "id" : "yuiop", "keyW" : "blah" }] } ] }


def findkeys(node, kv):
    if isinstance(node, list):
        for i in node:
            for x in findkeys(i, kv):
               yield x
    elif isinstance(node, dict):
        if kv in node:
            yield node[kv]
        for j in node.values():
            for x in findkeys(j, kv):
                yield x

print(list(findkeys(d, 'id')))

Answer 4

def find(key, value):
  for k, v in value.items():
    if k == key:
      yield v
    elif isinstance(v, dict):
      for result in find(key, v):
        yield result
    elif isinstance(v, list):
      for d in v:
        for result in find(key, d):
          yield result

EDIT: @Anthon noticed that this will not work for directly nested lists. If you have this in your input, you can use this:

def find(key, value):
  for k, v in (value.items() if isinstance(value, dict) else
               enumerate(value) if isinstance(value, list) else []):
    if k == key:
      yield v
    elif isinstance(v, (dict, list)):
      for result in find(key, v):
        yield result

But I think the original version is easier to understand, so I will leave it.

Answer 5

pip install nested-lookup does exactly what you are looking for:

document = [ { 'taco' : 42 } , { 'salsa' : [ { 'burrito' : { 'taco' : 69 } } ] } ]

>>> print(nested_lookup('taco', document))
[42, 69]

Answer 6

I just wanted to iterate on @hexerei-software's excellent answer using yield from and accepting top-level lists.

def gen_dict_extract(var, key):
    if isinstance(var, dict):
        for k, v in var.items():
            if k == key:
                yield v
            if isinstance(v, (dict, list)):
                yield from gen_dict_extract(v, key)
    elif isinstance(var, list):
        for d in var:
            yield from gen_dict_extract(d, key)

Answer 7

This function recursively searches a dictionary containing nested dictionaries and lists. It builds a list called fields_found, which contains the value for every time the field is found. The 'field' is the key I'm looking for in the dictionary and its nested lists and dictionaries.

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 8

Another variation, which includes the nested path to the found results (note: this version doesn't consider lists):

def find_all_items(obj, key, keys=None):
    """
    Example of use:
    d = {'a': 1, 'b': 2, 'c': {'a': 3, 'd': 4, 'e': {'a': 9, 'b': 3}, 'j': {'c': 4}}}
    for k, v in find_all_items(d, 'a'):
        print "* {} = {} *".format('->'.join(k), v)    
    """
    ret = []
    if not keys:
        keys = []
    if key in obj:
        out_keys = keys + [key]
        ret.append((out_keys, obj[key]))
    for k, v in obj.items():
        if isinstance(v, dict):
            found_items = find_all_items(v, key, keys=(keys+[k]))
            ret += found_items
    return ret

Answer 9

I was not able to get the solutions posted here to work out-of-the-box so I wanted to write something that is a little more flexible.

The recursive function below that should allow you to collect all values that meet some regex pattern for a given key in an arbitrarily deeply set of nested dictionaries and lists.

import re

def search(dictionary, search_pattern, output=None):
    """
    Search nested dictionaries and lists using a regex search
    pattern to match a key and return the corresponding value(s).
    """
    if output is None:
        output = []

    pattern = re.compile(search_pattern)
    
    for k, v in dictionary.items():
        pattern_found = pattern.search(k)
        if not pattern_found:
            if isinstance(v, list):
                for item in v:
                    if isinstance(item, dict):
                        search(item, search_pattern, output)
            if isinstance(v, dict):
                search(v, search_pattern, output)
        else:
            if pattern_found:
                output.append(v)

    return output

If you want to search for a specific term, you can always make your search pattern something like r'\bsome_term\b'.

Answer 10

Here is my stab at it:

def keyHole(k2b,o):
  # print "Checking for %s in "%k2b,o
  if isinstance(o, dict):
    for k, v in o.iteritems():
      if k == k2b and not hasattr(v, '__iter__'): yield v
      else:
        for r in  keyHole(k2b,v): yield r
  elif hasattr(o, '__iter__'):
    for r in [ keyHole(k2b,i) for i in o ]:
      for r2 in r: yield r2
  return

Ex.:

>>> findMe = {'Me':{'a':2,'Me':'bop'},'z':{'Me':4}}
>>> keyHole('Me',findMe)
<generator object keyHole at 0x105eccb90>
>>> [ x for x in keyHole('Me',findMe) ]
['bop', 4]

Answer 11

Following up on @hexerei software's answer and @bruno-bronosky's comment, if you want to iterate over a list/set of keys:

def gen_dict_extract(var, keys):
   for key in keys:
      if hasattr(var, 'items'):
         for k, v in var.items():
            if k == key:
               yield v
            if isinstance(v, dict):
               for result in gen_dict_extract([key], v):
                  yield result
            elif isinstance(v, list):
               for d in v:
                  for result in gen_dict_extract([key], d):
                     yield result    

Note that I'm passing a list with a single element ([key]}, instead of the string key.

Answer 12

Since there's a maximum recursion depth in Python I would consider implementing an iterative approach for arbitrary size:

def get_ids(data: Dict, key: str) -> List:
    stack = [data]
    result = []
    while stack:
        elem = stack.pop()
        if isinstance(elem, dict):
            for k, v in elem.items():
                if k == key:
                    result.append(v)
                if isinstance(elem, (list, dict)):
                    stack.append(v)
        elif isinstance(elem, list):
            for obj in elem:
                stack.append(obj)
    return result

Answer 13

glom is a great library for searching and restructuring that can also do nested lookups using globs. Example:

In [1]: import glom

In [2]: data = { "id" : "abcde", "key1" : "blah", ... }  # OP example

In [3]: glom.glom(data, '**.id')
Out[3]: ['abcde', 'qwerty', 'xyz', 'fghi', 'asdf', 'yuiop']

The nesting levels are separated by dots (think of them as slashes in Unix globs), single star is a placeholder for one level, double star is a placeholder for multiple levels. In the above example, **.id means "id key on any level". More examples:

In [4]: glom.glom(d, ('*.*.id', glom.Flatten()))
Out[4]: ['qwerty']

This will go through all keys on third level only and extract the values for the id, whereas empty results are discarded (the nested results list is flattened).

Another example that collects id values specifically in the anothernestednestedlist list only:

In [5]: glom.glom(d, ('nestedlist', [('anothernestednestedlist', ['id'])]))
Out[5]: [['asdf', 'yuiop']]

However, the library can do a lot more than just that. Read the glom docs for more features.