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