4
$\begingroup$

Example of Data

This is the data for one monkey. There are many similar but different monkeys.

X(Y,Z) means Y, Z are parent of X.

A(D,E)  If monkey see banna (D) and monkey is hungry (E), it squeaks (A).
B(E,F)  If monkey is hungry (E), and monkey see other monkey, it jumps(B).
C(D,F)  If monkey see banna (D), and it is not hungry (E), it walks away(C).   
0(A,B)  If monkey squeak(A) and jumps(B), it grabs the banna
        with priority 10 and reduce priority for doing other
        things (0).

D, E, F are the source.

Notice that this is not a tree. A-C-D is a undirected cycle. Trees have no cycle (wikipedia). The priority and the words at right are not part of the data structure I am interested in (at this moment).

Question

Is there a data structure that conserves memory and allow reasonably efficient recalculation of values for the following case?

The data structure is for the rete algorithm (https://en.wikipedia.org/wiki/Rete_algorithm).

[Description of the data]

  1. Each node (except the end points) has exactly two parents.
  2. Any two parents have at most one child.
  3. A node can be the parent of multiple nodes.
  4. Each node has value, which is a boolean. (Or an array of fixed number of boolean for sharing the nodes between different monkeys.)
  5. Value of child is logical and of values of its parents.
  6. Want to keep all values of the nodes to save recalculation time.

[Operations on the data structure]

  1. The structure of the graphs never changes. I don't mind taking a long time to construct the data structure.
  2. When value of a node changes, values of its children are recalculated. The values of the end points occasionally changes in every cycles of calculation.
  3. Want to know if the predefined interesting nodes (for example we know that node 0,3,and 5 are interesting.) change value.
  4. Don't need to query or look up for any particular values among the nodes. Also don't need to output values of all the nodes (that would take too much time.)

There are lots of nodes, and lots of parent-child relationships, because there are lots and lots of rules, and lots of slightly different monkeys.

(I have never taken any computer science class... I learned everything online. Sorry if I use the wrong terms.)

$\endgroup$
  • $\begingroup$ by the way, is there a name for this situation? $\endgroup$ – dot dot dot Oct 16 '16 at 21:15
  • $\begingroup$ Do you have this common subtree or have to find it? Recalculations are essentialy the same among all shared resources? So if you allocate such subtree separately and add list of parents to the root is it ok? $\endgroup$ – Evil Oct 16 '16 at 21:15
  • 1
    $\begingroup$ @Evil: I finally get what you mean by common subtree. stackoverflow.com/questions/37065538/… $\endgroup$ – dot dot dot Oct 17 '16 at 0:11
  • 1
    $\begingroup$ It's unclear to me what you're trying to optimise. Assuming you're trying use as little memory as possible to represent the data (since you said Is there a data structure that conserves memory for the following case?), then it's as easy as only storing the data of the so called "end points" since value of all other points can be calculated as needed. OR perhaps you are implicitly wanting something else as well from this data structure, such as, low update time or low query time. In short, try to re-explain what you really want. $\endgroup$ – Apiwat Chantawibul Oct 17 '16 at 1:31
  • 2
    $\begingroup$ What operations are you looking to perform on this data structure, to read values from it? Is the only thing you want to do is to output all values of all nodes? Or do you want to be able to look up the value of a node quickly? Are all queries available in advance, or do you have to handle them in realtime? $\endgroup$ – D.W. Oct 17 '16 at 4:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.