Eficienţa algoritmilor

-Aveam de realizat un proiect cu tema "Eficienţa algoritmilor". Primul lucru pe care l-am făcut a fost următorul: am luat dicţionarul explicativ al limbii române şi am căutat cuvântul eficienţă. Scrie acolo :"ceea ce produce efectul aşteptat (pozitiv)".

Să luăm doi algoritmi care realizează acelaşi lucru. Ei sunt eficienţi: conduc la acelaşi rezultat scontat, însă primul algoritm este mai rapid decât celălalt, deci este MAI EFICIENT.

Înţelegem de aici că eficienţa se poate cuantifica din simplul motiv că oricând şi oriunde e loc de mai bine. Aceasta este şi întreaga filosofie a unui programator bun.

Dar...destul cu filosofia - să luăm nişte exemple concrete.

Interesat fiind în urmă cu ceva vreme de encoderele audio, am testat câteva dint re ele, în scopul dezvoltarii unei aplicaţii. Dintre ele se remarcă trei: encoderul LAME (Lame Ain't an Mp3 Encoder), FRAUNHOFER şi Xing.

-LAME, dezvoltat de comunitatea OpenSource este disponibil sub licenta GPL, este destul de rapid (in forma lame.exe), dar are rezultate mai slăbuţe în forma lame_enc.dll, iar calitatea encodingului este acceptabilă. Ca un punct în minus, LAME_enc.dll nu acceptă ca fişiere de intrare decât cele ce au "sample rate-ul" de 32000 , 44100 sau 48000 Khz.

-FRAUNHOFER encodează cu o viteză bună , raportată la o calitate excelentă a materialului audio generat, însă nu este disponibil gratuit.

-Pe de altă parte, Xing este liderul la capitolul viteză, dar calitatea audio lasă de dorit.

-Priviţi ca trei algoritmi distincţi, ei sunt eficienţi pentru că realizează acelaşi lucru (encodează wav în mp3), dar observăm că Fraunhofer este cel mai eficient.

-Ce trebuie să înţelegem din acest exemplu ? Ei bine, se pare că nu numai timpul de execuţie al algoritmului este factorul decisiv în categorisire, ci se pare că mai putem lua în considerare şi calitatea. Aş mai putea adăuga din proprie experienţă cum că viteza/consum de resurse ar fi de asemenea un factor important.

Exemplu de ilustrare a eficienţei algoritmilor de sortare implementat în limbajul C++

Programul permite compararea timpului de execuţie a trei dintre algoritmii standard de sortare: sortarea prin metoda bulelor (sau selecţie) , sortarea prin inserţie şi sortarea Shell. Se dă un vector k ce se va unple cu N numere întregi aleatoare. Puteţi testa timpul de execuţie pentru fiecare algoritm în parte, dând programului numărul de elemente ale vectorului, sau puteţi efectua un test complet (in care se vor folosi toate cele trei metode pe un vector cu 10000 de elemente generate aleator). La final se va afişa timpul de execuţie al fiecărei metode în bătăi de ceas intern şi secunde.

Pentru a asigura o testare cât mai aproape de adevăr şi pentru a elimina diferenţele de caz (favorabil - nefavorabil) determinate de generarea aleatoare se va genera o singură dată vectorul cu numere aleatoare, pentru ca după terminarea sortării cu o metodă, structura vectorului să fie restaurată.

Recomand alegerea unei dimensiuni a vectorului de peste 3000 de elemente pentru un calculator Pentium 200MHz sau mai bun, pentru un test edificator. Dimensiunea maximă a vectorului poate fi de 60000 de elemente.

/*
(c) 2002 Lucian Sabo
Exemplu de testare a eficientei pentru trei dintre algoritmii de sortare standard:
- bubble sort
- insertie
- shell
*/
#include <iostream.h>
#include <stdio.h>
#include <conio.h>
#include <time.h>
#include <stdlib.h>
clock_t t0,t1;
int k[60000],n,i,v,p,opt,k_salvat[60000],t_bule,t_insertie,t_shell;
//=================================================
void insertie()
{
int c=0;
cout<<"Sortez vectorul...";
t0=clock(); //citeste timpul initial (referinta)
//Sortare prin insertie
for(i=2;i<=n;i++)
{
// Insereaza Ki
v=k[i];
p=i-1;
while(p>0 && k[p]>v) // sa fie ordonat crescator
{
k[p+1]=k[p];
p=p-1;
}
k[p+1]=v;
if(c==n/60){ //progresul operatiei
c=0; //reseteaza contorul (s-a afisat o steluta)
cout<<"*";
}
c++; //incrementeaza contorul ce se reseteaza dupa afisarea unei stelute de progres
} //endfor
cout<<"OK\n";

cout<<"Vectorul a fost sortat cu metoda de sortare prin insertie"<<endl;
t1=clock(); //citeste timpul final

cout<<"Sortarea a durat "<<(t1-t0)<<" batai de ceas intern --> aproximativ "<<(t1-t0)/CLK_TCK<<" secunde !\n\n";
t_insertie=t1-t0;
}
//=================================================
void bubble_sort()
{
cout<<"Sortez vectorul...";
t0=clock(); //citeste timpul initial (referinta)
int aux,c=0;
for(i=1;i<n;i++)
{
for(int j=i+1;j<=n;j++)
if(k[i]>k[j]) { aux=k[i]; k[i]=k[j];k[j]=aux; }
if(c==n/60){ //progresul operatiei
c=0; //reseteaza contorul (s-a afisat o steluta)
cout<<"*";
}
c++; //incrementeaza contorul ce se reseteaza dupa afisarea unei stelute de progres
}
cout<<"OK\n";
cout<<"Vectorul a fost sortat cu metoda bulelor (bubble-sort)"<<endl;
t1=clock(); //citeste timpul final

cout<<"Sortarea a durat "<<(t1-t0)<<" batai de ceas intern --> aproximativ "<<(t1-t0)/CLK_TCK<<" secunde !\n\n";
t_bule=t1-t0;
}
//==================================================
void shell()
{
cout<<"Sortez vectorul...\n";
t0=clock(); //citeste timpul initial (referinta)
int gap=n/2,aux,modificari;
do
{
do
{
modificari=0;
for(i=1;i<n-gap;i++){
if(k[i]>k[i+gap])
{
aux=k[i];
k[i]=k[i+gap];
k[i+gap]=aux;
modificari=1;
}
}

} while (modificari);
} while(gap=gap/2);
cout<<"Vectorul a fost sortat cu metoda de sortare Shell"<<endl;
t1=clock(); //citeste timpul final

cout<<"Sortarea a durat "<<(t1-t0)<<" batai de ceas intern --> aproximativ "<<(t1-t0)/CLK_TCK<<" secunde !\n\n";
t_shell=t1-t0;
}
//==================================================
void salvare_vector()
{
/*operatie utila pentru testarea eficientei metodelor in aceleasi conditii
Se aplica fiecare metoda pentru aceeasi structura si aceeasi componentză a vectorului k*/
cout<<"Salvez asezarea elementelor in vector...\n";
for(i=1;i<=n;i++)
k_salvat[i]=k[i];
}
//==================================================
void restaurare_vector()
{
/*Restaureaza asezarea elementelor in vector
Vectorul inainte de apelul acestei functii este sortat*/
cout<<"Restaurez asezarea elementelor in vector...\n";
for(i=1;i<=n;i++)
k[i]=k_salvat[i];
}

//==================================================
void meniu()
{
clrscr();//functia sterge ecranul

cout<<"Exemplu de testare a eficientei pentru trei dintre algoritmii de sortare standard:"<<endl;
cout<<"- Bubble-sort\n- Sortare prin Insertie\n- Sortare Shell\n";
cout<<"(c) 2002 Lucian Sabo \"Universitatea Valahia Targoviste\""<<endl<<endl;
cout<<"Vectorul test va fi umplut cu numere intregi generate aleator\n";
cout<<"Pentru testarea optima a fiecarei sortari se recomanda alegerea unei dimensiuni a vectorului de peste 3000 elemente\n";
cout<<"In cazul testului complet se va lua ca dimensiune a vectorului 10000 de elemente\n\n";
//desenez meniul
cout<<"1.Test complet\n2.Bubble-sort\n3.Sortare prin insertie\n4.Sortare Shell\n5.Iesire\n\nOptiunea dvs:";
cin>>opt; //citesc optiunea
clrscr(); //sterg ecranul
}
//===================================================
void test_complet()
{
cout<<"Generez vectorul cu 10000 nr intregi aleatoare...\n";
//numarul de elemente ale vectorului este setat la 10000
n=10000;
//se genereaza elementele vectorului k (nr. intregi aleatoare)
for(i=1;i<=n;i++)
{
k[i]=rand();
}
//se salveaza vectorul inainte de a fi sortat
//se aplica apoi fiecare algoritm de sortare
salvare_vector();
bubble_sort();
cout<<"Apasati orice tasta...";
getch();

//se restaureaza starea vectorului k initial (nesortata)
restaurare_vector();
insertie();
cout<<"Apasati orice tasta...";
getch();

restaurare_vector();
shell();
cout<<"Apasati orice tasta...\n\n";
getch();
cout<<"Timpi de executie algoritmi de sortare:\n\n";
cout<<"Algoritmul de sortare 'Shell' : aproximativ "<<t_shell/CLK_TCK<<" secunde\n";
cout<<"Algoritmul de 'Sortare prin Insertie' : aproximativ "<<t_insertie/CLK_TCK<<" secunde\n";
cout<<"Algoritmul 'Bubble-sort' : aproximativ "<<t_bule/CLK_TCK<<" secunde\n\n";
}
//====================================================
main()
{
do
{
meniu(); //desenare ecran principal + meniu
/*daca optiunea nu e 1(Test complet) sau 5(Iesire), ci o valoarea intre aceste doua
se citeste numarul de elemente si apoi se genereaza elementele vectorului*/
if(opt>1 && opt<5 ){
cout<<"Cƒte elemente are vectorul:";cin>>n;
cout<<"Generez vectorul cu nr intregi aleatoare...\n";
for(i=1;i<=n;i++)
{
k[i]=rand(); //nr intregi aleatoare
}
}

//in functie de valoarea introdusa ca optiune (opt)
switch(opt){
case 1:test_complet();break;
case 2:bubble_sort();break;
case 3:insertie();break;
case 4:shell();break;
case 5:exit(0);
default:"Atentie nu ati specificat o optiune valida!\n";break;
}

//afisare vector sortat
cout<<"Afisez primele 10 elemente din noua structura a vectorului..."<<endl;
for(i=1;i<=10;i++)
printf("k[%d]=%d\n",i,k[i]);

cout<<"Apasati orice tasta...";
getch();

}
while(opt!=5); //programul se termina la alegerea optiunii 5 (Iesire)
/*Iesirea propriu-zisa se face in switch() cu exit(0), conditia de iesire din acest
do while nefiind niciodata un motiv de terminare a programului*/
}