Найбільш важливими з точки зору практичного використання є наступні критерії ефективності алгоритмів:
Критерії 1 та 3 дуже подібні між собою, проте не еквівалентні. Прогрес у мікроелектроніці привів до того, що сучасні комп’ютери, навіть ті, які мають лише один процесор, можуть виконувати декілька команд одночасно. Тому, виконуючи бодай часткове розпаралелювання обчислень, можна отримати суттєвий приріст швидкості виконання.
Ввівши необхідні нам поняття, ми можемо перейти до оцінки різних алгоритмів згідно вказаних критеріїв.
Перш за все, ми повинні звернути увагу на те, що алгоритми переводу виразу з інфіксної форми представлення до префіксної та обчислення виразу в префіксній формі можуть бути одразу виключені з розгляду згідно наступних причин:
Тоді нам залишається розглянути тільки алгоритми обчислення виразу безпосередньо в інфіксній формі та обчислення за допомогою переведення в постфіксну форму.
Раніше ми вже відмічали, що алгоритми POSTFIX та ІТР мають складність O(N). Тоді їх послідовне застосування дає нам алгоритм обчислення виразів в інфіксній формі, складність якого буде також О(N). Спробуємо уточнити дану оцінку. Для цього просто підрахуємо операції, що виконуються в процесі роботи. Для алгоритму ІТР кількість операцій буде
К = N + КД + КО * 3 + КБ + ППО ,
де N - кількість операцій порівняння символів (визначення наступного символу послідовності);
КД - кількість дужок (на стек попадають лише відкриваючі дужки, але ж їх потім звідти ще й забирають, тому операцій вдвічі більше);
КО - кількість операцій (кожна операція попадає на стек, знімається звідти і виводиться у вихідну послідовність);
КБ - кількість букв-ідентифікаторів (кожен ідентифікатор одразу виводиться);
ППО - порівняння пріоритетів операцій (перед тим, як занести операцію на стек, звідти видаляються операції з меншим пріоритетом).
Можна також дати наступні оцінки для розглядуваних величин:
КД £ N/2 (не більше половини символів у виразі є дужками);
KO £ N/2 (не більше половини символів є знаками операцій);
КБ £ N/2 +1;
ППО £ КО £ N/2.
Звідси можемо зробити висновок, що загальна кількість операцій алгоритму ІТР має порядок 4N.
Для алгоритму POSTFIX має місце така формула:
К = N + 2*СЄ + КО,
де N - кількість операцій порівняння символів (визначення наступного символу послідовності);
СЄ - сумарна ємність арифметичних функцій та операцій виразу (для кожної функції операнди спочатку попадають на стек, а потім знімаються звідти для обчислень);
КО - кількість операцій (має місце просте виконання дій або виклик арифметичних функцій).
Величину СЄ можна оцінити так:
СЄ < N (випливає з твердження 3).
Тому загальна оцінка кількості операцій алгоритму POSTFIX має порядок 3.5 * N.
Тепер розглянемо деякий абстрактний алгоритм обчислення виразу в інфіксній формі (назвемо його INFIX), який знаходить шукане значення без конвертації виразу в постфіксну форму. Оцінимо той мінімально можливий набір операцій, що повинен виконати INFIX.
К = N + КД + 3*КО + 2*КБ + ППО,
де N - операції аналізу символу, КД - занесення і видалення дужок зі стеку, або рекурсивний виклик алгоритму для підвиразу в дужках; 3*КО - операції спочатку повинні заноситися на стек, до вияснення їх пріоритету відносно сусідніх операцій, потім зніматися звідти і виконуватися; 2*КБ - букви (операнди, ідентифікатори, константи) спочатку повинні попадати на стек, потім зніматися для обчислень; ППО - порівняння пріоритетів операцій.
Тому загальну кількість операцій можна оцінити порядком 4.5*N.
Ми приходимо до висновку, що в загальному випадку жоден алгоритм, що обчислює арифметичний чи логічний вираз безпосередньо в інфіксній формі є не кращим за алгоритм POSTFIX, котрий обчислює той самий вираз в постфіксній формі запису. Тут потрібно також прийняти до уваги той факт, що запис виразу в постфіксній формі є коротшим, оскільки не містить дужок та ком між аргументами функцій, і найчастіше вже є лексично згорнутим, отже наведені вище оцінки алгоритмів будуть ще більше відрізнятися між собою (за суттєвої переваги POSTFIX). Отже складність алгоритму INFIX є більшою за складність POSTFIX, і в той же час меншою за складність комбінації ITP+POSTFIX (якщо ні, то ми просто замінимоINFIX на ITP+POSTFIX).
Цей факт дуже корисно використовувати при розробці компіляторів. При використанні алгоритму POSTFIX левову частку обчислень (аналіз, перевід виразу в постфіксну форму) можна виконати на етапі компіляції, а вже безпосередньо згенерована програма буде виконувати значно менше обчислень ніж у випадку безпосереднього обчислення інфіксного виразу. Крім того, алгоритм POSTFIX потребує для роботи не більше ніж N/2 вільних елементів стекового простору, в той час як для INFIX потрібно резервувати N елементів пам’яті, оскільки на стек попадають як операнди, так і операції разом з дужками (або з рекурсивними самовикликами для обчислення підвиразів у дужках).
§4. Оптимізація програм.
Взагалі кажучи, безпосереднє обчислення виразів у інфіксній формі слабо піддається оптимізації. І, зважаючи на те, що складність алгоритмів обчислення є лінійною, для інтерпретаторів проблема оптимізації гостро не стоїть. Зовсім інша ситуація спостерігається в області компіляторів, де іде боротьба з кожним "зайвим" тактом роботи процесора. Існують різні методи машинно-залежної та машинно-незалежної оптимізації коду [3]. Вони можуть використовуватися на всіх рівнях синтаксичного представлення і використовувати відомості про весь текст програми для оптимізації обчислення одного виразу. Одним з найпростіших методів є так зване "розмноження констант". При його використанні довільне посилання на константу замінюється самим значенням константи. В наступному прикладі підвищити ефективність коду можна завдяки видаленню трьох адресних посилань і заміні їх константами:
у = 3;
а = (у + 1) * ( у - 5) + с / у;
переводиться в
у = 3;
а = (3 + 1) * ( 3 - 5) + с / 3;
Розмноження констант може навіть зменшити кількість необхідних присвоювань. Також воно тісно пов’язане з методом "згортки констант" (константною арифметикою), що зводить вирази з константами до якомога простішої форми. Сталі величини використовуються в програмі або безпосередньо (як у випадку чисел та цифр), або опосередковано (як у випадку декларування констант).
Згортка констант зводить наступний фрагмент програми на мові C
#define TWO 2
a = 1 + TWO;
до його еквівалентної форми
а = 3;
під час компіляції, завдяки чому видаляються зайві арифметичні операції із стадії виконання програми. Згортання констант можна застосовувати як до цілочислових констант, так і до логічних та констант з плаваючою комою.
"Алгебраїчні спрощення" - це різновид згортки констант, який видаляє арифметичні тотожності. Код, що генерується для таких операторів як
х = у + 0;
х = у * 0;
х = у / 1.0;
повинен бути простим константним присвоюванням і не повинен містити команд для виконання арифметичних операцій. Подібні вирази можуть бути і частиною більш складного виразу, тому завчасне їх виявлення може значно спростити обчислювальний процес.
"Логічні спрощення" - аналог попереднього методу оптимізації, що стосується логічних виразів. Оператори
x = y AND False;
x = y AND True;
x = y OR True;
x = y OR False;
та їх неявні модифікації можуть бути спрощені для уникнення зайвих обчислень. Можливі випадки навіть повного припинення обчислення логічного виразу, якщо в процесі роботи було виявлено незалежність результату від значень підвиразів.
"Видалення спільних підвиразів" - це процес зменшення кількості зайвих обчислень. Замість того, щоб генерувати код для обчислення значення кожен раз, коли воно використовується, оптимізуючий компілятор може спробувати виділити вираз таким чином, щоб його значення обчислювалося тільки один раз. Там, де це можливо, наступні появи цього ж виразу використовують раніше обчислене значення. Наприклад у*3 є спільним підвиразом у наступному тексті:
if( a[y*3] < 0 || b[y*3] > 10)
a[y*3] = 0;
Виділення його приводить до логічно еквівалентного тексту, що містить менше обчислень:
Т1 = у*3;
if( a[Т1] < 0 || b[Т1] > 10)
a[Т1] = 0;
Видалення спільних підвиразів зазвичай відбувається всередині оператора або блоку операторів. "Глибоке видалення спільних підвиразів" є більш складним методом, оскільки тут аналізу підлягають базові блоки конкретної мови програмування.
"Зменшення потужності" має на увазі заміщення операцій, які потребують більшого часу виконання, більш швидкими. Це є класичний приклад машинно-залежної оптимізації. Компілятор може використовувати зменшення потужності різними способами. Наприклад, застосовуючи зменшення потужності до вже згенерованого коду, компілятор може замінювати операції, які множать або ділять цілі числа на степені двійки операціями зсуву.
"Видалення зайвих присвоювань" включає знаходження проміжку існування змінної і знищення присвоювань значень цієї змінної, якщо ці присвоювання не можуть змінити логіку програми. Цей метод звільняє обмежені ресурси, такі як стековий простір або машинні регістри (чому важливо мати багато вільних регістрів буде описано далі). В наступній послідовності команд:
а = х + у*3 - с;
b = 0;
a = b;
перший оператор є зайвим присвоюванням і може бути безпечно видалений. Зайві присвоювання можуть виникати ненавмисно, коли проміжок існування змінної великий і між входженнями змінної є доволі багато коду. Зайві присвоювання можуть бути також результатом попередніх проходів оптимізації.