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

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

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

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

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

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

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

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

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

Оптимизация циклов

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

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

Для оптимизации циклов используются следующие методы:

- вынесение инвариантных вычислений из циклов;

- замена операций с индуктивными переменными;

- слияние и развертывание циклов.

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

Например, цикл

for i:=l to 10 do

begin

A[i] := В * С * A[i]:

end;

может быть заменен на последовательность операций

D := В * С;

for i:=l to 10 do

begin

A[1] := D * A[i];

end;

если значения В и С не изменяются нигде в теле цикла.

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

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

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

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

Например, цикл

S := 10;

for i:=l to N do A[i] :=i*S;

может быть заменен на последовательность операций

S := 10;

T := S; i := 1;

While I<=10 do

Begin

A[i] := T;

T := T+10;

i := i +1;

End;

В другом примере

s:=10;

for i:=l to n do

begin

R := R + F(S);

S := S + 10;

end.

две индуктивных переменных — i и S. Если заменить их на одну, то выяснится, что переменная i вовсе не имеет смысла, тогда этот цикл можно заменить на по­следовательность операций

S := 10;

М := 10 + N*10;

while S <= М do

begin

R := R + F(S);

S :- S + 10;

end.

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

Слияние двух циклов можно проиллюстрировать на примере циклов.

for i:=l to N do

for j:=l to M do A[i,j] :=0;

Здесь происходит инициализация двумерного массива. Но в объектном коде
двумерный массив — это всего лишь область памяти размером N*M, поэтому
эту операцию можно представить так:

К :=N*M;

for i:=l to К do A[i] := 0;

Развертывание циклов можно выполнить для циклов, кратность выполнения ко­торых известна уже на этапе компиляции. Тогда цикл, кратностью N, можно заменить на линейную последовательность N операций, содержащих тело цикла.

Например, цикл

for 1:=1 to 3 do A[i] := i;

можно заменить операциями:

A[1] := 1;

A[2] := 2;

A[3] := 3;