Ефективність програм та методи оптимізації
План
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));
б) 4vA краще обчислювати як 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. Отже, треба розташовувати логічні операнди таким чином, щоб на початку виразу послідовних логічних множень знаходився операнд, який найчастіше має значення “хибність”.
Логічний вираз