Analiza complexitatii algoritmilor – o abordare practica
Last Updated: Mar 17 2016 17:03, Started by
dani.user
, Dec 26 2015 17:06
·
0
#1
Posted 26 December 2015 - 17:06
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:
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 downloads prime_counter-instructions-graph.png 19.49K 121 downloads 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 downloads prime_counter-user_time-graph.png 19.19K 70 downloads 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:
Enjoy Complexity Analysis.zip 2.6MB 17 downloads Edited by dani.user, 26 December 2015 - 17:19. |
#3
Posted 26 December 2015 - 20:11
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 downloads La durată, în schimb, au fost niște rezultate mai urâte. Duration.png 21.1K 93 downloads Edited by adrian93, 26 December 2015 - 20:13. |
#4
Posted 26 December 2015 - 20:54
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) Edited by dani.user, 26 December 2015 - 21:07. |
#5
Posted 17 March 2016 - 13:27
Nu exista un profiler in VisualStudio ce iti masoara tot ce misca?
|
#6
Posted 17 March 2016 - 17:03
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.
|
Anunturi
Bun venit pe Forumul Softpedia!
▶ 0 user(s) are reading this topic
0 members, 0 guests, 0 anonymous users