Represent a tree with specific constraints with processes. Too much memory?

Questions / Help
, , ,
1

Hi everyone.

I am working on a personal project where I need to represent a horizontal tree in a visual way for a user to interact with it, like shown at FIG. 1.

FIG. 1

IMG_2128.jpg2798Ă—2568 1.14 MB

I have thought about representing it as a list of lists as it usually goes, but I have this constraints:

  • I need to increase the depth of the tree at user request
  • The content of the new nodes (at depth expansion) depends solely on the leafs of the tree

To do this, I need to know the content of each leaf every time I want to increase its depth, and transversing the lists every time seems unnecessary and expensive. With other programming languages I could store the memory reference of each leaf at creation time, but with elixir this is not possible.

It came to my mind the possibility to make every node a process, having a “tree manager” that stores the PID of the root and the PIDs of each leaf. Leading to interact directly with the leafs at depth expansion without interacting with the rest of the nodes. But my lack of experience doesn’t let me know if this is unnecessary memory usage, seeing that a process uses 338 words when spawned, including a heap of 233 words compared with other data structures.

The tree is not very wide, but can increase its depth at user request. Maybe I can set a limit to change the root of the tree for one closer to the leafs every time the user passes it.

What do you guys think?

2

I would just represent it as a map of maps, or if you really need efficiency with querying and such then perhaps a :graph (the BEAM comes with a graph module for graph data structures).

2 Likes
3

That might be a good use case to test neo4j.

1 Like
4

Any specifics of why maps rather than lists? My concern about this approach is that what’s in the middle of the tree doesn’t matter for the depth expansion, but I trust your advice. I may do a little demo to see it in action.

I am also checking the graph module, thank you very much!

5

Really interesting, I enjoyed it. I am not interacting or querying the data the graph contains though. It is only for visualization of text information.

6

Easier to do positional lookup primarily, but there is also the idea that you could encode the path as keys and just flatten the whole tree into a single map (at which point if you need full speed then you could lift that into ETS itself later on). :slight_smile:

1 Like
7

With FP You can use a [zipper](https://en.wikipedia.org/wiki/Zipper_(data_structure) to traverse the tree.

@OvermindDL1 could explain what a zipper is much better than I might.

1 Like
8

Hehe, I love zippers. Even in a flat encoding you can keep a special data structure to hold a fresh zipper to start iterations from if you need. ^.^

1 Like
9

Wow.

but there is also the idea that you could encode the path as keys and just flatten the whole tree into a single map

Didn’t thought about that, thank you a lot for the suggestion. At the beginning I was thinking on creating the tree first, and then transverse it to “draw” it on the browser with dot. But I could draw it on the go and at the same time save the tree as a flat map. So if the user wants to access a node, or expand the tree, I can access directly to its value on the map. :thumbsup:

1 Like