novel approach to calculations
Hi,
I am in a little bit of a bind trying to perform some computations in a clean and efficient way. Basically I have some arrays of doubles (a1[],a2[],a3[]). each value in a1 corresponds to an period so a1[0] = period 1 a2[0] = period 2 and so forth. a2 and a3 each correspond to the periods but a2[0] might start at period 4 and increment by 1 etc.
so anyways, heres the tricky part. there are different formulas for a1 calculations, a2 calculations and a3 calculations. each one has its own TYPE of calculation and then METHOD. So A1 receives its method from the database as does A2 and A3 except that their respective methods are of a certain type unique to A1 A2 and A3. I basically use reflection to call their respective methods but a problem arises because A2 and A3's calculations not only rely on A1's but they could be dependant on each others.
For example A2's formula could be A1*A3 or A3's could be A1/A2
Hopefully whoevers reading follows because now if we throw in an A4 whose method requires that if theres an A2 or A3 that the total of their respective formulas be used in the calculation in the A4 method.
This creates a problem because i may not have an A2 or an A3 or in a case where I have both and i must calculate A4, I do not know before getting to the A4 method 1) if A2 or A3 have been calculated and 2) if the unique method applying to A4 even requires A2 or A3 (because A4 might have multiple methods, one of which does not requires the other values).
The real big issue is that this has to be abstract enough that there is no set order for when these formulas are calculated (with the exception of A1). So I can be in a position where I am calculating A4 before A3 and A2 yet A4 needs the values of A2 and A3. Even though im calculating A4, I need A2 and A3 seperate so they need to be calculated regardless. So I dont want to get in a position where I get to A4, and call the formulas for A2 and A3 within it and then have to calculate A2 and A3 again afterwards and I don't want to use flags because I can have Ainfinity.
If you can decipher what I just typed out, do you have any brilliant ideas how it can be approached efficiently?
Much Appreciated.
[2247 byte] By [
celfiea] at [2007-10-1 1:51:24]
So your requirements include:
1) D can depend on B and C being calculated already
2) The order of calculation of B, C, and D must be arbitrary
You see the problem here, right? This is not a computer science issue, it's just impossible. Either the predicate steps have to always happen first, or all steps must be independent of one another - your requirements are mutually exclusive.
Consider the lowly spreadsheet.
The value in a cell is calculated using a formula that depends on the values in other cells.
If you have a circular definition such as A=B+1 and B=A+1 then you do not ingeneral have a solvable system.
If your question was, can this circular definition happen, the answer is yes. If you are not carefull defining your formulae it is very easy to create a system that has no solution.
If your question was how do you properly evaluate a system that does not have a circular definition, or equally useful, how do you detect that a system has a circular definition, you need to look up "topological sorting"
Basically you need to look at the dependancy graph. So a formula like A = B + C means that A depends on B and A depends on C and rather obviously you want to calculate B before you calculate A and you want to calculate C before you calculate A.
You may think of these dependancies as determining an order relationship. In the case I gave B < A and C < A meaning that the calculation of B must come before the calculation of A.
This collection of order relationships which you get from looking at each of the formulae that you must eventually calculate determines a partial order. The word partial refers to the fact that if I just give you the two ordering B<A and C><A you don't know whether B><C or C><B
The job of a topological sort is to take a collection of order relations from a partial order and to give you a list that is completely ordered. This means that no item shows up on the list "before it's time" so that if you calculate the items in the list order you will never violate a dependancy constraint.
Lastly, the standard topological sort algorithm conveniently FAILS if there is a circular definition somewhere.
So that is basically how the spreadsheets handle the problem of ordering their calculations and I don't see anything that makes your problem sound any different.
If google does not lead you to a defination or code for a topo sort, Knuth's ancient book on Sorting and Searching has it.
Enjoy>
