Kontynuujemy przegląd podstawowych elementów techniki pisania programów, mających wpływ na efektywność otrzymanego kodu. Zaczniemy od przykładu, w którym wyjątkowo uda się zaoszczędzić i czasu i pamięci. Poniższy program nadaje wartości początkowe elementom dwóch tablic T i A:
PROGRAM P6
FOR I=1 TO N
T(I) = 0
NEXT I
FOR I=1 TO N
A(I) = I
NEXT I
Wykonanie pętli to nie tylko wykonanie N razy zawartych w niej instrukcji (w naszym przypadku podstawienia) ale również wykonanie tyle samo razy operacji pomocniczych, służących do zorganizowania pętli, takich jak zwiększenie wartości zmiennej I o 1, sprawdzenie czy już I równa się N itd. Jednym słowem organizacja pętli też kosztuje - widać to wyraźnie jeśli organizujemy tę pętlę sami, przy pomocy skoków warunkowych. W takim razie, skoro już jedną pętlę zorganizowaliśmy, to wykorzystajmy ją do maksimum.
FOR I=1 TO N
T(I)=0
A(I)=I
NEXT I
W ten sposób skracamy również program o kod potrzebny na zorganizowanie drugiej pętli.
Skoro już mowa o minimalizacji kosztów organizacji pętli, to popatrzmy na następujące instrukcje:
FOR I=1 TO N*M
T(I)=I
NEXT I
Żeby sprawdzić, czy I osiągnęło już końcową wartość trzeba po każdym wykonaniu zawartości obliczyć wartość wyrażenia N*M. I jest to obliczenie niepotrzebne, bo wartości N i M nie zmieniają się wewnątrz pętli, więc można to zrobić tak:
NM = N*M FOR I=1 TO NM REM itd.
Przejdźmy teraz do następnego zagadnienia, którym jest wykorzystanie w programach tzw. zmiennych indeksowanych, czyli odwołań do elementów tablic. Są one kosztowniejsze niż odwołania do zwykłych zmiennych, gdyż wymagają obliczenia położenia w pamięci żądanego elementu tablicy na podstawie podanych indeksów: Rozważmy następujące zadanie: mamy dane współczynniki A, B, C trójmianu kwadratowego, czyli funkcji ax2 + bx + c. W tablicy X są wartości z, dla których trzeba obliczyć wartość trójmianu. Można to zrobić tak:
PROGRAM P7
FOR I=1 TO N
PRINT A*X(I)*X(I) + B*X(I) + C
NEXT I
trzy razy odwołując się do tego samego elementu X(I). Można również użyć zmiennej pomocniczej, która pozwoli tego uniknąć:
PROGRAM P8
FOR I=1 TO N
POM=X(I) REM Czy to podstawienie musi być w pętli ?
PRINT A*POM*POM + B*POM + C
NEXT I
W naszym przykładzie użyliśmy tablicy zawierającej liczby, jednak takie podejście stosuje się do tablic wszystkich typów.
Następnym godnym uwagi źródłem oszczędności są wyrażenia arytmetyczne. Obliczymy dwa pierwiastki trójmianu kwadratowego
X1 = (-B -SQRT (B*B - 4*A*C)) / (2*A) X2 = (-B +SQRT (B*B - 4*A*C)) / (2*A)
Dwa razy obliczana jest dokładnie ta sama wartość pierwiastka. Można to łatwo usprawnić, wykonując obliczenie pomocnicze i zapamiętując jego wynik:
PROGRAM P9 SQ = SQRT(B*B - 4*A*C) X1 = (-B - SQ)/(2*A) X2 = (-B + SQ)/(2*A)
Jest to usprawnienie tym bardziej ważne, że obliczanie wartości funkcji matematycznych, takich jak pierwiastek, logarytm, sinus itd. wymaga wykonania przez komputer dużej liczby obliczeń, a więc zajmuje wielokrotnie więcej czasu niż zwykłe działania arytmetyczne czy podstawienie wartości na zmienną. Jednak zapamiętywanie na zmiennych pomocniczych tych fragmentów wyrażeń arytmetycznych, które powtarzają się w programie wielokrotnie, jest opłacalne nawet gdy nie występują w nich wywołania funkcji.
W programie P9 możemy jeszcze "pozbyć się" jednej operacji dzielenia:
POM = 1/(2*A) SQ = SQRT(B*B-4*A*C) X1 = (-B - SQ)*POM X2 = (-B + SQ)*POM
Zrobiliśmy to kosztem użycia dodatkowej zmiennej i... zmniejszenia się czytelności programu.
Ważna jest umiejętność przekształcania wyrażeń arytmetycznych. W programie P8 możemy usunąć z pętli jeszcze jedno mnożenie tylko dzięki wyciągnięciu przed nawias - popatrzcie uważnie.
Oszczędność czasu wykonywania można uzyskać również dzięki właściwej budowie programu. Znowu posłużymy się przykładem:
PROGRAM P10 IF DTYG=1 THEN PRINT "Poniedziałek" IF DTYG=2 THEN PRINT "Wtorek" IF DTYG=3 THEN PRINT "Środa"
Z trzech powyższych warunków tylko jeden może być prawdziwy, niemniej jednak, nawet jeśli prawdziwy jest już pierwszy, to i tak sprawdzane będą wszystkie! Możemy tego uniknąć jeśli język, w którym programujemy rozpoznaje konstrukcje IF ... THEN ... ELSE. Możemy wtedy napisać:
PROGRAM P11
IF DTYG=1 THEN
PRINT "Poniedziałek"
ELSE
IF DTYG=2 THEN
PRINT "Wtorek"
ELSE
IF DTYG=3 THEN
PRINT "Środa"
ENDIF
ENDIF
ENDIF
Niektóre języki programowania, np. PASCAL, zawierają specjalną instrukcję CASE, która pozwala zapisać to samo co zawiera program P11 w dużo wygodniejszy sposób.
Ważnym elementem programów są procedury, lub jak kto woli podprogramy. Instrukcja wywołania podprogramu jest instrukcją dość kosztowną, przy czym koszt jest tym większy im więcej parametrów przekazujemy do wołanego podprogramu. Jednak upatrywanie źródła oszczędności w eliminacji podprogramów było by dużym błędem. Rozsądnie dobrane podprogramy są elementem praktycznie niezbędnym przy realizacji prawie wszystkich zadań, a zyski płynące z ich używania zawsze przekraczają koszty wywołań. Pamiętajmy tylko, że jeśli nie jest to konieczne, to nie należy umieszczać wywołań wewnątrz pętli.
No zakończenie chciałbym jeszcze raz przypomnieć, że jak w każdej dziedzinie życia, tak i w programowaniu potrzebny jest zdrowy rozsądek. Chciałbym, aby podane wyżej przykłady i zasady posłużyły Wam do zrozumienia pewnych mechanizmów występujących przy realizacji programów przez współczesne komputery. Natomiast potraktowanie podanego materiału jako zbiór zasad, których należy ślepo i bezmyślnie przestrzegać może w szczególnych przypadkach przynieść więcej strat niż pożytku.
Pamiętajmy również, że programu zbudowanego w oparciu o nieefektywny, za wolny algorytm nie uratują żadne sztuczki programistyczne, oraz o tym, że nadrzędną wartością dla programów jest poprawne działanie. Program w pełni zoptymalizowany, ale działający niepoprawnie jest zupełnie bezwartościowy.
Andrzej Pilaszek - Bajtek 07/1997r.