Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: strlen in for  (Citit de 2472 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
vld7
Strain


Karma: 7
Deconectat Deconectat

Mesaje: 17



Vezi Profilul
« : 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) ?
Memorat
PlayLikeNeverB4
Nu mai tace
*****

Karma: 212
Deconectat Deconectat

Mesaje: 721



Vezi Profilul
« Răspunde #1 : Mai 22, 2012, 19:03:11 »

Da. De aceea e de preferat sa retii valoarea inainte.
Memorat
MciprianM
Nu mai tace
*****

Karma: 87
Deconectat Deconectat

Mesaje: 324



Vezi Profilul
« Răspunde #2 : 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

Atentie la versiunile de compilatoare si optiunile date la compilare!
Memorat
devilkind
Echipa infoarena
Nu mai tace
*****

Karma: 284
Deconectat Deconectat

Mesaje: 1.240



Vezi Profilul
« Răspunde #3 : 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;
v.push_back(1)
for (int i = 0; i < v.size(); i++) {
   for (int j = 0; j < vecini[v[i]]; j++) {
     int vecin = vecini[v[i]][j]
     if (!viz[vecin]) {
        vecin.push_back(vecin)
     }
   }
}

In cazul de fata vrei ca in primul for, valoarea lui v.size() sa se recalculeze de fiecare data deoarece se schimba.
Memorat
SpiderMan
Nu mai tace
*****

Karma: -463
Deconectat Deconectat

Mesaje: 937



Vezi Profilul
« Răspunde #4 : 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.
Memorat
MciprianM
Nu mai tace
*****

Karma: 87
Deconectat Deconectat

Mesaje: 324



Vezi Profilul
« Răspunde #5 : 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 daca nu vrei ca variabila ta sa fie inlocuita de o constanta.
Memorat
vld7
Strain


Karma: 7
Deconectat Deconectat

Mesaje: 17



Vezi Profilul
« Răspunde #6 : 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.
Memorat
laurion
De-al casei
***

Karma: -41
Deconectat Deconectat

Mesaje: 102



Vezi Profilul
« Răspunde #7 : 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.
Memorat
freak93
Echipa infoarena
Nu mai tace
*****

Karma: 342
Deconectat Deconectat

Mesaje: 819



Vezi Profilul
« Răspunde #8 : 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.
Memorat
skyel
Nu mai tace
*****

Karma: 29
Deconectat Deconectat

Mesaje: 263



Vezi Profilul
« Răspunde #9 : 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
Memorat
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines