Wieża Hanoi jest algorytmem bardzo krótkim i zwięzłym o wykładniczo rosnącej złożoności, wraz z liczbą krążków.
Implementacja w języku PL/SQL jest bardzo prosta..
CREATE OR REPLACE PROCEDURE Pdb_HanoiTower
( vn_Level NUMBER, vn_From NUMBER, vn_To NUMBER,
vn_Helper NUMBER) IS
BEGIN
IF vn_Level > 0 THEN
Pdb_HanoiTower( vn_Level-1, vn_From, vn_Helper, vn_To);
Pdb_HanoiTower(vn_Level-1, vn_Helper, vn_To, vn_From);
END IF;
END;
Do testowania wydajności procedury wykorzystajmy poniższy blok:
DECLARE
vn_Start NUMBER;
BEGIN
vn_Start := dbms_utility.get_time;
PdB_HanoiTower(25,1,3,2);
DBMS_OUTPUT.PUT_LINE( round( (dbms_utility.get_time- vn_start)/100, 2 ) || ' seconds...' );
END;
Blok wykonał się w 16,38 s (średnia z kilku pomiarów).
Spróbujmy przyśpieszyć… Zauważmy, że do przekazywania parametrów wykorzystywany jest typ number, który zapewnia bardzo duży zmiennoprzecinkowy zakres liczbowy, a w naszym przypadku wystarczy zakres typu SIMPLE_INTEGER – jest to odpowiednik czterobajtowego typu signed int z języka C bez sprawdzenia przepełniania ( dla zwiększenia wydajności).. Unikniemy także niepotrzebnych konwersji między typami numerycznymi zmiennopozycyjnymi i całkowitymi..
CREATE OR REPLACE PROCEDURE Pdb_HanoiTower
( vn_Level SIMPLE_INTEGER, vn_From SIMPLE_INTEGER, vn_To SIMPLE_INTEGER,
vn_Helper SIMPLE_INTEGER) IS
BEGIN
IF vn_Level > 0 THEN
Pdb_HanoiTower( vn_Level-1, vn_From, vn_Helper, vn_To);
Pdb_HanoiTower(vn_Level-1, vn_Helper, vn_To, vn_From);
END IF;
END;
Blok testowy dla procedury w powyższej postaci wykonał się w 15.08 s (czas uśredniony).
Przyśpieszajmy dalej.. Ponieważ w trakcie działania procedury wywoływane są dwie procedury z czterema parametrami, zastosujmy mechanizm inline znany z języka C++ - zamiast wskaźnika do funkcji, wstawiane jest rozwinięcie funkcji..
CREATE OR REPLACE PROCEDURE Pdb_HanoiTower
( vn_Level SIMPLE_INTEGER, vn_From SIMPLE_INTEGER, vn_To SIMPLE_INTEGER,
vn_Helper SIMPLE_INTEGER) IS
BEGIN
IF vn_Level > 0 THEN
PRAGMA INLINE (Pdb_HanoiTower, 'YES');
Pdb_HanoiTower( vn_Level-1, vn_From, vn_Helper, vn_To);
PRAGMA INLINE (Pdb_HanoiTower, 'YES');
Pdb_HanoiTower(vn_Level-1, vn_Helper, vn_To, vn_From);
END IF;
END;
Blok testowy wykonał się w 8.66 s – to prawie dwukrotne przyśpieszenie..
Domyślnie funkcjonalności PL/SQL kompilowane są do kodu pośredniego wykonywanego na maszynie wirtualnej.. Oracle 11g oferuje kompilaję do kodu natywnego dla danego systemu operacyjnego.. Wykorzystajmy to
ALTER PROCEDURE PdB_HanoiTower COMPILE PLSQL_CODE_TYPE = NATIVE
Czas wykonania zmniejszył się do 3.83 s. – przyrost ponad czterokrotny..
Usuńmy teraz wskazówki do rozwinięcia funkcji inline (dodawanie ich jest mocno uciążliwe), zachęćmy kompilator do samodzielnego rozwinięcia i innych sztuczek optymalizacyjnych( parametr kompilacji PLSQL_OPTIMIZE_LEVEL = 3).
Kod wraca do czytelnej postaci:
CREATE OR REPLACE PROCEDURE Pdb_HanoiTower
( vn_Level SIMPLE_INTEGER, vn_From SIMPLE_INTEGER, vn_To SIMPLE_INTEGER,
vn_Helper SIMPLE_INTEGER) IS
BEGIN
IF vn_Level > 0 THEN
Pdb_HanoiTower( vn_Level-1, vn_From, vn_Helper, vn_To);
Pdb_HanoiTower(vn_Level-1, vn_Helper, vn_To, vn_From);
END IF;
END;
Po kompilacji
ALTER PROCEDURE PdB_HanoiTower COMPILE PLSQL_CODE_TYPE = NATIVE PLSQL_OPTIMIZE_LEVEL = 3
Czas wykonania zmniejszył się do 3.43..
Warto było?? Uważam, że tak!
Uwagi:
· Powyższy przykład dotyczy Oracle 11g
· Po sprawdzeniu na platformach Windows 64 i HP Unix 64 otrzymałem dość zbliżone przyrosty, wstawiłem z pierwszego środowiska
· Optymalizacja powyższa przeznaczona jest raczej dla algorytmów obliczeniowych lub operujących ma łańcuchach, w mniejszym stopniu opierających się na częstych operacjach bazodanowych
