Algorytm Sethi-Ullmana: Różnice pomiędzy wersjami
Nie podano opisu zmian |
(Brak różnic)
|
Wersja z 22:46, 24 maj 2003
Algorytm Sethi-Ullmana to algorytm konwersji drzewa na taki szereg prostych instrukcji w którym zostanie użyta minimalna liczba rejestrów (lub zmiennych tymczasowych jeśli rejestry się wyczerpią).
Jest to bardzo ważne, ponieważ większość współczesnych komputerów ma relatywnie niewielką ilość rejestrów
Przykład problemu
Kod:
x = a + (b + (c + (d + x)))
Można przekształcić zgodnie z zasadą "wyliczaj najpierw lewą stronę" na:
t1 = a t2 = b t3 = c t4 = d + x t3 = t1 + t4 t2 = t2 + t3 t1 = t1 + t2 x = t1
Lub też zgodnie z zasadą "wyliczaj najpierw prawą stronę" na:
t1 = d + x t1 = c + t1 t1 = b + t1 t1 = a + t1 x = t1
Dla tego wyrażenia korzystniejsza jest ta druga postać.
Algorytm
Algorytm Sethi-Ullmana pozwala nam zawsze znaleźć optymalną postać. Krok pierwszy polega na wyliczeniu ile co najmniej rejestrów tymczasowych jest potrzebnych do wyliczenia 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
- jeśli węzeł ma 2 podwęzły o takich samych wartościach, otrzymuje tą wartość plus 1
Takie ponumerowanie da nam dla przykładowego wyrażenia:
x = a + (b + (c + (d + x))) 0 0 0 0 0 [ 1 ] [ 1 ] [ 1 ] [ 1 ]
Teraz generujemy kod w następujący sposób:
- Jeśli mają taki sam numer:
- Generujemy kod dla jednego poddrzewa
- Alokujemy dodatkowy rejestr do którego wstawiamy rezultat dotychczasowych obliczeń
- Generujemy kod dla drugiego poddrzewa
- Scalamy wynik
- W przeciwnym razie:
- Generujemy kod dla poddrzewa o większym numerze
- Wykorzystujemy jeden z rejestrów które zaalokowaliśmy na potrzeby wyliczania 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ści i przemienności działań, wyliczyć w trakcie kompilacji stałe części drzewa, oddzielić wyliczanie wspólnych podwyrażeń itd.