Writing nested dictionary (forest) of a huge depth to a text file

Question

I have a huge depth dictionary that represents forest (many non-binary trees) which I want to process the forest and create a text file with all possible relations of the forest, e.g. given the dictionary:

{'a': {'b': {'c': {}, 'd': {}}, 'g': {}}}

the generated text file will look like:

a b c
a b d
a g

Note that the nested dictionary is big and iterating over it recursively is makes a memory run-time error.

What I tried doing is converting the dictionary into a list of lists recursively which yields a run-time error. The code:

def return_list(forest):
    for ent in forest.keys():
        lst = [new_ent] + grab_children(forest[ent])
        yield lst

def grab_children(father):
    local_list = []
    for key, value in father.items():
        local_list.append(new_key)
        local_list.extend(grab_children(value))
    return local_list

The error: "maximum recursion depth exceeded in comparison" RuntimeError

Please show your recursive code and the error. It's not clear how you want to permutate from your example. — Zev, Jul 24 '18 at 13:37
DFS, write a line for each terminator. Or just don't ever iterate recursively in python, if you can avoid it. — Kenny Ostrom, Jul 24 '18 at 13:37
Also see http://blog.moertel.com/posts/2013-05-11-recursive-to-iterative.html — Zev, Jul 24 '18 at 14:04

blhsing · Answer 1 · 2018-07-24T14:26:17.117

3

def l(d):
    return '\n'.join(k + (i and ' ' + i) for k, v in d.items() for i in l(v).split('\n'))
print(l({'a': {'b': {'c': {}, 'd': {}}, 'g': {}}}))

This outputs:

a b c
a b d
a g

edited Jul 24 '18 at 14:26

answered Jul 24 '18 at 14:06

blhsing

91,368
6
71
106

Thanks. How can I modify your code for printing into a text file? – Codevan Jul 24 '18 at 20:23
You can use the `file` parameter of the `print` function, e..g `with open('filename','w') as file: print(l(your_dict), file=file)` – blhsing Jul 24 '18 at 23:37
Thanks, but still recursive. – Codevan Jul 25 '18 at 08:57
Yes, but I don't think you'd hit the recursion limit nearly as easily with this code. – blhsing Jul 25 '18 at 08:58
For my nested dictionary, it does, – Codevan Jul 25 '18 at 08:59
I see. I've added an answer with a non-recursive approach then. – blhsing Jul 25 '18 at 10:46

Andrej Kesely · Accepted Answer · 2018-07-24T20:56:22.617

3

Without recursion, with generator and trampoline (with writing to file):

data = {'a': {'b': {'c': {}, 'd': {}}, 'g': {}}}


def write_dict(d, s=(), f_out=None):
    if len(d) == 0:
        if f_out:
            f_out.write(' '.join(s) + '\n')
        return

    for k, v in reversed(list(d.items())):
        yield write_dict, v, s + (k, ), f_out


with open('data_out.txt', 'w') as f_out:

    stack = [write_dict(data, f_out=f_out)]

    while stack:
        try:
            v = next(stack[-1])
        except StopIteration:
            del stack[-1]
            continue

        stack.insert(-1, v[0](v[1], v[2], v[3]))

The file contains:

a b c
a b d
a g

edited Jul 24 '18 at 20:56

answered Jul 24 '18 at 14:34

Andrej Kesely

168,389
15
48
91

Still recursive, isn't it? – user2390182 Jul 24 '18 at 14:35
2

@schwobaseggl No, the `yield write_dict()` returns new generator, it isn't calling itself recursively. I edited my answer to make it explicitly clear (`yield write_dict, v, s`) – Andrej Kesely Jul 24 '18 at 14:36
@AndrejKesely Thanks. How can I use your code to write the prints into a file? And if I would want BFS instead of DFS, how can I modify your code? I'll check your answer tomorrow and accept it. – Codevan Jul 24 '18 at 19:49
@AndrejKesely thanks, what do you think I should do if I get "OSError: [Errno 28] No space left on device" error when applying your function? – Codevan Jul 25 '18 at 09:00
@Codevan Is your input file huge size? Try with smaller parts and/or output to file which is on disk with enough space. Or you can try to print to stdout and pipe the stdout to gzip - that way you will compress the output. – Andrej Kesely Jul 25 '18 at 09:03
@AndrejKesely How exactly I can combine this - "print to stdout and pipe the stdout to gzip" in your code? – Codevan Jul 25 '18 at 09:05
Let us [continue this discussion in chat](https://chat.stackoverflow.com/rooms/176712/discussion-between-codevan-and-andrej-kesely). – Codevan Jul 25 '18 at 11:21
@AndrejKesely See also https://stackoverflow.com/questions/52060788/writing-nested-dictionary-forest-of-a-huge-depth-to-a-text-file-in-bfs-style?noredirect=1#comment91072462_52060788 – Codevan Aug 28 '18 at 15:20

blhsing · Answer 3 · 2018-08-29T01:51:37.470

1

A non-recursive approach:

d = {'a': {'b': {'c': {}, 'd': {}}, 'g': {}}}
p = q = []
while True:
    for k, v in d.items():
        if v:
            q.append((v, p + [k]))
        else:
            print(' '.join(p + [k]))
    if not q:
        break
    d, p = q.pop(0)

This outputs:

a g
a b c
a b d

edited Aug 29 '18 at 01:51

answered Jul 25 '18 at 10:46

blhsing

91,368
6
71
106

Writing nested dictionary (forest) of a huge depth to a text file

3 Answers3

Linked