|
|  |
Оптимальні програми обчислення виразів, Детальна інформація
|
КД - кількість дужок (на стек попадають лише відкриваючі дужки, але ж їх потім звідти ще й забирають, тому операцій вдвічі більше);
КО - кількість операцій (кожна операція попадає на стек, знімається звідти і виводиться у вихідну послідовність);
КБ - кількість букв-ідентифікаторів (кожен ідентифікатор одразу виводиться);
ППО - порівняння пріоритетів операцій (перед тим, як занести операцію на стек, звідти видаляються операції з меншим пріоритетом).
Можна також дати наступні оцінки для розглядуваних величин:
КД ( 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;
|
| Коментарі до даного документу |
|
|
|
|
 |
ТОП-5 АВТОРІВ |
|
|
|
|
Скачати "Курсова на тему Оптимальні програми обчислення виразів"
