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 # include # include # 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 i * 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.