Оптимизация умножения переменных

Question

[Это было изначально на матрицах, но я думаю, что это применимо к любой переменной в общем]

Скажем, у нас есть Var1 * Var2 * Var3 * Var4.

Один из них время от времени изменяется, причем один из них является случайным.

Можно ли минимизировать умножения?

Если я сделаю

In case Var1 changes: newVar1 * savedVar2Var3Var4

Я заметил, что тогда мне нужно пересчитывать сохраненные значения Var2Var3Var4 каждый раз при изменении Var2, Var3, Var4.

Будет ли этот пересчет «сохраненных комбинаций» не соответствовать цели?

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

Затем на каждом уровне (ну, может быть, только на нескольких верхних уровнях) у вас может быть запомненный подответ, а также некоторые данные, чтобы сообщить вам, если переменные ниже негоизменился.Если события приходят, чтобы сказать вам, чтобы изменить переменную, то это может привести к распространению недействительности выражения вверх при получении события (или просто пересчитать запомненные подответы для каждого события).Если переменные просто волшебным образом изменяются, и вы должны изучить их, чтобы сказать, что они изменились, тогда у вас есть больше работы.

О, другой способ сделать это просто появился у меня в голове, и мне стыдно, чтоЯ не думал об этом раньше.Если вы знаете старые и новые значения переменной, которая изменилась тогда, если старое значение не было 0, вы могли бы просто:

new_answer =  (old_answer * new_var) / old_var;

В реальной математике это будет работать, но в компьютерематематика это может потерять слишком много точности для ваших целей.

Answer 2

Во-первых, подобные микрооптимизации практически никогда не стоят того. Время вашей программе, чтобы увидеть, есть ли проблемы с производительностью, профиль, чтобы увидеть, где проблема, и проверить после внесения изменений, чтобы увидеть, сделали ли вы вещи лучше или хуже.

Во-вторых, умножение чисел, как правило, быстрое в современных процессорах, тогда как филиалы могут быть более дорогими.

В-третьих, как вы его настраиваете, если Var1 изменится, вам потребуется пересчитать savedVar1Var2Var3, saved Var1Var2Var4, saved Var1Var3Var4 и весь продукт. Очевидно, что вам лучше просто пересчитать сумму.

Answer 3

Да, это возможно.

Для скаляров, вероятно, не будет никакой пользы. Для большой математической матрицы вы можете вычислить и сохранить: Var1 * Var2 и Var3 * Var4. Ваш результат является продуктом этих двух вещей. Теперь, когда один из них изменяется, вам нужно обновить только 2 продукта вместо 3. Обновите только один из 2 сохраненных продуктов в зависимости от того, кто из них изменился, и обновите результат.

Вот оно, 2 умножения вместо 3 с каждым обновлением. Это принесет вам пользу только в том случае, если на самом деле общий случай - это обновление только одного из них, но если это правда, это должно очень помочь.

Answer 4

Ответ зависит от того, как часто меняются значения. В вашем примере вычисление SavedVar2Var3Var4 обходится вам в два умножения, с одним дополнительным умножением каждый раз, когда изменяется Var1 (или вам необходимо вычислить итоговое значение) Итак: сколько раз изменяются Var2, Var3, Var4 по сравнению с Var1?

Если Var1 изменяется более чем в 3 раза чаще, чем остальные, стоит пересчитать saveVar2Var3Var4 по мере необходимости.

Answer 5

Я не думаю, что вы экономите время.Каждый раз, когда изменяется одна из N переменных, вам нужно рассчитать (N - 1) дополнительных продуктов, верно?Допустим, у вас есть изменения A, B, C и D. A, и вы сохранили продукт B, C и D, но теперь вы должны пересчитать кэшированные продукты ABC, ABD и ACD.Вы на самом деле делаете дополнительную работу.A B C D - это три операции умножения, а A BCD, A B C, A C D и A B D работает до СЕМЬ.

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 += (C-C');

Та же идея для продукта: Product *= 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;
}

Перегрузка отсутствует (только проверка изменений), и ее можно использовать для матриц (не зависит от коммутативности, только от ассоциативности).