Algorytm Sethi-Ullmana: Różnice pomiędzy wersjami

Rozmiar się nie zmienił ,  11 lat temu
m
językowe
m (językowe)
Kod:
x = a + (b + (c + (d + x)))
można przekształcić zgodnie z zasadą „wyliczaj„obliczaj najpierw lewą stronę” na:
t1 = a
t2 = b
t1 = t1 + t2
x = t1
lub też zgodnie z zasadą „wyliczaj„obliczaj najpierw prawą stronę” na:
t1 = d + x
t1 = c + t1
=== Algorytm ===
Algorytm Sethi-Ullmana pozwala nam zawsze znaleźć optymalną postać.
Krok pierwszy polega na wyliczeniuobliczeniu ile co najmniej rejestrów tymczasowych jest potrzebnych do wyliczeniaobliczenia poddrzewa:
* każdy liść otrzymuje wartość 0;
* jeśli węzeł ma 2 podwęzły o różnych wartościach, otrzymuje wartość większego z nich;
* w przeciwnym razie:
** generujemy kod dla poddrzewa o większym numerze,
** wykorzystujemy jeden z rejestrów, które zaalokowaliśmy na potrzeby wyliczaniaobliczania pierwszego poddrzewa,
** generujemy kod dla drugiego poddrzewa,
** scalamy wynik.
 
Algorytm ten ustali „optymalną” kolejność wykonywania obliczeń.
Oczywiście w praktyce możliwe są inne optymalizacje – możemy przekształcić drzewo korzystając z praw [[Łączność (matematyka)|łączności]] i [[przemienność|przemienności]] działań, wyliczyćobliczyć w trakcie kompilacji stałe części drzewa, oddzielić wyliczanieobliczanie [[wspólne podwyrażenie|wspólnych podwyrażeń]] itd.
 
[[kategoria:algorytmy|Sethi-Ullmana]]