Реферат на тему:

Ефективність програм та методи оптимізації.

План

1. Що таке ефективність та вартість оптимізації.

2.Вибір алгоритму.

3. Зниження потужності виразів.

4. Видалення надмірних операцій.

5. Використання констант та ініціалізація змінних.

6. Логічні вирази.

7. Індексація.

8. Оптимізація циклів.

9.Видалення надмірних операцій

10. Порядок вкладання циклів

11. Розгортка циклів

12. Об’єднання циклів

13. Роз’єднання циклів

Література

1. Що таке ефективність та вартість оптимізації.

Перш за все, домовимось про термінологію. Ефективність – це степінь
сумірності результатів з витратами. Оптимізація – це покращення
характеристик програмної системи або просто програми. Тобто швидкоруч
написана програма, яка довго, хоч і правильно працює, очевидно,
неефективна. Вона підлягає оптимізації. З іншого боку, ефективна
програма нікому не потрібна, якщо вона не забезпечує правильних
результатів.

Отже, перший етап програмування – створення правильної програми, і лише
другий – її оптимізація. Але перед тим, як починати покращувати
ефективність програми, слід перевірити, наскільки це покращення буде
корисним, і точно визначити місце, яке слід переробити.

Справа у тому, що існує правило 20/80: 20% об’єктного коду (тексту
програми) виконується 80% часу роботи всієї програми. Деякі програми
наукових обчислень дають навіть співвідношення 3/90.

Ця невелика частина програми, виконання якої займає більшу частину часу
роботи програми, називається критичною областю. Саме критичну область і
слід оптимізувати.

У вартості процеса програмування переважну частину складає вартість
людської праці, тому при визначенні можливого покращення треба оцінювати
обсяг роботи, необхідної для досягнення цього покращення. Наприклад, для
кожної підпрограми можна обчислити коефіцієнт

k = (% часу роботи * % покращення) / (необхідні зусилля),

і підпрограма з найвищим значенням коефіцієту k – першочерговий
претендент на оптимізацію (якщо мало часу або немає потреби переробляти
всю програму).

Існують два підходи до оптимізації програм: “чистка” – виправлення
очевидних неохайностей і перепрограмування – заміна алгоритму на більш
швидкий (наприклад, сортування зі складністю O(n2) замінити сортуванням
зі складністю O(n ln n)).

Багато засобів, які підвищують ефективність програми, не погіршують її
зручність для читання, отже, мають використовуватись завжди. В усіх
інших випадках слід дотримуватись правила: зручність для читання
програми важливіша за її ефективність.

2.Вибір алгоритму.

Найбільш важливим фактором у прискоренні роботи програми є вибір
алгоритму або структури даних – між ефективним алгоритмом та
неефективним може бути величезна різниця. Невелика ілюстрація до
сказаного – наступний приклад, де за рахунок введення додаткової змінної
вдається позбавитись від n перевірок в тілі циклу.

for i := 1 to n do

if (i mod 2) = 0 then

S := S + f(i)

else

S := S – f(i);

Тут перевірка умови (i mod 2) = 0 виконується на кожному кроці. Введемо
зайву змінну, яка позбавить від перевірки умови.

mult := -1;

for i := 1 to n do

begin

S := S + mult*f(i);

mult := –mult;

end;

3. Зниження потужності виразів.

Цей термін означає такий вид оптимізації, коли більш дорога операція (в
сенсі часу виконання) заміняється на більш дешеву. Колись це означало в
першу чергу заміну множень додаваннями або зсувами. Для сучасних
процесорів тепер це майже нічого не покращує, оскільки множення
виконується практично так само швидко, як і додавання. Але ділення та
взяття залишку від ділення виконуються суттєво (приблизно в 10 разів)
повільніше за множення, отже, код програми значно покращиться, якщо
ділення замінити множенням на обернену величину, а взяття залишку при
діленні на степені двійки – замінити використанням бітової маски. Отже,

a)

(* гірший варіант *)

y := 1/(x*x) + cos (2/x);

(* кращий варіант *)

x1 := 1/x;

y := x1*x1 + cos (2*x1);

б) A/2 краще замінити на A*0.5;

в) A/B/C/D краще замінити на A/(B*C*D);

г) y = ax3 + bx2 + cx + d = a*x*x*x + b*x*x + c*x + d

краще замінити на y = ((a*x + b)*x + c)*x + d.

Заміна повільних операцій швидкими якраз і називається зниженням
потужності операцій. В деяких випадках успіху можна досягти за допомогою
стандартних функцій:

a) A4 краще обчислювати як sqr(sqr(A));

б) 4?A краще обчислювати як sqrt(sqrt(A)), і т.д.

Крім того, якщо ідеальна точність обчислень не вимагається, в програмі
краще використовувати типи даних з низькою точністю. Наприклад, не
користуйтесь типом подвоєної точності без необхідності, оскільки
арифметичні операції над виразами такого типу, як правило, виконуються
значно повільніше.

4. Видалення надмірних операцій.

Якщо деяке складне обчислення зустрічається в вашій програмі декілька
разів, виконайте його один раз, запам’ятавши результат, наприклад:

y = 3 sin2? + 2 sin? +sin4? краще запрограмувати так:

sn := sin (alpha);

y := 3*sqr(sn) + 2*sn + sqr(sqr(sn));

(звичайно, цей запис можна удосконалювати далі).

5. Використання констант та ініціалізація змінних.

Якщо початкові значення надаються змінним одночасно з їх визначенням,
відбувається економія часу виконання програми, тому що змінні таким
чином ініціалізуються не під час виконання програми, а під час
компіляції. Наприклад, визначення в програмі мовою С виду int i = 0;
більш ефективне ніж

int i;

i = 0;

