Algorytm Sethi-Ullmana - Google

Algorytm Sethi-Ullmana

Z Wikipedii

Skocz do: nawigacji, szukaj

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).

[edytuj] 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 = t3 + 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ć.

[edytuj] 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.


ME w klasie 29-er: Polacy nie obronili tytułu
Brytyjczycy triumfowali w zakończonych w holenderskim Medemblik żeglarskich mistrzostwach Europy w klasie 29-er. Polska załoga Łukasz Przybytek (DKŻ Dobrzyń), Krzysztof Mongird (YK Stal Gdynia) zajęła ósme miejsce.
Lubelskie szczypiornistki mistrzyniami Europy szkół wyższych
Słuchaczki Wyższej Szkoły Społeczno-Przyrodniczej im. Wincentego Pola w Lublinie zostały mistrzyniami Europy szkół wyższych w piłce ręcznej.
Tomasz Piszcz wygrał żużlowy turniej w Lublinie
Tomasz Piszcz wygrał w Lublinie żużlowy turniej zaliczany do Pucharu MACEC (Stowarzyszenia Motocyklowego Krajów Europy Środkowej).
MŚ w piłce nożne plażowej: zacięte półfinały
Brazylia zagra z Włochami w finale rozgrywanych w Marsylii mistrzostw świata w piłce nożnej plażowej.
MŚJ klasy 470: słaby wiatr przyniósł zmiany liderów
Pierwszy dzień wyścigów finałowych mistrzostw świata juniorów w żeglarskiej klasie 470 przyniósł spore zmiany w klasyfikacji generalnej. Zarówno wśród kobiet jak i mężczyzn nastąpiły zmiany liderów.
Linki: Strona gwna