Analiza complexitatii algoritmilor – o abordare practica

Am scris o aplicatie ce urmareste executia unei aplicatii, inregistrand cat dureaza executia unor functii pe masura ce primesc diversi parametrii.

Cum o putem folosi pentru a analiza complexitatea unui algoritm?

Luam ca exemplu problema: sa se afiseze cate numere prime exista mai mici decat n.

Pasul 1

Implementam algoritmul sub forma unor functii (in acest caz cea mai banala & ineficienta implementare):

bool isPrimeNumber(unsigned int value)
{
   if (value < 2)
   {
	  return false;
   }
   for (unsigned int i = 2; i < value; i++)
   {
	  if ((value % i) == 0)
	  {
		 return false;
	  }
   }
   return true;
}

unsigned int countPrimeNumbers(unsigned int until)
{
   unsigned int result = 0;
   for (unsigned int i = 1; i <= until; i++)
   {
	  if (isPrimeNumber(i))
	  {
		 result += 1;
	  }
   }
   return result;
}

Pasul 2

Definim o functie ce apeleaza functia countPrimeNumbers.
Functia aceasta trebuie sa aibe semnatura void functionToMonitor(unsigned int)

void functionToMonitor(unsigned int n)
{   
   printf("%d prime numbers until %d\r\n", countPrimeNumbers(n), n);
}

Pasul 3

Din main() apelam functia monitorizata cu diverse valori ale parametriilor

for (size_t i = 5; i < 255; i += 10)
{
   functionToMonitor(i);
}

Pasul 4

Compilam programul pe 32 bit cu Visual Studio in Debug mode, fara optimizari, avand grija sa nu stergem fisierul .pdb generat pe langa executabil.

Pasul 5

Pornim aplicatia mea si alegem executabilul obtinut.

Pasul 6

Alegem modul de inregistare. Aplicatia suport doua astfel de moduri:

• Numara instructiunile executate. Acest mod este indicat atunci cand executia algoritmului pentru o anumita intrare este foarte scurta, altfel, din cauza modului de inregistrare, poate dura foarte mult. Functii externe precum printf() NU sunt contorizate.
  
• Inregistreaza timpul scurs in mod utilizator. Acest mod functioneaza doar daca executia functiei dureaza cel putin cateva sute de milisecunde, altfel avand precizie scazuta (returnand chiar 0). Acest mod inregistreaza strict timpul in care aplicatia lucreaza, nu si cand astepta dupa disc sau alte evenimente.

Pasul 7

Exportam rezultatele, trasam un grafic si calculam un trendline.

De exemplu, in cazul numararii instructiunilor pentru algoritmul de mai sus aplicat pe intervalul [5, 245], rezultatele arata in felul urmator:

 prime_counter-instructions.png   40,88K   111 download-uri
 prime_counter-instructions-graph.png   19,49K   121 download-uri

In cazul aceluiasi algoritm, dar aplicat pe intervalul [10 000 - 200 000], cu a 2-a metoda de inregistrare, rezultatele arata in felul urmator:

 prime_counter-user_time.png   40,42K   103 download-uri
 prime_counter-user_time-graph.png   19,19K   70 download-uri

Pasul 8

Tragem concluzia: asa cum era de asteptat, in cazul algoritmului de mai sus, timpul necesar executiei creste la patrat pe masura ce creste valoarea de intrare.


Cerinte sistem pentru rularea programului:

• Windows 7 sau mai nou
  
• Visual C++ Redistributable for Visual Studio 2015

Enjoy

 Complexity Analysis.zip   2,6MB   17 download-uri

Editat de dani.user, 26 decembrie 2015 - 17:19.

Mi-a mers doar după ce am șters .dll-ul ăla .

Am testat pe ceva mai „la mișto”:

void weirdstuff(unsigned int n)
{
	for (size_t i = 0; i < n; i++)
	{
		for (size_t j = 1; j < 9999; j++)
			sqrt(i*j);
   }
}

Cam asta am obținut folosind nr de instrucțiuni (a durat enooooorm pt [5,18] cu increment 1), o funcție liniară, frumoasă.
 sqrt1.png   24,85K   93 download-uri

La durată, în schimb, au fost niște rezultate mai urâte.
 Duration.png   21,1K   93 download-uri

Editat de adrian93, 26 decembrie 2015 - 20:13.

Dureaza prea putin pentru a fi precisa masurarea "duratei". Respectiva metoda "se uita la ceas" odata la cateva milisecunde (nu controlez eu perioada) si e indicata doar cand dureaza macar cateva sute de ms executia functiei.

Daca las al doilea for pana la 10 merge decent cu prima varianta.
Daca il cresc la 9999999 iese ok si a 2-a metoda (dureaza cam 1.5s pentru n = 5 si 5.3s pentru n = 17)

Editat de dani.user, 26 decembrie 2015 - 21:07.

Nu exista un profiler in VisualStudio ce iti masoara tot ce misca?

Exista dar nu-i precis la operatii foarte scurte si trebuie sa-l rulezi manual pentru fiecare input ca altfel iti pune timpii la gramada/functie/operatie.