Правило 4.

Большего эффекта можно добиться путем оптимизации тела цикла. К процедурам оптимизации тела цикла относятся чистка цикла и вынос ветвлений из цикла.

Чистка цикла - это вынос из тела цикла операций, не зависящих от переменной цикла. Классическим примером чистки цикла является программа, вычисляющая следующую сумму:

S = X*Аt,

sum:=0; sum:=0;

for i:=1 to n do for i:=1 to n do

sum:=sum+x*A[i]; sum:=sum+A[i]

sum:=x*sum;

В данном примере вынос из цикла одного умножения сэкономит N-1 умножение. Спедующим примером чистки цикла является программа, вычисляющая сумму

S = (L - 1)

sum:=0; sum:=0;

for i:=1 to n do for i:=1 to n do

sum:=sum+L[i]-1; sum:=sum+L[i];

sum:=sum-n;

В данном случае удается сэкономить N-1 вычитание.

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

верки этого условия из цикла исходный цикл заменяется двумя циклами, соответствующими двум частям исходного:

Пример 1.

for i:=1 to 20 do if k=2 then

if k=2 then for i:=1 to 20 do

a[i]:=b[i]+2 a[i]:=b[i]+2

else else

a[i]:=b[i]*c[i]; for i:=1 to 20 do

a[i]:=b[i]*c[i];

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

Пример 2.

Здесь вычисляется значение некоторой функции, которое в зависимости от условия заносится то в один, то в другой массив. Напрашивается вопрос: а почему не вынести общий член за операторные скобки begin - end, точно так же, как в математике выносятся за скобки общие множители:

end;

Исходный код стал более компактным, более понятным и меньшим по размеру. К тому же, вместо простого выражения y:=f(x) здесь может использоваться любое количество операторов. При изменении кода в первом случае нужно не забывать вносить изменения в оба места, что может привести к ошибкам.

Задание. Если проанализировать следующий фрагмент программы, окажется то, что проверка условия x < 0 в цикле вообще лишняя.

for i:=1 to N do

begin

x[i]:=sqr(a[i]);

y[i]:=-b[i]+x[i];

if x[i]>=0 then

z[i]:=x[i];

end

Таким образом, основными процедурами по оптимизации циклов являются:

- чистка циклов, т.е. удаление из тела цикла операций, не зависящих от переменной цикла;

- объединение циклов;

- вынос ветвлений из циклов;

- увеличение шага изменения управляющей переменной цикла;

- удаление коротких циклов;

- оптимальное вложение циклов.