Optimization of variable multiplication_问答_开发者

[This was initially on matrices, but I guess it applies to any variable generically]

Say we have 开发者_StackOverflow社区Var1 * Var2 * Var3 * Var4.

One of them sporadically changes, which one of them is random.

Is it possible to minimize multiplications?

If I do

In case Var1 changes: newVar1 * savedVar2Var3Var4

I noticed that then I need to recalculate savedVar2Var3Var4 each time Var2, Var3, Var4 change.

Would that re-calculation of 'saved combinations' defy the purpose?

If you had a lot more numbers to multiply or if multiplication was extremely expensive then there is one thing I can think of to do.

If you had a huge number of numbers to multiply then you could separate them into sub-sets and memoize the product of each set. When a particular set changes, due to one of its members changing, then the memoized product becomes invalid and needs to be recomputed. You could do this at several levels depending on how expensive multiplication is, how much memory you have available, and how often things change. How to best implement this in C probably depends on how the variables go about changing -- if an event comes in that says "here is a new value for C" then you can invalidate all products that had C in them (or check that old C actually is different from new C before invalidation). If they are volatile variables then you will probably just have to compare each of the current values to the previous values (and this will probably take as much or more time as just multiplying on any machine with a hardware multiply instruction).

So, if you have:

answer = A * B * C * D * E * F * G * H;

then you could do separate those out to:

answer = ( (A * B) * (C * D) ) * ( (E * F) * (G * H) );

Then, if rather than having this multiplication done directly in C you were to do it on an expression tree:

                         answer
                            *
                           / \
                          /   \
                         /     \
                     ABCD       EFGH
                     *             *
                    / \           / \
                   /   \         /   \
                 AB    CD       EF    GH
                 *      *       *      *
                / \    / \     / \    / \
               A   B  C   D   E   F  G   H

Then at each level (well maybe just the top few levels) you could have a memoized sub-answer as well as some data to tell you if the variables below it had changed. If events come in to tell you to change a variable then that could cause the invalidation of the expression to propagate upward upon receipt of the event (or just recompute the memoized sub-answers for each event). If variables just magically change and you have to examine them to tell that they did change then you have more work to do.

Oh, another way to do this just popped in my head, and I'm ashamed that I didn't think of it earlier. If you do know the old and new values of a variable that has changed then, as long as the old value was not 0, you could just:

new_answer =  (old_answer * new_var) / old_var;

In real math this would work, but in computer math this might lose too much precision for your purposes.

In the first place, micro-optimizations like this are almost never worthwhile. Time your program to see if there is a performance problem, profile to see where the problem is, and test after making changes to see if you've made things better or worse.

In the second place, multiplications of numbers are generally fast in modern CPUs, while branches can be more expensive.

In the third place, the way you're setting it up, if Var1 changes, you'll need to recalculate savedVar1Var2Var3, saved Var1Var2Var4, saved Var1Var3Var4, and the whole product. Obviously, you're better off just recalculating the total.

Yes, it is possible.

For scalars there will probably be no benefit. For largish matrix math, you could compute and store: Var1*Var2 and Var3*Var4. Your result is the product of these 2 things. Now when one changes you only need to update 2 products instead of 3. Update only one of the 2 stored products depending who change, and update the result.

There you have it, 2 multiplications instead of 3 with each update. This will only benefit you if the common case really is for only one of them to update, but if that's true it should help a lot.

I don't think you save any time. Every time one of the N variables changes, you need to calculate (N - 1) additional products, right? Say you have A, B, C, and D. A changes, and you have saved the product of B, C, and D, but now you must recalculate your cached ABC, ABD, and ACD products. You are, in fact, doing additional work. ABCD is three multiply operations, while ABCD, ABC, ACD, and ABD works out to SEVEN.

The answer depends on how often the values change. With your example, calculating savedVar2Var3Var4 costs you two multiplications, with one additional multiplication each time Var1 changes (or you otherwise need to calculate the total). So: how many times do Var2, Var3, Var4 change, compared to Var1?

If Var1 changes more than about 3 times as often as the others, it should be worth recalculating savedVar2Var3Var4 as needed.

I don't think the gain is worth the effort, unless your "multiply" operation involves heavy calculations (matrices?).

edit: I've added an example that shows you... it's not worth it :)

T multiply(T v1, T v2, T v3, T v4)
{
    static T v1xv2 = v1*v2;
    static T v1xv3 = v1*v3;
    static T v1xv4 = v1*v4;
    static T v2xv3 = v2*v3;
    static T v2xv4 = v2*v4;
    static T v3xv4 = v3*v4;

    static T v1save = v1;
    static T v2save = v2;
    static T v3save = v3;
    static T v4save = v4;

    if v1save != v1 
    {
        v1save = v1;
        v1xv2 = v1*v2;
        v1xv3 = v1*v3;
        v1xv4 = v1*v4;
    }

    if v2save != v2
    {
        v2save = v2;
        v1xv2 = v1*v2;
        v2xv3 = v2*v3;
        v2xv4 = v2*v4;
    }


    if v3save != v3
    {
        v3save = v3;
        v1xv3 = v1*v3;
        v2xv3 = v2*v3;
        v3xv4 = v3*v4;
    }

    if v4save != v4
    {
        v4save = v4;
        v1xv4 = v1*v4;
        v2xv4 = v2*v4;
        v3xv4 = v3*v4;
    }

    return v1xv2*v3xv4;

}

Suppose you had a sum of many many variables, like Sum = A+B+C+D+.... and one of them changed, like C. If C' is the old value of C, then you could just say Sum += (C-C');

Same idea for a product: Product *= C/C';. (For matrices, they would have to be invertible.)

Of course, you might get creeping roundoff errors, so once in a while you could recalculate the whole thing.

I would try something like this:

var12 = var1*var2;
var34 = var3*var4;
result = var12*var34;
while (values available) {
        get new values;
        if (var1 changes || var2 changes) var12 = var1*var2;
        if (var3 changes || var4 changes) var34 = var3*var4;
        result = var12*var34;
}

There is no overload (only change checking) and it can be used for matrices (doesn't rely on commutativity, only associativity).