Ustaliliśmy, że decydujący wpływ na szybkość działania programu ma przyjęty algorytm rozwiązania problemu. Decydujący ale nie jedyny, choćby dlatego, że ten sam algorytm można zaprogramować na wiele sposobów: bardzo dobrze i bardzo źle. Dziś zajmiemy się przeglądem konstrukcji, które warto stosować oraz tych, których należy unikać jeśli chcemy, aby nasze programy były optymalne.
Do ilustracji użyję przykładów w BASIC-u, niemniej jednak zachowują one wartość dla innych języków programowania, gdyż wynikają z analizy sposobu w jaki komputer wykonuje dowolny program. Jeśli np. w przykładzie występuje pętla FOR ... NEXT, to zasada ilustrowana tym przykładem dotyczy wszystkich pętli, także tych zorganizowanych za pomocą użytej w programie instrukcji skoku.
Zaczniemy od prostego zadania: na elementy tablicy T trzeba podstawić wartość pola powierzchni koła o danym promieniu R. Można to zrobić tak:
PROGRAM P1
FOR I=1 TO N
PI=3.1415
T(I)=PI*R^2 REM ^ oznacza potęgowanie
NEXT I
W tym programie podstawienie PI=3.1415 wykona się tyle razy, ile wynosi wartość N i to zupełnie niepotrzebnie, bo przecież można tak:
PROGRAM P2
PI=3.1415
FOR I=1 TO N
T(I)=PI*R^2
NEXT I
Zauważmy dalej, że wartość podstawiana na kolejne elementy tablicy NIE ZMIENIA się w czasie wykonywania pętli, co pozwala nam napisać
PROGRAM P3
PI=3.1415
POM=PI*R^2 REM używamy zmiennej pomocniczej POM
FOR I=1 TO N
T(I)=POM
NEXT I
Dzięki tej operacji nasz program wykona o N-1 mniej operacji mnożenia i o tyleż mniej potęgowań. Dzieje się to kosztem użycia jednej zmiennej więcej. Jest to zgodne z ogólną zasadą, że oszczędność czasu wykonania można zwykle uzyskać zwiększając zajęty przez program obszar pamięci, i odwrotnie, oszczędność pamięci zwykle wydłuża czas obliczeń.
Popatrzmy jeszcze przez chwilę na programy P1, P2, P3. Ich porównanie ilustruje zasadę, że wszystko co może być wykonane poza pętlą należy tam właśnie umieszczać. Podkreślam jednak, że takie operację można robić tylko, jeśli wartość wyrzucanych z pętli wyrażeń jest taka sama we wszystkich jej obiegach. Np. jeśli zechcemy kolejnym elementom tablicy nadać wartości pól kół, których promieniami są kolejne liczby naturalne (tzn. w elemencie I pole koła o promieniu I), musimy to zrobić tak:
PROGRAM P4
FOR I=1 TO N
T(I)=PI*I^2
NEXT I
gdyż program:
POM=PI*I^2
FOR I=1 TO N
T(I)=POM
NEXT I
będzie oczywiście błędny (na czym polega błąd?)
Czy jednak program P4 nie da się trochę przyśpieszyć? Możemy spróbować, potrzebna nam będzie jednak trochę głębsza znajomość działania komputera. Otóż na ogół potęgowanie zajmuje dużo więcej czasu niż mnożenie. Możemy tę informację wykorzystać i zamiast potęgowania użyć mnożenia, czyli zamiast
T(I)=PI*I^2
napisać
T(I)=PI*I*I
Podobnie możemy porównać czasy wykonywania innych operacji arytmetycznych np, mnożenie jest na ogół wykonywane dłużej niż dodawanie, czyli zamiast instrukcji
A=2*B
warto napisać (nie ma to nic wspólnego z naszym przykładem z kołami)
A=B+B
UWAGA, 3*B=B+B+B, ale dwa dodawania już wcale nie muszą być szybsze niż jedno mnożenie.
Dalej wiemy jeszcze, że dzielenie jest dłuższe od mnożenia, więc np.
A=B/5
zajmie więcej czasu niż
A=0.2*B
Pamiętajmy jednak, że (w przeciwieństwie do zasady wynoszenia niezmiennych fragmentów przed pętlę) wykorzystujemy tutaj bardzo głęboko pewne właściwości budowy procesora i gdy tylko ktoś zbuduje procesor, który równie szybko mnoży i dzieli co dodaje, takie optymalizacje przestaną być skuteczne, innymi słowy, zanim będziemy stosować chwyty wykorzystujące szczególne właściwości środowiska, w którym działa program, musimy mieć dokładne i rzetelne informacje o tym środowisku. W szczególności zysk z zastąpienia dłuższych działań krótszymi jest niewątpliwy przy korzystaniu z kompilatora, ale jeśli stosujemy interpreter to po zastąpieniu 2*A przez A+A unikamy mnożenia, ale za to operacja identyfikacji zmiennej A występuje dwa razy, a nie jak poprzednio raz. Czy w tej sytuacji powyższa zmienna będzie optymalizacją, czy stratą zależy od samego interpretera. Odpowiedź na takie pytania można czasami znaleźć w instrukcji lub opisie technicznym sprzętu, z którego korzystamy. Można też przeprowadzić serię testów, wykorzystując do nich np. powyższe przykłady. Trzeba tylko przyjąć odpowiednio dużą wartość N, aby różnica w czasie wykonywania poszczególnych pętli była zauważalna.
Oszczędność czasu wynikająca z właściwego doboru operacji jest bardzo niewielka jeśli bierzemy pod uwagę pojedyncze instrukcje, dlatego np. nie warto zmieniać instrukcji POM=PI*R^2 w programie P3, gdyż taki sposób zapisania wzoru ułatwia skojarzenie go ze znanym wszystkim wzorem na pole powierzchni koła, a więc zwiększa czytelność programu. Oszczędność zaczyna być zauważalna jeśli instrukcje, o których mowa, znajdują się wewnątrz pętli. Popatrzmy na przykład:
PROGRAM P5
A=A+1 REM ta instrukcja wykona się tylko raz
FOR I=1 TO N
A=A+1 REM ta instrukcja wykona się N razy
FOR J=1 TO M
B=B+1 REM ta instrukcja wykona się N*M razy (dlaczego?)
FOR K=1 TO L
C=C+1 REM ta instrukcja wykona się N*M*L razy!
NEXT K
NEXT J
NEXT I
Widać chyba na pierwszy rzut oka, że najwięcej możemy uzyskać optymalizując najgłębszą pętlę, tam też warto włożyć najwięcej wysiłku. Jeśli zakresy pętli, to znaczy liczby N, M, L są wszystkie równe 100, to wewnętrzna pętla wykona się 100*100*100, czyli 1000000 razy. Łatwo policzyć o ile godzin! krócej działałby ten program, gdyby skrócić wykonanie zawartości tej pętli tylko o jedną dziesiętną sekundy!
ZAPAMIĘTAJMY: optymalizować programy trzeba w sposób rozsądny. Po pierwsze, nie warto męczyć się cały dzień, aby skrócić czas działania programu o 0.01 sekundy. Dlatego warto pomyśleć nad tym, co się dzieje wewnątrz pętli, szczególnie tych zagnieżdżonych, nie warto zaś zbyt wiele czasu poświęcać instrukcjom, które będą wykonywane tylko raz. Po drugie, nie wolno zapominać, że programy muszą być czytelne i przejrzyste - łatwe do zrozumienia dla człowieka. Niech udoskonalenia nie zmniejszają zbytnio czytelności. Warto również używać komentarzy wyjaśniających sytuację, jeśli stosujemy jakieś skomplikowane chwyty.
Oczywiście powyższe uwagi stosują się do wszystkich sposobów zwiększania efektywności programu, zarówno tych już omówionych, jak i tych, o których będziemy mówić za miesiąc, w drugiej części tego artykułu.
Andrzej Pilaszek, 06/1987r.