变量乘法的优化

Question

[这最初是在矩阵上，但我想它一般适用于任何变量]

假设我们有 Var1 * Var2 * Var3 * Var4。

其中之一是零星变化的，哪一个是随机的。

是否可以最小化乘法？

如果我这样做

In case Var1 changes: newVar1 * savedVar2Var3Var4

，我注意到每次 Var2、Var3、Var4 发生变化时，我都需要重新计算 savingVar2Var3Var4。

重新计算“已保存的组合”是否违背了目的？

Answer 1

如果您有更多的数字需要相乘，或者如果乘法非常昂贵，那么我可以想到做一件事。

如果您有大量数字需要相乘，那么您可以将它们分成子集并记住每组的乘积。当特定集合发生变化时，由于其中一个成员发生变化，那么记忆的乘积就会变得无效并需要重新计算。您可以在多个级别上执行此操作，具体取决于乘法的成本、可用内存的大小以及事物更改的频率。如何在 C 中最好地实现这一点可能取决于变量如何变化——如果出现一个事件说“这是 C 的新值”，那么您可以使所有包含 C 的产品无效（或者检查旧的产品） C 实际上与失效前的 new 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

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

哦，另一种方法突然出现在我的脑海中，我很遗憾我没有早点想到它。如果您确实知道已更改的变量的旧值和新值，只要旧值不为 0，您就可以：

new_answer =  (old_answer * new_var) / old_var;

在实际数学中，这可行，但在计算机数学中，这可能会导致您的精度损失太多。目的。

Answer 2

首先，像这样的微观优化几乎不值得。对程序进行计时以查看是否存在性能问题，分析以查看问题所在，并在进行更改后进行测试以查看是否使事情变得更好或更糟。

其次，现代 CPU 中的数字乘法通常速度很快，而分支运算的成本可能更高。

第三，你设置的方式，如果Var1改变，你需要重新计算savedVar1Var2Var3，saved Var1Var2Var4， 保存了 Var1Var3Var4 以及整个产品。显然，您最好重新计算总数。

Answer 3

是的，这是可能的。

对于标量来说可能没有任何好处。对于较大的矩阵数学，您可以计算并存储：Var1*Var2 和 Var3*Var4。你的结果是这两件事的乘积。现在，当一项更改时，您只需更新 2 个产品，而不是 3 个。根据更改者仅更新 2 个存储的产品之一，然后更新结果。

就这样，每次更新都是 2 次乘法，而不是 3 次。仅当常见情况确实只有其中一个需要更新时，这才会对您有利，但如果这是真的，它应该会有很大帮助。

Answer 4

我不认为你能节省任何时间。每当 N 个变量之一发生变化时，您就需要计算 (N - 1) 个额外的乘积，对吧？假设您有 A、B、C 和 D。A 发生更改，并且您已经保存了 B、C 和 D 的乘积，但现在您必须重新计算缓存的 ABC、ABD 和 ACD 乘积。事实上，你正在做额外的工作。 ABCD 是三个乘法运算，而 ABCD、ABC、ACD 和ABD 相当于七。

Answer 5

答案取决于值变化的频率。在您的示例中，计算 savingVar2Var3Var4 需要两次乘法，每次 Var1 更改时都会增加一次乘法（否则您需要计算总数）。那么：与 Var1 相比，Var2、Var3、Var4 改变了多少次？

如果 Var1 的变化频率是其他变量的 3 倍以上，则值得根据需要重新计算 savingVar2Var3Var4。

Answer 6

我认为这种收获不值得付出努力，除非您的“乘法”运算涉及大量计算（矩阵？）。

编辑：我添加了一个示例来向您展示...这不值得:)

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;

}

Answer 7

假设您有许多变量的总和，例如 Sum = A+B+C+D+....，并且其中一个变量发生了变化，例如 C。如果 C' 是 C 的旧值，那么您可以直接说 Sum += (CC');

对于产品来说同样的想法： 产品 *= C/C';。 （对于矩阵，它们必须是可逆的。）

当然，您可能会遇到渐进的舍入错误，因此偶尔您可以重新计算整个过程。

Answer 8

我会尝试这样的事情：

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;
}

没有重载（仅更改检查）并且它可以用于矩阵（不依赖于交换性，仅依赖于关联性）。