2

I have a lot of nested dictionaries, I am trying to find a certain key nested inside somewhere.

e.g. this key is called "fruit". How do I find the value of this key?

smci
  • 32,567
  • 20
  • 113
  • 146
TIMEX
  • 259,804
  • 351
  • 777
  • 1,080

5 Answers5

6

@Håvard's recursive solution is probably going to be OK... unless the level of nesting is too high, and then you get a RuntimeError: maximum recursion depth exceeded. To remedy that, you can use the usual technique for recursion removal: keep your own stack of items to examine (as a list that's under your control). I.e.:

def find_key_nonrecursive(adict, key):
  stack = [adict]
  while stack:
    d = stack.pop()
    if key in d:
      return d[key]
    for k, v in d.iteritems():
      if isinstance(v, dict):
        stack.append(v)

The logic here is quite close to the recursive answer (except for checking for dict in the right way;-), with the obvious exception that the recursive calls are replaced with a while loop and .pop and .append operations on the explicit-stack list, stack.

Alex Martelli
  • 854,459
  • 170
  • 1,222
  • 1,395
2

(Making some wild guesses about your data structure...)

Do it recursively:

def findkey(d, key):
    if key in d: return d[key]
    for k,subdict in d.iteritems():
        val = findkey(subdict, key)
        if val: return val
Marcelo Cantos
  • 181,030
  • 38
  • 327
  • 365
  • 2
    If any value that's not itself a dict is ever met in the recursion, this approach will try to index it, or call iteritems on that nondict, and thus fail quite peculiarly. – Alex Martelli Mar 26 '10 at 14:45
0

Just traverse the dictionary and check for the keys (note the comment in the bottom about the "not found" value).

def find_key_recursive(d, key):
  if key in d:
    return d[key]
  for k, v in d.iteritems():
    if type(v) is dict: # Only recurse if we hit a dict value
      value = find_key_recursive(v, key)
      if value:
        return value
  # You may want to return something else than the implicit None here (and change the tests above) if None is an expected value
Håvard S
  • 23,244
  • 8
  • 61
  • 72
  • that's not the way to check type of object. @jathanism: and what are the other possible ways of using recursive function? – SilentGhost Mar 26 '10 at 11:09
  • 1
    Hmmm... instead of `type(v)` is `dict`, shouldn't you use `instanceof(v, dict)`? The former does not accept subclasses of `dict`. Also, if you check for the existence of `__contains__` instead, your code will also accept other objects that support the "in" operator, not just dicts. – Tamás Mar 26 '10 at 11:21
  • @Tamás You could also use `isinstance()`, yes. However, dict was a given in this case. The `__contains__` suggestion would not necessarily be right - think about what would happen if you hit a list with that approach, for instance. – Håvard S Mar 26 '10 at 11:39
0

Almost 11 years later... based on Alex Martelli answer with slight modification, for Python 3 and lists:

def find_key_nonrecursive(adict, key):
    stack = [adict]
    while stack:
        d = stack.pop()
        if key in d:
            return d[key]
        for v in d.values():
            if isinstance(v, dict):
                stack.append(v)
            if isinstance(v, list):
                stack += v
Cristian
  • 584
  • 6
  • 13
0

I have written a handy library for this purpose.

I am iterating over ast of the dict and trying to check if a particular key is present or not.

Do check this out. https://github.com/Agent-Hellboy/trace-dkey

An example from README

>>> from trace_dkey import trace
>>> l={'a':{'b':{'c':{'d':{'e':{'f':1}}}}}}
>>> print(trace(l,'f'))
[['a', 'b', 'c', 'd', 'e', 'f']]

Now you can query it as l['a']['b']['c']['d']['e']['f']

>>> l['a']['b']['c']['d']['e']['f']
1
Prince Roshan
  • 144
  • 9