Problema eficienta algoritm

[•ucc_5]

Am o problema foarte ciudata. Am o problema in care trebuie sa folosesc ciurul lui eratostenes.
Problema e ca daca verific numerele pana la n (nu pana la sqrt(n)) merge bine, dar daca scriu undeva la inceput int lim=n, si verific numerele pana la lim (practic acelasi lucru) atunci programul imi merge cu muuuuult mai incet.
adica asta
int lim=n;
for (i=3; i<=lim; i+=2)

[•toni2007]

Posteaza si tu sursa, nu prea avem cum sa ne dam seama asa.

[•ucc_5]

Asta merge greu :

Cod:

void ciur (char *p)
{  long i,j,aux=sqrt(n);
   for (i=3; i<=aux; i+=2)
   if (p[i]==0)
    for (j=i+i+i; j<=n; j+= i<<1)
     p[j]=1;    
}

Asta merge repede :

Cod:

void ciur (char *p)
{  long i,j;
   for (i=3; i<=sqrt(n); i+=2)
   if (p[i]==0)
    for (j=i+i+i; j<=n; j+= i<<1)
     p[j]=1;    
}

[editat de moderator] ce zici de tagul "code"?

[•alexandru92]

Acum nu stiu cum ai initializat vectorul, dar n-ar trebuie sa fie ceva de genu p[ i ]=='0', p[j]='1';
ps: mergi pana la  i*i <= n, e mai eficient dacat sa apelezi sqrt(n)

[•toni2007]

Cu cat merge mai greu ? Daca e vorba de 20-30 de milisecunde, e de la procesor. Daca rulezi un proces de mai multe ori, o sa vezi ca o sa obtii timpi foarte diferiti.

[•ucc_5]

Pai spre exemplu am avut o problema pe infoarena, nu mai stiu exact care, si o modalitate de a o rezolva era folosind ciurul lui eratostenes, si folosind varianta slaba mi se pare ca imi iesea cu peste 100ms, pe unele teste poate chiar mai mult ca banuiesc ca daca scrie 150 ms nici nu si-a mai batut capul evaluatorul cu asa ceva.
Dar mi se pare totusi un paradox, treaba asta. Adica nu inteleg ce ar putea face el de merge asa greu in varianta teoretic mai rapida. adica la algoritmul teoretic incet calculeaza in plus sqrt(n) de ... sqrt(n) ori, pe cand il cel teoretic rapid il calculeaza doar odata. Si sincer sa fiu m-ar oftica rau intr-un concurs sa mi se intample asa ceva.
P.S.: vectorul era defapt global, am initializat de forma cu int *p, si da, stiu si de varianta cu i*i, dar teoretic varianta cu aux=sqrt(n), ar trebui sa fie si mai rapida.

[•alexandru92]

Am testat cele 2 surse pe  ubuntu si au aproape acelasi timp de executie.
Am luat n=1000000;

[•wefgef]

Problema despre care vorbesti este Divizori. Hai ca incerc sa iti mai explic o data:
 
Ciurul lui Eratostene se foloseste pentru a determina toate numerele prime intre 1 si N. Are complexitatea O(N log log N). Poti citi mai multe aici: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Pentru a determina factorii primi ai unui numar, poti sa folosesti un algoritm foarte simplu pe care ti l-am schitat in topicul problemei Divizori. Acel algoritm are complexitatea O(sqrt(N)).

Nu stiu cum ai ajuns tu la concluzia ca poti folosi ciurul pentru a rezolva Divizori, sau de unde ai dedus tu ca ar fi mai rapid.

[•ucc_5]

Deci hai sa clarificam 2 lucruri :
1. Eu nu am intrebat special pentru problema divizori, ci in general, ca sa zicem mi se intampla pentru alt algoritm acelasi lucru si eu pierd puncte degeaba.
2. Am inteles faza la problema aia, si nu am ajuns singur la concluzia ca asa se face problema, eu am facut asa, pentru ca acelasi mod de rezolvare era explicat la o problema identica cu "subproblema de la divizor" data la etapa judeteana din 2005 parca; deci probabil stia ceva profesorul ala (chiar daca stia cam prost, ca acum stiu ca nu a gandit bine modul de rezolvare cu ciurul) daca a propus subiectul la judeteana si asa a dat rezolvarea. Oricum am vazut ca e mai bine cum zici tu, ca oricum complexitatea e cam aceeasi. Inca ceva ca sa nu par prost, algoritmul ala pe care "mi l-ai schitat" cred ca e primul algoritm care se preda la informatica, deci nu e o minune pentru mine 
P.S. : alexandru daca e iti dau problema divizori sa o testezi ca la ea am avut problema, o fi strict legat de problema respectiva, dar evaluatorul de la infoarena banuiesc ca e destul de bun, deci timpul de executie a fost corect.

[•alexandru92]

P.S. : alexandru daca e iti dau problema divizori sa o testezi ca la ea am avut problema, o fi strict legat de problema respectiva, dar evaluatorul de la infoarena banuiesc ca e destul de bun, deci timpul de executie a fost corect.

Pe infoarena evaluare se face sub linux, deci timpii de executie sunt foarte precisi, dar, poate la afisarea in borderou sa fie o mica greseala ...