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

Поэтому уделяйте основное внимание циклам. Разберем пример:

Рассмотрим вначале цикл С. Любая экономия, даже самая малая, будет здесь увеличиваться в 100ХЮ0ХЮ0= 1 000 000 раз, т. е. коэффициент улучшения равен одному миллиону. Очень малое улучшение внутри цикла С гораздо выгоднее, чем значительное улучшение вне его. Затем рассмотрите цикл В и, наконец, цикл А.

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

Повторяющиеся вычисления в циклах являются наиболее типич-выми ошибками, влияющими на эффективность. В примере

У* Ъ будет вычисляться каждый раз при выполнении цикла, который может повторяться тысячекратно. Вместо этого программа должна вычислять У Ъ вне цикла, т. е.

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

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

Оптимизируйте сначала внутренние циклы.

В нижеследующем примере повторяющихся вычислений используется обозначение для части вычислений:

ПЛЦ:

DO I = 1 ТО 10;

DO J = 1 ТО 10;

A(I, J)=B(I, J) + D/I + D/K;

END; END;

Выражения D/K и D/I являются повторяющимися вычислениями и их следует исключить из внутреннего цикла. Например,

ПЛЦ:

DK = D/K;

DO I = 1 ТОЮ;

DI = D/I;

DO J = 1 ТО 10;

A(I, J)=B(I, J) + DI + DK;

END; END;

Здесь D/K вычисляется один раз вместо 100, вычисление D/I —десять раз вместо 100. Операция пересылки заменяет операцию деления. Пересылка обычно дешевле, чем арифметические операции. Однако здесь имеется еще одно выражение, которое можно удалить из цикла. Можете ли вы найти его?

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

ФОРТРАН:

DO 12 1 = 1,1000 А(1) = 0.0 12 CONTINUE

Улучшение, сделанное следующим образом: ФОРТРАН:

DO 12 1= 1,1000,2 А(1) = 0.0 А(1+1) =0.0 12 CONTINUE сокращает наполовину количество выполняемых операций приращения и завершения цикла. Заметим, что полученная программа требует большего объема памяти. Такое преобразование цикла называется его разверткой.

Часто циклы можно объединять. Поясним на примере:

ПЛ/1:

DO I = 1 ТО 500;

Х(1) — 0.0; END;

DO I — 1 ТО 500;

Y(I) = 0.0; END;

Очевидный способ сокращения как времени, так и памяти состоит в следующем:

DO I = 1 ТО 500;

Х(1) — 0.0;

Y(I)=0.0; END;

Он называется сжатием или объединением циклов. Сжатие цикла сокращает накладные расходы цикла и требуемый размер памяти.

Последний пример оптимизации цикла, который противоположен сжатию цикла:

АЛГОЛ W:

FOR I : — 1 UNTIL 100 DO

IF (T) THEN X(I) := A(I) + B(I) ELSE X(I) := A(I) — B(I);

Здесь оператор IF должен выполняться в каждой итерации 100 раз, хотя логическая переменная Т не изменяется внутри цикла. Более эффективный способ состоит в следующем:

АЛГОЛ W:

IF (Т) THEN

FOR I : = 1 UNTIL 100 DO X(I) :=A(I)+B(I)

ELSE

FOR I :=* 1 UNTIL 100 DO X(I) :=A(I)-B(I);

Теперь оператор IF выполняется только один раз. Этот процесс называется разъединением. Время выполнения здесь уменьшается за счет расхода памяти.