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.