Подібного результату в програмі мовою Паскаль можна досягти за рахунок
типізованої константи:

const i : integer = 0;

Така константа рівнозначна змінній з попередньо ініціалізованим
значенням.

6. Логічні вирази.

Економії часу можна добитись правильним розташуванням складних логічних
виразів. Більшість компіляторів зупиняють подальше обчислення виразу,
якщо його результат вже відомий. Наприклад, логічний вираз ( A and B
and C and D ) матиме значення false , як тільки один із операндів матиме
значення false. Отже, треба розташовувати логічні операнди таким чином,
щоб на початку виразу послідовних логічних множень знаходився операнд,
який найчастіше має значення “хибність”.

Логічний вираз ( A or B or C and D ) матиме значення true , як тільки
один із операндів матиме значення true. Отже, треба розташовувати
логічні операнди таким чином, щоб на початку виразу послідовних логічних
додавань знаходився операнд, який найчастіше має значення “істина”.

Якщо ж компілятор не зупиняє обчислень при відомому результаті логічного
виразу, то в деяких випадках можна зменшити кількість логічних
перевірок, наприклад замінивши оператор

if (( a > b ) and ( c > d )) then …

на

if ( a > b ) then

if ( c > d ) then …

7. Індексація.

Якщо можна не використовувати багатовимірні масиви, то краще цього не
робити (при кожному звертанні до елемента багатовимірного масива,
наприклад, A[i,j], відбувається перерахування дійсної адреси елементу
масива, оскільки у пам’яті масив розташований лінійно). Отже, якщо це
можливо, зведіть до мінімуму кількість звертань до елементів масивів,
особливо багатовимірних.

Приклад (множення матриць).

for i := 1 to n do

for j := 1 to n do

begin

c[i,j] := 0.0;

for k := 1 to n do

c[i,j] := c[i,j] + a[i,k]*b[k,j];

end;

Кращий варіант (введемо зайву змінну temp):

for i := 1 to n do

for j := 1 to n do

begin

temp := 0.0;

for k := 1 to n do

temp := temp + a[i,k]*b[k,j];

c[i,j] := 0;

end;

8. Оптимізація циклів.

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

9.Видалення надмірних операцій

Повторні обчислення в циклах є типовою помилкою, яка впливає на
ефективність. В наступних прикладах із циклів видалені інваріантні
вирази.

Замість:

for i := 1 to n do

for k := 1 to n do

x[i,k] := A[i] + sin(k*i); Краще:

for i := 1 to n do

begin

Ai := A[i];

for k := 1 to n do

x[i,k] := Ai + sin(k*i);

end;

Замість:

for i := 1 to n do

S := S + x[i]/n; Краще:

for i := 1 to n do

S := S + x[i];

S := S/n;

10. Порядок вкладання циклів

Організація та виконання циклів типу for вимагають деяких неявних
додаткових затрат часу часу на ініціалізацію змінної циклу та на
перевірку на кожному кроці необхідності завершення циклу. Правильною
організацією вкладених циклів можна економити час роботи програми.
Розглянемо приклад.

for i := 1 to 1000 do

for j := 1 to 100 do

for k:= 1 to 10 do

begin

(* 1000*100*10 кроків *)

end; Неявні операції:

1 ініціалізація i + 1000 перевірок на завершення;

1000 ініціалізацій j + 100000 перевірок;

1000000 ініціалізацій k +1000000 перевірок

Усього:

1001001 ініціалізація + 1101000 перевірок

Якщо порядок вкладання циклів є інваріантним щодо тіла циклу (для
множення матриць, наприклад, це не так), то краще організувати вкладені
цикли таким чином:

for k := 1 to 10 do

for j := 1 to 100 do

for i:= 1 to 1000 do

begin

… (1000*100*10)

end; Неявні операції:

1 ініціалізація k + 10 перевірок завершення;

10 ініціалізацій j + 1000 перевірок;

1000 ініціалізацій i + 1000000 перевірок

Усього:

1011 ініціалізацій + 1001010 перевірок

Отже, будемо користуватись правилом: в інваріантних випадках порядок
вкладання циклів визначається зростанням кількості ітерацій циклу (від
найкоротших до найдовших).

ЛІТЕРАТУРА

Н. Вирт. Систематическое программирование. – М.: Мир, 1977. – 183 с.

Ален И. Голуб. С и С++. Правила программирования. – М.: БИНОМ, 1996. –
272 с.

У. Дал, Э. Дейкстра, К. Хоор. Структурное программирование. – М.: Мир,
1973. – 247 с.

Э. Дейкстра. Дисциплина программирования. – М.: Мир, 1978. – 275 с.

Д. Ван Тассел. Стиль, разработка, эффективность, отладка и испытание
программ. – М.: Мир, 1985. – 332 с.

М. Зелковиц, А. Шоу, Дж. Гэннон. Принципы разработки программного
обеспечения. – М.: Мир, 1982. – 368 с.

Г. С. Иванова. Основы программирования: Учебник для вузов. – М.: Изд-во
МГТУ им. Н.Э. Баумана, 2002. – 416 с.

Г. С. Иванова. Технология программирования: Учебник для вузов. – М.:
Изд-во МГТУ им. Н.Э. Баумана, 2002. – 320 с.

Э. Йодан. Структурное проектирование и конструирование програм. – М.:
Мир, 1979. – 415 с.

Б. Керниган, Р. Пайк. Практика программирования. – СПб.: Невский
диалект, 2001. – 381 с.

Э.Б. Коффман. Turbo Pascal. – М.: Издательский дом «Вильямс», 2002. –
896 с.

Р. Линнер, Х. Миллс, Б Уитт. Теория и практика структурного
программирования. – М.: Мир, 1982. – 406 с.

Похожие записи