|
Titlul: strlen in for Scris de: Campeanu Vlad din Mai 22, 2012, 18:43:51 Am o functie liniara, strlen de exemplu, si un sir S de lungime N.
Cod: for (int i = 0; i < strlen(S); i++) La fiecare iteratie se calculeaza din nou strlen(S) ? Adica o parcurgere a sirului o sa fie in O(N^2) ? Titlul: Răspuns: strlen in for Scris de: George Marcus din Mai 22, 2012, 19:03:11 Da. De aceea e de preferat sa retii valoarea inainte.
Titlul: Răspuns: strlen in for Scris de: MciprianM din Mai 22, 2012, 21:01:53 Pe cazul general, cand ai o functie O (n), care se apeleaza intr-un for cum ai scris tu, intr-adevar se calculeaza de n ori.
Totusi in cazul functiei strlen, exista unele compilatoare de C/C++ care fac o optimizare si calculeaza valoarea acestei functii o singura data. Vezi aici: http://ridiculousfish.com/blog/posts/will-it-optimize.html (http://ridiculousfish.com/blog/posts/will-it-optimize.html) Atentie la versiunile de compilatoare si optiunile date la compilare! Titlul: Răspuns: strlen in for Scris de: Savin Tiberiu din Mai 23, 2012, 17:41:55 Nu cred ca e bine sa optimizeze in cazul asta deoarece valoarea se poate schimba.
De ex cand faci un BF din nodul 1: Cod: vector<int> v; In cazul de fata vrei ca in primul for, valoarea lui v.size() sa se recalculeze de fiecare data deoarece se schimba. Titlul: Răspuns: strlen in for Scris de: Simoiu Robert din Mai 23, 2012, 17:57:55 Da, dar vectorul din STL si STL in general nu cred ca are complexitatea lui strlen, adica liniara. Cred ca v.size () e constant.
Titlul: Răspuns: strlen in for Scris de: MciprianM din Mai 23, 2012, 19:02:56 @Tiberiu Savin
M-am gandit si eu la ce se intampla daca lungimea sirului variaza. Intr-adevar, in acel caz, valoarea nu va fi corecta daca va fi inlocuita de o constanta. Cand am vazut intrebarea lui Campeanu Vlad mi-am amintit ca am citit despre aceasta optimizare si de aceea am vrut sa arat ca strlen poate fi scos de compilator (poate ca sa se optimizeze strlen trebuie specificate ceva optiuni suplimentare?). Un alt caz in care se face o optimizare nedorita este atunci cand folosesti variabile care nu isi modifica valoarea initiala "in raza de vizibilitate" a compilatorului. Si de aceea trebuie sa folosesti volatile (http://en.wikipedia.org/wiki/Volatile_variable)daca nu vrei ca variabila ta sa fie inlocuita de o constanta. Titlul: Răspuns: strlen in for Scris de: Campeanu Vlad din Mai 23, 2012, 19:32:34 @ Marginean Ciprian
Evaluatorul de pe infoarena nu optimizeaza strlen. http://infoarena.ro/job_detail/750315 http://infoarena.ro/job_detail/750319 In a doua sursa am 2 variabile pentru cate un strlen si le-am folosit pe alea in for. E diferenta mare de timpi, deci chiar e bine de stiut si recomandat sa calculezi inainte valoarea, cine stie cum poti sa bulesti o problema aiurea. Pentru STL m-am uitat pe cplusplus si size() e constanta. Titlul: Răspuns: strlen in for Scris de: Laurentiu Ion din Mai 23, 2012, 23:54:51 size() nu este inlocuit de o constanta, si nici nu este o valoare constanta, dar este calculata in timp constant.
Titlul: Răspuns: strlen in for Scris de: Adrian Budau din Mai 24, 2012, 08:54:57 size() e o functie inline. Compilatorul inlocuieste toate aparitiile cu ceva de genul (_M_end - _M_begin) unde cele 2 variabile sunt de tip pointer. O scadere -> timp constant.
Titlul: Răspuns: strlen in for Scris de: HighScore din Mai 30, 2012, 02:24:27 Se poate face optimizarea si pentru strlen, chiar daca exista riscul sa poata varia dimensiune sirului (folosind taint checking[1]) . Dar pare o bataie prea mare de cap, cand pur si simplu ar putea utilizatorul sa scrie o linie de cod in plus.
http://en.wikipedia.org/wiki/Taint_checking |