Главная Теоретический материал Лабораторные работы Задачи Тесты Контакты

Узбекское Агентство
Связи и Информатизации



Ташкентский Университет Информационных Технологий


Кафедра
«Программное обеспечение информационных технологий»

Направления:

5521900Информатика и
информационные технологии,
5523500Защита информации,
5523600Электронная коммерция,
5811200Сервис (информационный сервис),
5811300Сервис (электронные и
компьютерные технологии),
5320200Информатика и
библиотековедение,
5140900Профессиональное образование
(по направлению
информатика и
информационные технологии).


Преподаватель дисциплины



Доцент
Чернев Дмитрий Алексеевич

Оптимизация программы.

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

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

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

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

Существуют два подхода к оптимизации программ: «чистка» и перепрограммирование. Оба подхода имеют как достоинства, так и недостатки.

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

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

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

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

Рассмотрим основные Машинно-независимые приемы опти­мизации программ.

1)   Заголовки сообщений. Если большая часть сообщений со­держит пробелы (или другие повторяющиеся символы), то для экономии памяти ЭВМ следует использовать команды, выпол­няющие заполнение этой части сообщения пробелами (сим-волами).

2)   Инициирование переменных. Если начальные значения прис­ваиваются переменным (или константам) одновременно с их
объяв­­­­ле­нием, то экономится и память, и время выполнения
программы, т.к. в этом случае переменные получают начальные
значения во время компилирования программы, а не во время ее
выполнения.

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

3)   Уменьшение числа переменных. Отработанная «временная»
переменная на участке программы (например, управляющая
переменная цикла) продолжает занимать область памяти и
дальше во все время выполнения оставшейся части программы.
Ее надо удалить (очистить).

Но ее можно использовать в программе и дальше вместо другой «временной» переменной ( например, в качестве управляющей пере-менной в другом цикле) в другом качестве, чтобы не создавать новую. При этом тип переменной остается неизменной.

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

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

Рост числа временных и неиспользованных переменных обыч­но происходит у начинающих и неаккуратных программистов. Их типичная ошибка — выбор первой пришедшей в голову структуры данных. Считается хорошим стилем программирования, если в программе нет лишних переменных.

4)  Выбор типов данных. Переменные разных типов данных в
ЭВМ обрабатываются с разной затратой времени и памяти. В
данном случае требуется минимальное понимание особенностей
программы.

Например, если элемент массива А(1) — целочисленная, то в операторе FOR I:=l ТО 1000 DO A(I):= 0.0; произойдут 1000 преобразований типов из вещественного в целый. Здесь надо написать: А(1):= 0;.

5)  Удаление излишних операторов присваивания. Рассматри­ваемая процедура состоит в удалении из программы некоторых
операторов присваивания и замене в некоторых других операторах
(присваивания или условного перехода) переменных, являющихся левой частью удаляемых операторов, выражениями, яв­ляющимися правой частью удаляемых операторов, то есть выполняется объединение операторов.       Например, следующие четыре оператора присваивания

С1:= 5. + B1*D**2;

С2:= В+ SIN (R);

С3:= 5.+ А(1)*А(2);

С:= (С1 + С2)*СЗ;

можно заменить одним

С: = (5 + B1*D**2 + В + SIN(R))*(5 + А(1)*А (2));

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

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

6)  Отождествление переменных. Если в программе имеется
оператор вида А:=В, то во всех последующих операторах прог­раммы можно заменить переменную А переменной В или чис­ловым значением переменной В, а оператор А: = В удалить.

Если переменная А является индексируемой переменной, то оператор А: = В остается в программе, а переменная А в неко­торых операторах заменяется переменной В.

7)    Удаление тождественных операторов. Суть этой процедуры
состоит в удалении из программы тождественных операторов, т.е.
операторов вида А: = А. Такие операторы могут появляться в
программе в результате выполнения оптимизационных и других
преобразований.

8)    Устранение невыполняемых операторов. В реальных прог­раммах могут встретиться участки, содержащие невыполняемые операторы, т. е. такие операторы, которые не выполняются при любых наборах начальных данных.

Появление таких операторов можно объяснить двумя при­чинами:

1)     в. процессе отладки программы или ее модификации программист либо забывает о таких операторах, либо не хочет их искать, либо просто не в состоянии проследить за всеми пос­ледствиями, вызванными исправлениями некоторых участков программы;

