![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Оптимизация циклов
Большая часть процессорного времени в программах приходится на выполнение циклов, и здесь может достигаться самый значительный выигрыш от оптимизации. Например, при выполнении цикла на Фортране 77 (считается наиболее мощным языком для вычислительных задач) DO 1 I = M, N, L .......... Тело цикла .......... 1 CONTINUE, как правило, производятся следующие шаги:
1. вычисление числа повторений K=(N-M+L)/L; 2. проверка его на нуль и если необходимо, то переход на шаг 3; 3. вычисление и запоминание значения управляющей переменной I; 4. выполнение тела цикла; 5. уменьшение счетчика повторений К=К-1 и приращение управляющей переменной I=I+L; 6. проверка на окончание цикла К=0 (и если требуется, переход на шаг 3).
Видно, что шаги с 1 по 3 составляют затраты на инициализацию цикла, а шаги 5 и 6 - затраты на завершение цикла. При этом шаги с 3 по 6 циклически повторяются. Поэтому иногда издержки на организацию цикла сравнимы с затратами на выполнение тела цикла или больше. Примеры на Паскале – слева неоптимизированные, справа – оптимизированные. Правило 1. Не следует использовать короткие циклы. Например, цикл For I: =1 to 2 do A[I]: =0; лучше заменить на два оператора присваивания A[1]: =0; A[2]: =0;
Правило 2. Следует предусматривать (если это возможно) такую вложенность циклов, при которой циклы с наибольшим числом повторений были внутренними.
For I: =1 to 100 do Число инициализаций = 1 begin For J: =1 to 10 do 100 begin For K: =1 to 2 do 1000 begin ..... Всего = 1101 ..... end Число проверок на окончание = 2000 end 1000 end 100 Всего = 3100
Пример обратного вложения. Таким образом, полное число инициализаций циклов уменьшено с 1101 до 23, а число проверок на окончание циклов с 3100 до 2022, если указанные три цикла организовать в обратном порядке
Правило 3. Уменьшения времени на операции, не связанные с выполнением тела цикла, можно добиться путем развертки или объединения циклов. Под разверткой цикла понимают увеличение шага цикла или удаление короткого внешнего цикла. Например: - увеличение шага цикла DO 1 I = I, N DO 1 I= 2, N, 2 A(I)= B(I) * C(I) A(I-1) = B(I-1) * C(I-1) 1 CONTINUE A(I) =B(I) * C(I) 1 CONTINUE
- отказ от короткого внешнего цикла For i: =1 to 3 do For j: =1 to n do begin For j: =1 to n do x[1, j]: =y[1, j]+z[1, j]; x[i, j]: =y[i, j]+z[i, j]; x[2, j]: =y[2, j]+z[2, j]; x[3, j]: =y[3, j]+z[3, j]; end; - объединение циклов For j: =1 to n do For i: =1 to n do begin a[j]: =j*5; a[i]: =i*5; For i: =1 to n do b[i]: =k[i]*3-6 b[i]: =k[i]*3-6; end;
Как видно из приведенных выше примеров, путем развертки или объединения циклов, можно значительно уменьшить число повторений тела цикла и тем самым сократить накладные расходы.
|