变量乘法的优化

Question

[这最初是在矩阵上,但我想它通常适用于任何变量]

说我们有Var1 * Var2 * Var3 * Var4.

其中一个零星地改变,其中一个是随机的.

是否可以最小化乘法？

如果我做

In case Var1 changes: newVar1 * savedVar2Var3Var4

我注意到,每当Var2,Var3,Var4改变时,我需要重新计算savedVar2Var3Var4.

重新计算"已保存的组合"是否会违背目的？

Answer 1

如果你有更多的数字要乘,或者如果乘法非常昂贵,那么有一件事我能想到要做.

如果你有大量的数字要加倍,那么你可以将它们分成子集并记住每组的产品.当某个特定集发生更改时,由于其中一个成员发生更改,则备忘产品将变为无效并需要重新计算.您可以在多个级别执行此操作,具体取决于乘法的成本,可用的内存量以及更改的频率.如何在C中最好地实现这一点可能取决于变量如何变化 - 如果一个事件出现"这里是C的新值",那么你可以使所有产品中包含C的产品无效(或检查旧的C实际上与失效前的新C不同).

所以,如果你有:

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

然后你可以将这些分开:

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

然后,如果不是直接在C中完成这个乘法,那么你应该在表达式树上进行:

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

然后在每个级别(也许只是前几个级别)你可以有一个memoized子答案以及一些数据来告诉你它下面的变量是否已经改变.如果事件进来告诉您更改变量,则可能导致表达式失效在收到事件时向上传播(或者只是重新计算每个事件的记忆子答案).如果变量只是神奇地改变而你必须检查它们以告诉它们确实发生了变化,那么你还有更多的工作要做.

哦,另一种做到这一点的方法就是突然出现在我脑海里,我很惭愧,我没想到它.如果您确实知道已更改的变量的旧值和新值,只要旧值不为0,您就可以:

new_answer =  (old_answer * new_var) / old_var;

在实际数学中,这可以工作,但在计算机数学中,这可能会失去太多精确度以达到您的目的.

Answer 2

首先,像这样的微观优化几乎是不值得的.为您的程序计划是否存在性能问题,查看问题所在的配置文件,并在进行更改后进行测试,看看您是否做得更好或更糟.

第二,数字的乘法在现代CPU中通常很快,而分支可能更昂贵.

排在第三位,顺便说一下你设置它,如果Var1变更,就需要重新计算savedVar1Var2Var3,saved Var1Var2Var4,saved Var1Var3Var4,和整个产品.显然,你最好只重新计算总数.