I have a bunch of objects that I am not sure on how to represent in order to maximize memory occupancy and possibly avoiding large CPU overhead. The most natural way to see the whole data structure is as a tree. A picture is worth a thousand words
Each tree node contains an object that I simply represented as an integer. As you can guess, at each layer there are many nodes that are equal. For example, the last layer has 48 leaves; however, there are only two different kind of data in the leaves, namely
In addition, between each two connected node there may be a bunch of other objects. At each layer, the list are all equal. I've just shown an example using the
L_0 array on the two edges of the first layer.
Each layer of the list can be thought as having a
label, as shown on the left of the tree. Now, based on some other checks, not relevant for our purposes, some of the paths may be cancelled. The cancellation condition can be thought as
def cancellEdges(node1, node2): if node1.label == node2.label AND notInPattern(node1.data, node2.data): deleteEdgesBetweenNodes(node1, node2)
In our example the pattern is shown in the top-right corner. We observe that all the edges between
8 are useless, which in turn means that the leaves labeled as
8 descendant from
0 should not be reachable. In the same fashion, the edges
1 -> -> 9 and
10 are useless. In the picture, this fact is represented by a red background for the nodes whose incoming edge is useless.
At the last layer, the same thing happens. In this case we have also blue nodes, that simply signals that the incoming edge to that node is useless not (only) because of the pattern, but because the parent is red.
Basically, each element of the
L_x lists can be thought of
SimpleNode (the array-like objects in the picture); all the nodes belonging to a layer are instead
AggregateNode (the elliptic shapes in the picture). The red arrows shows the links between the nodes of the linked list.
class SimpleNode: data: int nxt: SimpleNode prv: SimpleNode class TreeNode: data: int parents: List[TreeNode] childs: List[TreeNode] class AggregateNode extends SimpleNode: tnodes: List[TreeNode] label: string
Since the edge cancellations may happen only between nodes with the same
label, I've decided to use additional pointers to connect the internal
tnodes to their parents/childs with the same
label. Take care that this parents/childs are not the same ones of the original tree. For example node
9, in the full tree, has 3 parents:
6; in the linked list it only has
0 as parent.
How can we keep track of the total number of active paths? It would also be useful to do this incrementally, without having to check the whole tree at the end. In other words, it may be a property of a
AggregateNodeor even a global property. In our case, f.e. we should have for the last aggregate node
numberOfPaths = 15or, equivalently,
tnode11.numberOfPaths = 10and
How can we expand the whole tree starting from the new linked list? Or also, how can we traverse (depth-first or bread-first, it doesn't really matter) the paths from the list?
Is this structure the best we can do? Is there a better data structure that can be used in this case?