Оптимальні програми обчислення виразів, Детальна інформація

КД - кількість дужок (на стек попадають лише відкриваючі дужки, але ж їх потім звідти ще й забирають, тому операцій вдвічі більше);

КО - кількість операцій (кожна операція попадає на стек, знімається звідти і виводиться у вихідну послідовність);

КБ - кількість букв-ідентифікаторів (кожен ідентифікатор одразу виводиться);

ППО - порівняння пріоритетів операцій (перед тим, як занести операцію на стек, звідти видаляються операції з меншим пріоритетом).

Можна також дати наступні оцінки для розглядуваних величин:

КД ( 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;