Программирование арифметических операций

Практическая работа

Тема: Оптимизация программ.

Ход работы

I. Изучите краткий теоретический материал

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

Программирование арифметических операций.

Немалые резервы повышения скорости работы программы заключены в правильном программировании арифметических и логических выражений. Различные арифметические операции значительно различаются по быстродействию. Самыми быстрыми являются операции сложения и вычитания. Более медленным является умножение, затем идет деление. Программируя арифметические выражения, следует выбирать такую форму их записи, чтобы количество «медленных» операций было сведено к минимуму. Пусть необходимо вычислить многочлен 4-ой степени:

В этом выражении содержится 10 умножений и 4 сложения. Это же выражение можно записать в виде . Такая форма записи называется схемой Горнера. В этом выражении 4 умножения и 4 сложения. Общее количество операций сократилось почти в 2 раза.

Циклы

Различается и время исполнения циклов различных типов. Время выполнения цикла со счетчиком и цикла с постусловием при всех прочих равных условиях совпадает, цикл с предусловием выполняется дольшае на 20-30%. При использовании вложенных циклов следует иметь в виду, что затраты процессорного времени на обработку такой конструкции могут зависеть от порядка следования вложенных циклов. Рассмотрим, например, такой вложенный цикл со счетчиком.

for j:=1 to 100000 do

for k:=1 to 1000 do a:=1;

Этот цикл выполняется примерно на 10% дольше, чем слудующий:

for j:=1 to 1000 do

for k:=1 to 100000 do a:=1;

На первый взгляд, и в первом и во втором случае 10 000 000 раз выполняетсяоператора присваивания, и затраты времени на это должны быть одинаковы в ооих случаях. Но это не так. Инициализация цикла, то есть обработка процессором его заголовка с целью определения начального и конечного значени счетчика, а также шага приращения счетчика требует времени. В первом случае 1 раз инициируется внешний цикл и 100 000 раз внутренний, то есть всего выполняется 100 001 инициализация. Во втором случае таких инициализаций окаозывается лишь 1001.

Аналогично ведут себя вложенные циклы с предусловием и постусловием. При прогаммировании вложенных циклов по возможности следует делать цикл с наибольшим числом повторений самым внутренним, а цикл с наименьшим числом повторений-самым внешним.

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

Summa:=0;

For i:=1 to 1000 do summa:=summa+a*x[1];

Очевидно, что другая форма записи этого цикла оказыается более экономной:

Summa:=0;

For i:=1 to 1000 do summa:=summa+x[1];

summa:=a*summa;

Эта запись содержит всего одно умножение при том же числе сложений против 1000 умножений в первом случае.

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

В Турбо Паскале выполняется несколько типов оптимизации кода компилируемой программы с целью повышения её быстродействия и уменьшения объёма занимаемой памяти.

Свёртывание констант. Если операндами выражения являются константы ординального типа, то выражение вычисляется в период компиляции. То же относится к функциям abs, sqr, succ, pred, odd, lo, hi, swap, если их аргументами являются константы ординального типа.

Var k: integer;

Begin

k:=abs(-15)+sqr(7)-6*12;

Для выполняемой программы записанный в исходном тексте оператор будет заменён оператором k:= -23;
Если индексом массива является константа или выражение, состоящее из констант, то адрес элемента массива вычисляется во время компиляции. Например, доступ к элементам a[sqr(7)+2,3*8] и a[61,24] будет таким же эффективным, как и доступ к простой переменной.

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

Writeln('Введите значение ','x =');

................................

Writeln('Введите значение ','y =');

................................

Writeln('Введите значение ','z =')

................................

Для объектного кода программы это эквивалентно фрагменту

Const S = 'Введите значение ';

Begin

Writeln(S,'x =');

................

Writeln(S,'y =');

................

Writeln(S,'z =');

................

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

If (x>0) and (x<100) and (y>1) and (y<x) then...

While (x<0) or (y>1) or (z>x+y) do...

Если x = -1, то вычисление обоих логических выражений прекращается после вычисления значения истинности первого операнда. В первом случае имеем для всего выражения значение false, во втором - значение true.

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

If false then y:=sqr(x)+1;

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

Пример 4.

Const KeyPrint = 0; { Ключ тестовой печати: }

{ 0 - тестовая печать отсутствует; }

Begin { 1 - активизируется тестовая печать }

...............................

If KeyPrint>0 then

Begin

Печать массива A

End;

................................

Операторы отладочной печати включаются в объектный код программы, если до её компиляции было установлено значение константы KeyPrint = 1.

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

Uses Graph;

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

Контрольные вопросы

1. С чем связана необходимость оптимизации программ? Приведите пример.
2. Как можно уменьшить время работы программы, оптимизировав вычисление арифметических операций?
3. Как можно уменьшить время работы программы, оптимизировав организацию циклов?
4. Как осуществляется оптимизация программного кода компилятором путем свертывания констант?
5. Как осуществляется оптимизация программного кода компилятором путем слияния констант?
6. Как осуществляется оптимизация программного кода компилятором путем вычисления по коротной схеме?
7. Как осуществляется оптимизация программного кода компилятором путем удаления неиспользуемого кода?
8. Как осуществляется оптимизация программного кода компилятором путем эффективной компоновки?