CODEWITHSUNDEEP
pythonpython-3.xrecursiontail-recursion
texasflood
texasflood

Reputation: 1633

Remove recursion from this Python generator

I have a generator that iterates over all combinations of keys up to a particular depth in a nested dictionary:

def iter_dict(levels, input_dict, items=[], sort=False, **sort_args):
    for dict_key, val in (sorted(input_dict.items(), **sort_args) if
                          sort else input_dict.items()):
        if levels == 1:
            yield items + [(dict_key, val)]
        else:
            yield from iter_dict(levels - 1, val, items + [(dict_key, val)])

So it acts like so:

>>> d = {'a': 1, 'b': 2}
>>> list(iter_dict(1, d))
[[('a', 1)], [('b', 2)]]

And

>>> d = {'a': {'c': 1}, 'b': {'d' : 2}}
>>> list(iter_dict(1, d))
[[('a', {'c': 1})], [('b', {'d': 2})]]
>>> list(iter_dict(2, d))
[[('a', {'c': 1}), ('c', 1)], [('b', {'d': 2}), ('d', 2)]]

Each iteration on the generator returns a list of tuples, with the nth tuple being (key, value) at a depth of n into the nested dictionary.

But I am implementing this function on huge dictionaries and am worried about reaching the maximum recursion depth level.

How can I rewrite the generator to remove the recursion?

Upvotes: 1

Views: 133

Answers (1)

tobias_k
tobias_k

Reputation: 82929

But I am implementing this function on huge dictionaries and am worried about reaching the maximum recursion depth level

Unless your dictionaries actually have 1000+ levels of nesting, this should not be a problem. Maximum recursion depth is really only about the depth; the branching factor is not an issue. That is, it can be quite an issue w.r.t. running time, but you won't get a maximum recursion depth error from that (and the running time will be just the same without recursion).

How can I rewrite the generator to remove the recursion?

I guess this can be done using a stack and storing sequences of keys on the stack (all the keys to the current sub-dict). Such a solution will probably be a bit more involved and not as elegant as the recursive algorith, so given the above, I don't think it's worth the effort.

But whatever, here you go (slightly simplified, without the sorting):

from functools import reduce
def iter_dict(levels, input_dict):
    def get_nested(keys):
        return reduce(lambda d, k: d[k], keys, input_dict)
    stack = [[k] for k in input_dict]
    while stack:
        keys = stack.pop()
        if len(keys) == levels:
            yield [(k, get_nested(keys[:i])) for i, k in enumerate(keys, 1)]
        else:
            stack.extend(keys + [k] for k in get_nested(keys))

Example:

>>> d = {'a': {'c': 1, "e": 2}, 'b': {'d' : 3, "f": 4}}
>>> list(iter_dict(2, d))
[[('a', {'c': 1, 'e': 2}), ('e', 2)],
 [('a', {'c': 1, 'e': 2}), ('c', 1)],
 [('b', {'d': 3, 'f': 4}), ('f', 4)],
 [('b', {'d': 3, 'f': 4}), ('d', 3)]]

Upvotes: 1

Related Questions