Programarea Calculatoarelor

Lucrarea nr. 1

Determinarea experimentala a timpului de execuţie al unui program

1. Scopul lucrării - lucrarea prezintă aspecte legate de diferite modalitaţi de determinare experimentală a timpilor de execuţie pentru diferite secvenţe de program.

2. Aspecte teoretice

2.1. Determinarea experimentală a timpului de execuţie al unui program

Determinarea timpului de execuţie al unui program prin metode analitice este foarte dificilă în practică. Aşa ca mai exista si o alta metoda experimentală, mult mai uşoară, şi cu rezultate la fel de concludente în condiţiile în care se porneşte de la anumite premize iniţiale. Ideea acestei metode constă din determinarea timpului efectiv (în secunde, milisecunde, etc.) necesar rulării unui algoritm, folosindu-ne de ceasul calculatorului. Se prezintă mai jos schema bloc a acestei metode.

Ideea acestui algoritm este aceea de a determina, folosindu-se ceasul calculatorului, două momente de timp : dinaintea inceputului algoritmului şi respectiv imediat de dupa terminarea acestuia. Rezultatul, ca fiind diferenţa între cele două momente, este considerat ca fiind timpul de execuţie efectiv al algoritmului respectiv.

Este cunoscut faptul că, în general, timpul de execuţie al unui program depinde de următorii factori :

-volumul datelor de intrare

-calitatea codului generat de compilator

-natura si viteza de execuţie a instrucţiunilor programului (dependentă şi de performanţele calculatorului pe care acesta rulează)

-complexitatea algoritmului care stă la baza programului.

In condiţiile în care algoritmii sunt rulaţi pe calculatoare cu performanţe similare, utilizîndu-se acelaşi compilator, practic timpul de execuţie devine funcţie doar de volumul datelor de intrare şi complexitatea algoritmului. In aceste condiţii simplificate, evaluarea experimentală a performanţelor unui algoritm este cu adevarat relevantă.

In C++, funcţia prin care se poate determina ora curentă a calculatorului este gettime, şi se găseşte în bibioteca <dos.h>

2.2. Exemplu de determinarea experimentala a timpului de executie al unui program

Se prezintã în continuare modul de evaluare a timpului de execuþie a procedurii de sortare a elementelor unui tablou de dimensiune N utilizînd algoritmul bubblesort, prezentat mai jos:

typedef int tablou[n];

void bubble_sort(tablou a)

{

int i,j,temp

(1) for (i=0;i<n;i++)

(2) for (j=n;j>=i+1;j--)

(3) if (a[j-1]>a[j])

{

(4) temp=a[j-1];

(5) a[j-1]=a[j];

(6) a[j]=temp

}

}

Dacă dorim să folosim metoda experimentală, şi să utilizăm funcţia gettime, programul se va modifica astfel:

typedef int tablou[n];

void bubble_sort(tablou a)

{

int i,j,temp

for (i=0;i<n;i++)

for (j=n;j>=i+1;j--)

if (a[j-1]>a[j])

{

temp=a[j-1];

a[j-1]=a[j];

a[j]=temp

}

}

void main()

{

(1) struct time t1,t2;

int durata;

(2) gettime(&t1);

(3) bubble_sort(a);

(4) gettime(&t2);

(5) durata=(t2.ti_sec*100+t2.ti_hund)

-(t1.ti_sec*100+t1.ti_hund);

printf("Durata de executie=%dms",durata);

}

Trebuie ţinut cont însă de faptul că funcţia gettime are nevoie ca şi parametri de variabile de tip structură de timp, deci în cazul nostru vom avea nevoie de două variabile t1 şi t2 în care să se stocheze ora calculatorului (1). Se stochează ora calculatorului în t1, exact înainte de a rula algoritmul (2). Se rulează algoritmul (3) dupa care, imediat se stochează în t2 ora calculatorului (4). Pentru obţinerea diferenţei se va realiza un mic calcul matematic pentru diferenţa între cei doi timpi t2 şi t1 (5), iar rezultatul final obţinut va fi durata de execuţie în sutimi de secunda.

Utilizînd aceasta metodă experimentală de determinare a timpului de execuţie, rezultatul se obţine mult mai uşor, fiindu-ne oferit chiar de calculator, în comparaţie cu metoda analitică, unde tot calculul trebuie realizat manual de catre programator, şi care implică, în anumite cazuri, cunoştinţe aprofundate de matematică. Este adevărat că metoda analitică este mai generală.