2)     большая логическая или информационная сложность программы не позволяет программисту «увидеть» такие опе-раторы или даже целые невыполняемые участки программы.

Смысл рассматриваемой процедуры состоит в удалении из программы невыполняемых операторов.

9)   Использования ввода-вывода.Операции ввода-вывода зани­мают много времени и должны быть сокращены до минимума. Данные, которые можно вычислить внутри программы, вводить не надо!

Две последовательные команды ввода-вывода для одного и того же устройства можно объединить в одну команду. Это сокращает количество обращений к системным подпрограммам ввода-вывода, что, естественно, сокращает время выполнения программы.

Не забудьте после отладки программы изъять все лишние (обычно отладочные) операторы ввода-вывода.

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

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

Лучше все же использовать не процедуры, а отдельные мо- дули.

11)  Сокращение числа процедур (функций).Связь процедур
(функций) с основной программой обеспечивается операторами
вызова в основной программе, которые замедляют работу прог-раммы.

Когда критерием оптимизации является время счета прог-раммы, то нужно хорошо подумать прежде, чем выделить участок программы в отдельную процедуру (функцию).

Если много операторов выполняются много раз и в разных местах программы, то, конечно, их надо выделить в отдельную процедуру. Но неразумно вызывать небольшую процедуру два (три ...?) раза.

Сокращение числа процедур (функций) выполняется заменой операторов их вызова телами этих процедур (функций) и заменой

формальных параметров соответствующими им фактическими парамет-рами. Зато увеличивается текст программы на соот­ветствующее число команд.

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

12) Альтернативы.Когда одну переменную нужно сравнить с несколькими значениями, некоторые программисты пишут так (очень плохой стиль программирования):

IFA= 1THEN... ;

IFA=2THEN... ;

IFA= 3THEN... ;

В этом случае, даже если А = 1, будут выполнены все условные операторы IF.

При использовании конструкции ELSE сравнение будет прекращено, как только будет найдено истинное условие:

   IF A=1 THEN...

             ELSE IF A=2         THEN...

                          ELSE IF A=3 THEN...;

Дальнейшее улучшение эффективности по времени (оно может привести к ухудшению удобочитаемости программы) состоит в том, чтобы расположить на первом месте условие, которое по всей вероятности, является истинным в первую очередь (имеет наибольшую вероятность быть истинным), затем остальные условия -в порядке убывания их вероятности быть истинными.

То же замечание касается конструкции выбора (CASE).

13) Арифметические операции.Арифметические операции выполняются с разной скоростью.

Перечислим их в порядке возрастания времени их выпол­- нения:

1)    сложение и вычитание;

2)    умножение;

3)    деление;

4)    возведение в степень.

Иногда бывает целесообразно заменить одну операцию другой. Например, 3*1 может быть заменено I+I+I или Х**2 можно заменить на Х*Х. Тем более, что для возведения в степень обычно требуется библиотечная программа.

Замена возведения в степень несколькими операциями ум- ножения экономит и память, и время, если показатель степени является небольшим целым числом.

Умножение выполняется почти в два раза быстрее деления.

Вместо А/5 можно написать 0.2*А;

Вместо А1 = B/D/E + С можно написать А1 = B/(D*E) + С;

SQRT(A); выполняется быстрее и точнее, чем А**0.5;

14) Преобразование выражений. Предварительное преобра­зование (упрощение) выражений может привести к исключению многих арифметических операций.

Например, X: = 2*У + 2*Т; можно заменить на X: = 2*(У + Т);

Последнее преобразование исключило одну операцию ум­ножения.

15) Оптимизация выражений.Суть процедуры состоит в замене всех сложных семантически эквивалентных подвыражений на одно простое.

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

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

16)  Предварительное вычисление арифметических подвыра­жений. Вместо, например:

А: = (M*B*C)/(D-E);

К: = D-E-B*C*M;

можно написать:

Т: = N*B*C;

U: = D-E;

А: = T/U;

К: = U-T;

Сокращается текст программы и время ее выполнения за счет сокращения количества выполняемых операций. Зато быть может чуть-чуть увеличивается память для Т и U.

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

