Wikipedia

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

Przeglądaj historię interaktywnie
[wersja nieprzejrzana][wersja nieprzejrzana]
← poprzednia edycjanastępna edycja →
Usunięta treść Dodana treść
WizualnieWikikod
Kocio (dyskusja | edycje)
Redaktorzy
46 587 edycji
Blade BMRQ (dyskusja | edycje)
771 edycji
Nie podano opisu zmian
Linia 1:
'''Algorytm Sethi-Ullmana''' to– algorytm konwersji [[drzewo (matematyka)|drzewa]] na taki szereg prostych instrukcji w którym zostanie użyta minimalna liczba [[rejestr|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).
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)))▼
<pre>
Możnamożna przekształcić zgodnie z zasadą "wyliczaj„wyliczaj najpierw lewą stronę"stronę” na:▼
▲x = a + (b + (c + (d + x)))
t1 = a + t1▼
</pre>
t2 = b
 
t3 = c
▲Można przekształcić zgodnie z zasadą "wyliczaj najpierw lewą stronę" na:
t1 t4 = d + x▼
<pre>
t1 t3 = at3 + t4
t2 = bt2 + t3
t3 t1 = ct1 + t2
t4 x = d + xt1
Lublub też zgodnie z zasadą "wyliczaj„wyliczaj najpierw prawą stronę"stronę” na:▼
t3 = t3 + t4
t2 t1 = t2d + t3x
t1 = t1c + t2t1
x t1 = b + t1
t1 = ca + t1▼
</pre>
x = t1▼
 
▲Lub też zgodnie z zasadą "wyliczaj najpierw prawą stronę" na:
<pre>
▲t1 = d + x
▲t1 = c + t1
t1 = b + t1
▲t1 = a + t1
▲x = t1
</pre>
 
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)))
<pre>
x = a + (b +0 (c + (d +0 x))) 0 0 0
0 0 0 0 0[ 1 ]
[ [ 1 ]
[ [ 1 ]
[ [ 1 ]
[ 1 ]
</pre>
 
Teraz generujemy kod w następujący sposób:
* Jeślijeśli mają taki sam numer:
** Generujemygenerujemy kod dla jednego poddrzewa,
** Alokujemyalokujemy dodatkowy rejestr, do którego wstawiamy rezultat dotychczasowych obliczeń,
** Generujemygenerujemy kod dla drugiego poddrzewa,
** Scalamyscalamy wynik;
* Ww przeciwnym razie:
** Generujemygenerujemy kod dla poddrzewa o większym numerze,
** Wykorzystujemywykorzystujemy jeden z rejestrów, które zaalokowaliśmy na potrzeby wyliczania pierwszego poddrzewa.,
** Generujemygenerujemy kod dla drugiego poddrzewa,
** Scalamyscalamy wynik.
 
Algorytm ten ustali "optymalną"„optymalną” kolejność wykonywania obliczeń.
Oczywiście w praktyce możliwe są inne optymalizacje -– możemy przekształcić drzewo korzystając z praw [[łączność|łą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.
 
[[kategoria:algorytmy]]
 
[[en:Sethi-Ullman algorithm]]
Źródło: „https://pl.wikipedia.org/wiki/Algorytm_Sethi-Ullmana”