How to flatten a nested dictionary without recursion?

python flatten dictionary
python recursively flatten json
iterate through nested dictionary python
flatten nested dictionary python pandas
python flatten nested dictionary comprehension
flatten a nested dictionary java
python flatten dictionary of lists
python unpack nested dictionary

I came across this function that can flatten a dictionary:

def flatten(dictionnary, container=None):
    if container is None:
        container = []
    for k, v in dictionnary.items():
        container.append(k)
        if v:
            flatten(v, container)
    return container

to test it I created a dictionnay that is nested n times like so:

nesteddict = {}
for i in range(n, 0, -1):
    emptydict = {}
    emptydict[i] = nesteddict
    nesteddict = emptydict

the function works while n is less than 999, otherwise it hit recursion limit:

RecursionError: maximum recursion depth exceeded while calling a Python object

so after a little bit of searching it seems that any recursive function can rewritten to iteration but I cant see how it could be done for the function I have to produce the same results.

Another weird problem I came across while playing with this is if I try the code below for n >= 998:

nesteddict = {}
for i in range(n, 0, -1):
    emptydict = {}
    emptydict[i] = nesteddict
    nesteddict = emptydict
print(nesteddict)

I get recursion error:

RecursionError: maximum recursion depth exceeded while getting the repr of an object

which is weird since I dont see any recursion here.

Instead of saving the dict in the stack, you should save the item's iterator in stack.

This way, you can resume the iterator on command.

Also because you're pausing and resuming the execution of iterators in order, the result will always be according to the order of the dict.

By the way, @iBug, dicts are ordered as per Python's specification from 3.7

def flatten(dictionary, container=None):
    if container is None:
        container = []
    iterators = []
    iterator = iter(dictionary.items())
    while True:
        for k, v in iterator:
            container.append(k)
            if v:
                # Save the current iterator for later
                iterators.append(iterator)
                # Run on the new dict
                iterator = iter(v.items())
                break

        # Current iterator is done, fetch the next one
        else:
            try:
                iterator = iterators.pop()
            except IndexError:
                return container

print(flatten({1: None, 2: {3: None, 4: None}, 5: None}))
[1, 2, 3, 4, 5]

python - How to flatten a nested dictionary without recursion?, I came across this function that can flatten a dictionary: def flatten(dictionnary, container=None): if container is None: container = [] for k, v in dictionnary.items():​  The following function is an example of flattening JSON recursively. Code at line 16 and 20 calls function “flatten” to keep unpacking items in JSON object until all values are atomic elements (no dictionary or list). In the following example, “pets” is 2-level nested. The value for key “dolphin” is a list of dictionary.

Logically, nested dictionaries (and lists) is a kind of recursion, so if you want to avoid logical recursion, that's impossible.

But, since recursion is just recursion, you can keep a stack of your own and simulate that in a loop:

def flatten(dct, c=None):
    if c is None:
        c = []
    stack = [dct]
    while stack:  # non-empty
        d = stack.pop()
        for k, v in d.items():
            c.append(k)
            if v:
                stack.append(v)
    return c

This function well emulates the behavior of function recursion, with a custom stack.

There's one potential downside: Theoretically, a dictionary like

{1: None, 2: {3: None, 4: None}, 5: None}

should be flattened as [1, 2, 3, 4, 5], while this method would give [1, 2, 5, 3, 4]. This is much like a DFS search vs a BFS search on a graph.

But, since dictionary is unordered, this shouldn't be a big matter (unless you're using collections.OrderedDict), and that's why I say this is a potential downside.

How To Flatten a Dictionary With Nested Lists and Dictionaries in , Here is a function that will flatten a dictionary, which accommodates nested that will default to an underscore if no custom separator is specified. our flattened dictionary and will be added to at the end of each recursion. Logically, nested dictionaries (and lists) is a kind of recursion, so if you want to avoid logical recursion, that's impossible. But, since recursion is just recursion, you can keep a stack of your own and simulate that in a loop: This function well emulates the behavior of function recursion, with a custom stack.

If you want to do it without recursion, it is impossible.

So Here the solution for the RecursionError.

Based on the doc of python. You could use sys.getrecursionlimit() to see the limit of recursion. You could also use sys.setrecursionlimit() to make the limit upper.

Python, Given a nested dictionary, the task is to convert this dictionary into a flattened dictionary where the key is separated by '_' in case of the nested key to be started​. In the above program, the first loop returns all the keys in the nested dictionary people. It consist of the IDs p_id of each person. We use these IDs to unpack the information p_info of each person. The second loop goes through the information of each person.

Python, Given a flattened dictionary, the task is to convert that dictionary into a nested dictionary where keys are Method #2: Using default dict and recursive approach. Following recursive function is called repetitively if the value component of each item in directory is a directory itself. def iterdict(d): for k,v in d.items(): if isinstance(v, dict): iterdict(v) else: print (k,":",v) iterdict(D1)

Flatten dictionary in Python (functional style), Write a function flatten_dict to flatten a nested dictionary by joining the keys with . character. So I decided to give it a try. Here is what I have and it  Approach to flatten JSON. There are many ways to flatten JSON. There is one recursive way and another by using the json-flatten library. Recursive Approach: Now we can flatten the dictionary array by a recursive approach which is quite easy to understand. The recursive approach is a bit slower than using json-flatten library. Example:

Pythonic way to flatten nested dictionarys, There's no need to add additional fluff to your comments. Function to flatten a nested dictionary structure :param dictionary: A python dict()  5 Flatten without recursion 6 Flatten nested lists 7 A list of tuples 8 Flatten 2d array 9 A list of NumPy arrays 9.1 numpy.ravel() 9.2 numpy.flatten() 9.3 numpy.reshape(-1) 10 Flatten JSON objects 11 Flatten a list of objects 12 Flatten a list of DataFrames 13 Flatten & remove duplicates 14 Flatten a dictionary into a list 15 Using reduce

Comments
  • stackoverflow.com/a/953097/941722 I think you should take a look at this answer, may be an good option.
  • Perfect answer, thank you. If you dont mind I have another function and would like your help, the function is called del_key(dictionary, key) and it body is return {k: del_key(v, key) for k, v in dictionary.items() if k != key}, it takes a dictionary and a key that need to be deleted from that nested dictionary, thanks again.
  • The first paragraph looks like the opposite of my answer. Are you sure?
  • Plus, it's not recommended to sys.setrecursionlimit to an arbitrarily high value, as it relies heavilybl on system resources.