suggestions how to keep "calculated" a lot of "dependent" parameters

Question

I have several indicators which need to be "always up to date". I.e. when anything is changed I need to recalculate "dependent". I have several levels where each next level should be calculated only when previous level is calculated. Let me explain by this shining picture:

At some point Assume that Franc changed. Then we should:

1. calc Franc / Dinar
2. calc Franc / Dinar / Peso

Or, if Peso, Franc and Dinar are changed all at once then we should:

1. calc Franc / Dinar
2. calc Franc / Dinar / Peso
3. calc Peso + Euro / (Euro + Usd)

So whenever anything at the Level 0 is chagned we should recalculate all other levels. But

• we should calculate only required items. If Euro changed we do not need to recalculate Franc / Dinar
• we should not calculate anything more than once. if Euro and Usd are changed at once we should calculate Euro + Usd only once (not twice).

The most straightforward solution would be:

• store each level in array
• for each item in array track "listeners" from next levels (could be difficulty because for example Peso has listeners from different levels - Franc / Dinar / Peso from Level2 and Peso + Euro / (Euro + Usd) from Level 3, so two-dimmension array is required..)
• if item is recalculated then mark all it listeners to be recalculated too
• go from Level 0 to last level and recalculate items that marked to be recalculated (initially updated items are market to be recalculated, for example Peso).

I guess that my problem is kind of well-known and probably you can suggest me general well-known solution. I don't want to reinvent the wheel :) Thanks!

Answer 1

I think the level-based approach is decent, on the assumption that listeners are always on a lower level.

The idea:

Have a 2D array containing your actual data, the first index is the level, the second is the position on the level. Let each element have a willBeRecalculated flag.

Have a toBeRecalculated list for each level (so an array of lists).

For each element, have a list of elements (the listeners) containing 2 integers - one for level and one for index.

For each element to be modified, add the element to toBeRecalculated on the appropriate level and set willBeRecalculated to true.

Then go through toBeRecalculated from the first to the last level, recalculating each element, setting its willBeRecalculated to false and, for each listener, looking up the applicable element, if willBeRecalculated is true, do nothing, otherwise, set willBeRecalculated to true and add it to toBeRecalculated on its (the listener's) level.

This approach doesn't go through all the data to check what needs to be modified / has been modified, it only checks applicable elements, and there are no repeated calculations.

Example:

For this:

(For my abbreviations I simply took the first letter of each word. I'm using 0-indexed arrays)

Actual data:

[[E, U, P, F, D],
 [E+U, F/D],
 [E/E+D, F/D/P],
 [P+E/E+U]
]

Listeners:

E:[(1,0), (2,0)] // E+U and E/E+U
U:[(1,0)] // E+U
P:[(2,1), (3,0)]
F:[(1,1)]
D:[(1,1)]
E+U:[(2,0)]
F/D:[(2,1)]
E/E+U:[(3,0)]

Modifying E and U:

Add E and U to toBeRecalculated[0] and set willBeRecalculated to true for both.

Go through toBeRecalculated[0].

When modifying E, set willBeRecalculated to false for it and set E+U's willBeRecalculated to true and add it to toBeRecalculated[1] and set E/E+U's willBeRecalculated to true and add it to toBeRecalculated[2].

When modifying U, set willBeRecalculated to false for it and we check E+U's willBeRecalculated and see it's true so do nothing.

Then go through toBeRecalculated[1]. When modifying E+U, set willBeRecalculated to false for it and check E/E+U's willBeRecalculated and see it's true so do nothing.

Note:

It might be better to have the listeners be pointers to the elements instead of a level and an index variable.