LEKCJA 22
NA ZDROWY CHŁOPSKI ROZUM PROGRAMISTY.
W trakcie tej lekcji dowiesz się:
* jak przyspieszać działanie programów w C++
* jakie dodatkowe narzędzia zyskujesz "przesiadając się" na nowoczesny kompilator C++
UNIKAJMY PĘTLI, które nie są NIEZBĘDNE !
Unikanie zbędnych pętli nazywa się fachowo "rozwinięciem pętli" (ang. loop unrolling). Zwróć uwagę, że zastępując pętlę jej rozwinięciem (ang. in-line code):
* zmniejszamy ilość obliczeń,
* zmniejszamy ilość zmiennych.
Wyobraźmy sobie pętlę:
for (i = 0; i < max; i++)
T[i] = i;
Jeśli "unowocześnimy" ją tak:
for (i = 0; i < max; )
{
T[i++] = i - 1;
T[i++] = i - 1;
}
ilość powtórzeń pętli zmniejszy się dwukrotnie. Czai się tu jednak pewne niebezpieczeństwo: tablica może mieć NIEPARZYSTĄ liczbę elementów. Np. dla 3-elementowej tablicy (max = 3) nastąpiłyby w pierwszym cyklu operacje:
i = 0;
0 < 3 ? == TRUE --> T[0] = 0 // Tu nastepuje i++; //
T[1] = 1 itd...
To, co następuje w tak "spreparowanej" tablicy możesz prześledzić uruchamiając program:
[P078.CPP]
# include <iostream.h>
# include <stdio.h>
# include <conio.h>
# define p(x) printf("%d\t", x)
int T[99+1], i, max;
main()
{
cout << "\nPodaj ilosc elem. tablicy T[] - 2...99 \n";
cin >> max;
cout << "T[i]\t\ti\n\n";
for (i = 0; i < max; )
{
T[i++] = i - 1; p(T[i-1]); cout << "\t" << i << "\n";
T[i++] = i - 1; p(T[i-1]); cout << "\t" << i << "\n";
while (!kbhit());
}
return 0;
}
Aby nie spowodować próby odwołania do nieistniejącego elementu tablicy, możemy zadeklarować tablicę T[max + 1]. W przypadku, gdy max jest liczbą nieparzystą, tablica wynikowa posiada parzystą liczbę elementów. Jeśli natomiast max jest parzyste, tworzymy jeden zbędny element tablicy, który później zostanie użyty, ale kompilator ani program nie będzie nam się "buntował". Można spróbować zastąpić w programie bardziej czasochłonne operacje - szybszymi. Dla przykładu, w pętli
for(i = 1; i <= 100; i++)
{
n = i * 10;
...
można wyeliminować czasochłonne mnożenie np. tak:
for(i = 1, n = 10; i <= 100; i++, n += 10)
{
...
lub wręcz wprost, jeśli dwie zmienne robocze nie są niezbędne:
for(n = 10; n <= 1000; n += 10)
{
...
Jeśli wiadomo, że jakaś pętla powinna wykonać się z definicji choćby raz, warto wykorzystywać konstrukcję do...while, zamiast analizować niepotrzebnie warunek. Jeśli stosujemy w programie pętle zagnieżdżone (ang. nested loops), to pęta zorganizowana tak:
for(i = 1; i < 5; i++) (1)
for(j = 1; j < 1000; j++)
{ A[i][j] = i + j; }
zadziała szybciej niż
for(j = 1; j < 1000; j++) (2)
for(i = 1; i < 5; i++)
{ A[i][j] = i + j; }
W przypadku (1) zmienna robocza pętli wewnętrznej będzie inicjowana pięć razy, a w przypadku (2) - tysiąc (!) razy. Czasami zdarza się, że w programie można połączyć kilka pętli w jedną.
for(i = 1; i < 5; i++)
TAB_1[i] = i;
...
for(k = 0; k < 5; k++)
TAB_2[k] = k;
Zmniejsza to i ilość zmiennych, i tekst programu i czas pracy komputera:
TAB_2[0] = 0;
for(i = 1; i < 5; i++)
TAB_1[i] = i;
TAB_2[i] = i;
Czasami wykonywanie pętli do końca pozbawione jest sensu. Przerwać pętlę w trakcie wykonywania można przy pomocy instrukcji break (jeśli pętle są zagnieżcżone, często lepiej użyć niepopularnego goto przerywającego nie jedną - a wszystkie pętle). Stosując umiejętnie break, continue i goto możesz zaoszczędzić swojemu komputerowi wiele pracy i czasu. Rutynowym "szkolno-strukturalnym" zapętlaniem programu
main() {
char gotowe = 0;
...
while (!gotowe)
{
znak = wybrano_z_menu();
if (znak == 'q' || znak == 'Q') gotowe = 1;
else
.......
gotowe = 1;
}
powodujesz często zupełnie niepotrzebne dziesiątki operacji, które już niczemu nie służą.
char gotowe;
main() {
...
while (!gotowe)
{
znak = wybrano_z_menu();
if (znak == 'q' || znak == 'Q') break; //Quit !
else
.......
gotowe = 1;
}
Tym razem to, co następuje po else zostanie pominięte. Wskaźniki działają w C++ szybciej, niż indeksy, stosujmy je w miarę możliwości w pętlach, przy manipulowaniu tablicami i w funkcjach.
INSTRUKCJE STERUJĄCE I WYRAŻENIA ARYTMETYCZNE.
Na "chłopski rozum" programisty wiadomo, że na softwarowych rozstajach, czyli na rozgałęzieniach programów prawdopodobieństwo wyboru każdwgo z wariantów działania programu z reguły bywa różne. Kolejność sprawdzania wyrażeń warunkowych nie jest zatem obojętna. Wyobraźmy sobie lekarza, który zwiezionego na toboganie narciarza pyta, czy ktoś w rodzinie chorował na żółtaczkę, koklusz, reumatyzm, podagrę, itp. zamiast zająć się najpierw wariantem najbardziej prawdopodobnym - czyli zagipsowaniem nogi nieszczęśnika. Absurdalne, prawda? Ale przecież (uderzmy się w piersi) nasze programy czasami postępują w taki właśnie sposób...
NAJPIERW TO, CO NAJBARDZIE PRAWDOPODOBNE I NAJPROSTSZE.
Jeśli zmienna x w naszym programie może przyjmować (równie prawdopodobne) wartości 1, 2, 3, 4, 5, to "przesiew"
if (x >= 2) { ... }
else if (x == 1) { ... }
else { ... }
okaże się w praktyce skuteczniejszy, niż
if (x == 0) { ... }
else if (x == 1) { ... }
else { ... }
Należy pamiętać, że w drabince if-else-if po spełnieniu pierwszego warunku - następne nie będą już analizowane. Zasada ta stosuje się także do wyrażeń logicznych, w których stosuje się operatory logiczne || (lub) i && (i). W wyrażeniach tych, których ocenę C++ prowadzi tylko do uzyskania pewności, jaka będzie wartość logiczna (a nie koniecznie do końca wyrażenia) należy zastosować kolejność:
MAX || W1 || W2 || W3 ...
MIN && W1 && W2 && W3 ...
gdzie MAX - oznacza opcję najbardziej prawdopodobną, a MIN - najmniej prawdopodobną. Podobnie rzecz ma się z pracochłonnością (zatem i czso-chłonnością) poszczególnych wariantów. Jeśli wariant najprostszy okaże się prawdziwy, pozostałe możliwości możemy pominąć.
NIE MNÓŻ I NIE DZIEL BEZ POTRZEBY.
Prawa MATEMATYKI pozostają w mocy dla IBM PC i pozostaną zawsze, nawet dla zupełnie nieznanych nam komputerów, które skonstruują nasze dzieci i wnuki. Znajomość praw de Morgana i zasad arytmetyki jest dla programisty wiedzą niezwykle przydatną. Jako próbkę zapiszmy kilka trywialnych tożsamości przetłumaczonych na C++:
2 * a == a + a == a << 1
16 * a == a << 4
a * b + a * c == a * (b + c)
~a + ~b == ~(a + b)
Możnaby jeszcze dodać, że a / 2 == a >> 1, ale to nie zawsze prawda. Przesunięcie w prawo liczb nieparzystych spowoduje obcięcie części ułamkowej. W przypadku wyrażeń logicznych:
(x && y) || (x && z) == x && (y || z)
(x || y) && (x || z) == x || (y && z)
W arytmetycznej sumie i iloczynie NIE MA takiej symetrii.
!x && !y == !(x || y)
!x || !y == !(x && y)
Jeśli w skomplikowanych wyrażeniach arytmetycznych i logicznych zastosujemy zasady arytmetyki i logiki, zwykle stają się krótsze i prostsze. Podobnie jak licząc na kartce, możemy zastosować zmienne pomocnicze do przechowywania często powtarzających się wyrażeń składowych. Wyrażenie
wynik = (x * x) + (x * x);
możemy przekształcić do postaci
zm_pomocn = x * x;
wynik = zm_pomocn << 1;
Często napisane "na logikę" wyrażenia da się łatwo zoptymalizować. Jako przykład zastosujmy funkcję biblioteczną strcmp() (string compare - porównaj łańcuchy znaków). Porównanie łańcuchów
if (strcmp(string1, string2) == 0) cout << "identyczne";
else if (strcmp(string1, string2) < 0) cout << "krotszy";
else
cout << "dluzszy";
można skrócić tak, by funkcja strcmp() była wywoływana tylko raz:
wynik = strcmp(string1, string2);
if (wynik == 0)
cout << "identyczne"; break;
else if (wynik < 0)
cout << "krotszy";
else
cout << "dluzszy";
Jeśli pracując nad programem nie będziemy zapominać, że PC operuje arytmetyką dwójkową, wiele operacji dzielenia i mnożenia (długich i pracochłonnych) będziemy mogli zastąpić operacjami przesunięcia w lewo, bądź w prawo (ang. shift), które nasz PC wykonuje znacznie szybciej. Dla liczb całkowitych dodatnich
x * 2 == x << 1; x * 4 == x << 2 itp. ....
[???] UWAGA:
Takich skrótów nie można stosować w stosunku do operandów typu double, ani float.
Podobnie w przypadku dzielenia przez potęgę dwójki można zastąpić dzielenia znacznie szybszą operacją iloczynu logicznego.
x % 16 == x & 0xF;
Jeśli w programie wartość zmiennej powinna zmieniać się w sposób piłokształtny (tj. cyklicznie wzrastać do MAXIMUM i po osiągnięciu MAXIMUM spadać do zera), najprostszym rozwiązaniem jest
x = (x + 1) % (MAXIMUM + 1);
ale dzielenie trwa. Poniższy zapis spowoduje wygenerowanie kodu znacznie szybszego:
if (x == MAXIMUM) x = 0;
else x++;
stosując zamiast if-else operator ? : możemy to zapisać tak:
(x == MAXIMUM) ? (x = 0) : (x++);
Mnożenie jest zwykle trochę szybsze niż dzielenie. Zapis
a = b / 10;
można zatem zastąpić szybszym:
a = b * .1;
Jeśli mamy do czynienia ze stałą STALA, to zapis w programie
y = x / STALA; --> y = x * (1.0 / STALA);
z pozoru bzdurny spowoduje w większości implementacji wyznaczenie wartości mnożnika 1.0/STALA przez kompilator na etapie kompilacji programu (compile-time), a w ruchu (run-time) będzie obliczany iloczyn zamiast ilorazu. W programach często stosuje się flagi binarne (jest-nie ma). C++ stosujemy jako flagi zmienne typu int lub char a w Windows BOOL. Jeśli weźmiemy pod uwagę fakt, że operatory relacji generują wartości typu TRUE/FALSE, typowy zapis:
if (a > b)
Flaga = 1;
else
Flaga = 0;
zastąpimy krótszym
Flaga = (a > b);
Taki krótszy zapis NIE ZAWSZE powoduje wygenerowanie szybszego kodu. Jest to zależne od specyfiki konkretnej implementacji. Jeśli natomiast uprościsz swój program tak:
if (x > 1) a = 3; --> a = 3 * (x > 1);
else a = 0;
spowoduje to wyraźne spowolnienie programu (mnożenie trwa). Kompilator C++ rozróżnia dwa rodzaje wyrażeń:
* general expressions - wyrażenia ogólne - zawierające zmienne i wywołania funkcji, których wartości nie jest w stanie określić na etapie kompilacji
* constant expressions - wyrażenia stałe, których wartość można wyznaczyć na etapie kompilacji.
Zapis
wynik = 2 * x * 3.14;
możesz zatem przekształcić do postaci
wynik = 2 * 3.14 * x;
Kompilator przekształci to wyrażenia na etapie kompilacji do postaci
wynik = 6.28 * x;
co spowoduje zmniejszenie ilości operacji w ruchu programu. Aby ułatwić takie działanie kompilatora trzeba umieścić stałe obok siebie.
4