Recursive dictate search with nested keys

Question

Recently, I had to solve a problem in a real data system with a nested dict / list combination. I worked on this for quite some time and came up with a solution, but I am very unhappy. I had to resort to using globals() and the named temporary global parameter.

I do not like to use global variables. It just requires an injection vulnerability. I believe that there should be a better way to accomplish this task without resorting to globals.

The set of task parameters:

 d = { "k":1, "stuff":"s1", "l":{"m":[ { "k":2, "stuff":"s2", "l":None }, { "k":3, "stuff":"s3", "l":{"m":[ { "k":4, "stuff":"s4", "l":None }, { "k":5, "stuff":"s5", "l":{"m":[ { "k":6, "stuff":"s6", "l":None }, ]} }, ]} }, ]} } 

Output Required:

 [{'k': 1, 'stuff': 's1'}, {'k': 2, 'stuff': 's2'}, {'k': 3, 'stuff': 's3'}, {'k': 4, 'stuff': 's4'}, {'k': 5, 'stuff': 's5'}, {'k': 6, 'stuff': 's6'}] 

My decision:

 def _get_recursive_results(d, iter_key, get_keys): if not 'h' in globals(): global h h = [] h.append({k:d.get(k) for k in get_keys}) d2 = d.copy() for k in iter_key: if not d2: continue d2 = d2.get(k) for td in d2: d3 = td.copy() for k in iter_key: if not d3: continue d3 = d3.get(k) if d3: return _get_recursive_results(td, iter_key, get_keys) h.append({k:td.get(k) for k in get_keys}) else: l = [k for k in h] del globals()['h'] return l 

Calling my function as follows returns the desired result:

 _get_recursively(d, ['l','m'], ['k','stuff']) 

How do I create a better solution?

Answer 1

This is a slightly modified version without using global variables. Set h to None by default and create a new list for the first call to _get_recursive_results() . Specify h later as an argument in recursive calls to _get_recursive_results() :

 def _get_recursive_results(d, iter_key, get_keys, h=None): if h is None: h = [] h.append({k:d.get(k) for k in get_keys}) d2 = d.copy() for k in iter_key: if not d2: continue d2 = d2.get(k) for td in d2: d3 = td.copy() for k in iter_key: if not d3: continue d3 = d3.get(k) if d3: return _get_recursive_results(td, iter_key, get_keys, h) h.append({k:td.get(k) for k in get_keys}) else: l = [k for k in h] return l 

Now:

 >>> _get_recursive_results(d, ['l','m'], ['k','stuff']) [{'k': 1, 'stuff': 's1'}, {'k': 2, 'stuff': 's2'}, {'k': 3, 'stuff': 's3'}, {'k': 4, 'stuff': 's4'}, {'k': 5, 'stuff': 's5'}, {'k': 6, 'stuff': 's6'}] 

No need to copy intermediate dicts. This is another modified version without copying:

 def _get_recursive_results(d, iter_key, get_keys, h=None): if h is None: h = [] h.append({k: d.get(k) for k in get_keys}) for k in iter_key: if not d: continue d = d.get(k) for td in d: d3 = td for k in iter_key: if not d3: continue d3 = d3.get(k) if d3: return _get_recursive_results(td, iter_key, get_keys, h) h.append({k: td.get(k) for k in get_keys}) else: return h 

Answer 2

This is not as general, but it does the job:

 def parse_tree(d, keys): result = [{key: d[key] for key in keys}] l = d.get('l', None) if l is not None: entries = l.get('m', []) for entry in entries: result.extend(parse_tree(entry)) return result >>> parse_tree(d, ['k', 'stuff']) [{'k': 1, 'stuff': 's1'}, {'k': 2, 'stuff': 's2'}, {'k': 3, 'stuff': 's3'}, {'k': 4, 'stuff': 's4'}, {'k': 5, 'stuff': 's5'}, {'k': 6, 'stuff': 's6'}] 

Answer 3

Use generator

With the following generator:

 def get_stuff(dct, iter_keys, get_keys): k, stuff = get_keys l, m = iter_keys if k in dct: yield {k: dct[k], stuff: dct[stuff]} if dct.get(l): for subdct in dct[l][m]: for res in get_stuff(subdct, iter_keys, get_keys): yield res list(get_stuff(d, ["l", "m"], ["k", "stuff"])) 

you get the results:

 list(get_stuff(d)) 

Python 3.3 provides a new yield from expression used to delegate assignment to a subgenerator. Using this expression, the code can be one line shorter:

 def get_stuff(dct): if "k" in dct: yield {"k": dct["k"], "stuff": dct["stuff"]} if dct.get("l"): for subdct in dct["l"]["m"]: yield from get_stuff(subdct) def get_stuff(dct, iter_keys, get_keys): k, stuff = get_keys l, m = iter_keys if k in dct: yield {k: dct[k], stuff: dct[stuff]} if dct.get(l): for subdct in dct[l][m]: yield from get_stuff(subdct, iter_keys, get_keys): 

Some methods to avoid globals

generators

Often, if you need to create a list and look for a replacement for global variables, generators can come in handy, because they save the status of the current work in its local variables, and the creation of the whole result is delayed by the consumption of the generated values.

recursion

Recursion stores subselects in local variables on the stack.

class instance with internal property

A class can serve as a tin to encapsulate your variables.

Instead of using a global variable, you store the intermediate result in the instance property.

Generalization for different data structures

In your comments, you mentioned that you get many different types with each dump.

I will assume that your data meets the following expectations:

• has a tree structure
• each node in the tree should contribute to the result (for example, the dictionary {"k": xx, "stuff": yy} )
• each node may contain subitems (list of trays)

One way to make the solution more general is to provide a list of keys to use to access the value / subitems; another option is to provide a function that does the job of getting the value and subitems of the node.

Here I use get_value to deliver the node value and get_subitems to deliver the trays:

 def get_value(data): try: return {"k": data["k"], "stuff": data["stuff"]} except KeyError: return None def get_subitems(data): try: return data["l"]["m"] except TypeError: return None 

Processing is performed as follows:

 def get_stuff(dct, get_value_fun, get_subitems_fun): value = get_value(dct) if value: yield value lst = get_subitems_fun(dct) if lst: for subdct in lst: for res in get_stuff(subdct, get_value_fun, get_subitems_fun): yield res 

called this way:

 get_stuff(d, get_value, get_subitems) 

The advantage of using functions is that it is much more flexible for any data structure that you would have to process (adaptation to other data structures will only require providing a custom version of the get_value and get_subitems - with the same or different names according to your preferences.

Answer 4

Edit: the first version had a bug fixed, which was fixed

I believe this should work, we use the power of recursion!

 def strip_leaves_from_tree(my_tree): result = list() row = dict() for key in my_tree: child = my_tree[key] if type(child) in (int, str,): row[key] = child elif isinstance(child, dict): result = strip_leaves_from_tree(child) elif isinstance(child, list): for element in child: result += strip_leaves_from_tree(element) if row: result = [row,]+result return result 

Answer 5

I confirmed that it works. Please check this out. Of course, it must be changed if you change the structure of the vocabulary list.

 def add(ret, val): if val is not None: ret.append(val) def flatten(d, ret): for k,v in d.items(): if isinstance(v, dict): add(ret,flatten(v, ret)) elif isinstance(v, list): for i in v: add(ret, flatten(i, ret)) elif k=='k': ret.append({'k':v,'stuff':d.get('stuff')}) ret = [] flatten(d, ret) 

Answer 6

Take a look at https://github.com/akesterson/dpath-python/blob/master/README.rst

This is a good way to search by dict.