18) Устранение лишних меток. По ряду причин в программах встречаются метки перед операторами, на которые нет передач управления.

Такие метки являются лишними и их следует удалить из программы.

19)   Устранение лишних операторов перехода.После многих опти-мизационных переделок программы, в ней могут появиться операторы безусловного перехода (GO TO), которые передают управление оператору с несуществующей меткой. Их надо удалить.

20)  Неявные операции.Операция Т:= М(1) требует в 1,5—2 раза больше времени и памяти, чем Т: = А;, а если М — параметр или функция, то в 2,5—3 раза больше.  Там, где часто используется М(1), можно использовать прос­тую  переменную MI: = M(I) и т. д.

Но если индекс I — константа, то индексация выполняться не будет: при трансляции вычисляется сдвиг элемента относи­тельно начала массива, и в процессе выполнения программы он обрабатывается как простая  переменная.

21)  Чистка циклов.Немного о памяти. Обычно программисты
не заботятся о памяти до тех пор, пока не превысят ее размеры.
Тогда становится очевидным, что память не безразмерна. Име-ются  прогнозы, что скоро будем располагать достаточной памятью для решения любой задачи. Но размеры решаемых задач также растут по мере  увеличения размера памяти ЭВМ.

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

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

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

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

FOR I: = 1 ТО 100 DO FOR J: = 1 ТО 10 DO X: = Y*Z + C[I, J];

Здесь Y*Z будет вычисляться тысяча раз, а в следующем примере — только один раз:

YZ: = Y*Z;

FOR I: = 1 ТО 100 DO FOR J: = 1 TO 10 DO X: = YZ + C[I, J];

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

Интересной разновидностью чистки циклов является изме­нение порядка циклов:

Цикл                                    FOR I: = 1 ТО N DO FOR J: = 1 ТО М DO...

при N < М выполняется быстрее, чем цикл

FOR I: = 1 ТО М DO FOR I: = 1 ТО N DO...

т.к. в первом случае выполняется M*N + N операций орга­низации циклирования, а во втором — M*N + М.

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

Иногда бывает полезным отказаться от использования циклов.

Не многократно повторяющиеся последовательности опера­торов, требующие сложной организации циклов, часто можно писать в программе последовательно (линейно), а не итеративно.

23)  Объединение циклов. При трансляции любого цикла с языка высокого уровня в машинные коды в объектной программе появляются операции, реализующие заголовок цикла, т. е. увели-чение управляющей переменной цикла на значение его шага; сравнение управляющей переменной с граничным значением; передачу управления.

Процедура объединения циклов производит соединение нес­кольких циклов с одинаковыми заголовками в один. Например:

FOR I: = 1 ТО 500 DO X[I]: = 0;

FOR J: = 1 ТО 500 DO Y[J]: = 0;

можно объединить в один цикл, что сокращает как время выполнения программы, так и память:

FOR I: = 1 ТО 500 DO BEGIN X[I]: = 0; У[1]: = 0 END;

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

FOR I = 1 ТО 200 DO

   IF К = 2 THEN A(I) = B(I)*C(I) ELSE A (I) = В (I) + 2;

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

IF К = 2 THEN FOR 1=1 ТО 200 DO A(I) = B(I)*C(I);

ELSE  FOR 1=1 TO 200 DO A (I) = В (I) + 2...

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

25) Удаление пустых циклов.Суть этой процедуры состоит в
удалении из программы пустых циклов.

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

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

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

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

FOR I = А ТО В DO IF I<= С THEN R(I) = P(I);

Процедура сжатия циклов осуществляет перенос таких огра­ничений в заголовок цикла:

DO I = А ТО С DO R(I) - P(I);

Здесь предполагается, что А <: С < В.

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

27) Управление по выбору. В операторе выбора выполняется первая группа команд, у которой условие выбора истинно.

Поэтому для увеличения скорости выполнения программы необходимо располагать группы команд в операторе выбора в порядке убывания частоты вероятности их использования.

Иными словами, в операторе выбора необходимо первой расположить группу команд, которая наиболее часто должна быть выполнена. Второй — следующую по частоте выполнения группу команд. И так далее. Группа команд, которая выполняется крайне редко, в операторе должна располагаться последней.


Назад


Главная Теоретический материал Лабораторные работы Тесты Контакты