Оптимизация логических выражений

Особенность оптимизации логических выражений заключается в том, что не всегда необходимо полностью выполнять вычисление всего выражения для того, чтобы знать его результат. Иногда по результату первой операции или даже по значению одного операнда можно заранее определить результат вычисления все­го выражения.

Операция называется предопределенной для некоторого значения операнда, если ее результат зависит только от этого операнда и остается неизменным (инвари­антным) относительно значений других операндов.

Операция логического сложения (or) является предопределенной для логиче­ского значения «истина» (true), а операция логического умножения — предопре­делена для логического значения «ложь» (false).

Эти факты могут быть использованы для оптимизации логических выражений. Действительно, получив значение «истина» в последовательности логических сло­жений или значение «ложь» в последовательности логических умножений* нет никакой необходимости далее производить вычисления — результат уже опреде­лен и известен.

Например, выражение А ог В or С or D не имеет смысла вычислять, если извест­но, что значение переменной А есть True («истина»).

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

Не всегда такие преобразования инвариантны к смыслу программы. Например, при вычислении выражения A or F(B) or G(C) функции F и G не будут вызваны и выполнены, если значением переменной А является true. Это не важно, если ре­зультатом этих функций является только возвращаемое ими значение, но если они обладают «побочным эффектом», то семантика программы может измениться.

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