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

[wersja nieprzejrzana]

Usunięta treść Dodana treść

Jednokolumnowy

Wersja z 14:26, 29 wrz 2008

Algorytm Sethi-Ullmana – 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.

Jego autorami są Ravi Sethi oraz Jeffrey Ullman (stąd nazwa).

Przykład problemu

Kod:

x = a + (b + (c + (d + x)))

można przekształcić zgodnie z zasadą „obliczaj najpierw lewą stronę” na:

t1 = a
t2 = b
t3 = c
t4 = d + x
t3 = t3 + t4
t2 = t2 + t3
t1 = t1 + t2
x  = t1

lub też zgodnie z zasadą „obliczaj 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 obliczeniu ile co najmniej rejestrów tymczasowych jest potrzebnych do obliczenia 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 obliczania 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ń, obliczyć w trakcie kompilacji stałe części drzewa, oddzielić obliczanie wspólnych podwyrażeń itd.

@@ Linia 6: / Linia 6: @@
 Kod:
  x = a + (b + (c + (d + x)))
-można przekształcić zgodnie z zasadą „wyliczaj najpierw lewą stronę” na:
+można przekształcić zgodnie z zasadą „obliczaj najpierw lewą stronę” na:
  t1 = a
  t2 = b
@@ Linia 15: / Linia 15: @@
  t1 = t1 + t2
  x  = t1
-lub też zgodnie z zasadą „wyliczaj najpierw prawą stronę” na:
+lub też zgodnie z zasadą „obliczaj najpierw prawą stronę” na:
  t1 = d + x
  t1 = c + t1
@@ Linia 26: / Linia 26: @@
 === 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:
+Krok pierwszy polega na obliczeniu ile co najmniej rejestrów tymczasowych jest potrzebnych do obliczenia 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;
@@ Linia 47: / Linia 47: @@
 * 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,
+** wykorzystujemy jeden z rejestrów, które zaalokowaliśmy na potrzeby obliczania 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ć w trakcie kompilacji stałe części drzewa, oddzielić wyliczanie [[wspólne podwyrażenie|wspólnych podwyrażeń]] itd.
+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ń, obliczyć w trakcie kompilacji stałe części drzewa, oddzielić obliczanie [[wspólne podwyrażenie|wspólnych podwyrażeń]] itd.
 [[kategoria:algorytmy|Sethi-Ullmana]]