Memorie/complexitate

[•Dddarius95]

Salut. Poate sa-mi explice careva care e diferenta intre memorie si memoria pentru stiva? si cum le calculez pe amandoua....
de la o anumita complexitate O(f(n)) , cum as sti pentru un n dat la ce timp  ma duce (de ce ordin- cateva sute de ms , secunde etc)?
Multumesc !

[•fdproxy]

Memoria e impartita in mai multe zone. De interes, in general, este stiva (stack) si free-store (heap).

Stiva este bucata de memorie in care alocarea se face pe principiul LIFO (last-in-first-out). Poti privi stiva ca un teanc de cutii inalt cat o camera (dimensiunea maxima); cand ai nevoie de o variabila locala (automata) iei ultima cutie, o stivuiesti alaturi si tot asa cu urmatoarele variabile. La iesirea din blocul de executie cutiile sunt puse, automat, inapoi in stiva initiala in ordine inverse (daca ai lua prima cutie, stiva s-ar darma). Alocarea variabilelor din stiva este foarte rapida (trebuie doar sa iei cutia urmatoare; nu cauti).
int fun()
{
  int i; // i este alocata
  for ( int j = 0 /* j este alocata */; j < 10; ++j )
  {
    //…
  } // j este dealocata
  // ...
} // i este dealocata


Memoria dinamica (heap sau free store) este zona de memorie din care alocare/dealocarea se face prin intermediul unui manager (new/delete). Este ca un raft in care ai cutii goale. Cand ai nevoie de o variabila, o ceri managerului (new) iar managerul cauta o cutie goala de dimensiunea ceruta. Cautarea ia mai mult timp decat in cazul stivei, dar heap-ul este mult mai mare decat stiva. Existenta variabilei nu se incheie in mod automat: daca nu mai ai nevoie de ea, trebuie s-o pui inapoi in heap (delete).

Variabilele globale nu sunt alocate pe stiva sau heap; este folosita o zona de memorie dedicata. In c++ utilizarea variabilelor globale este descurajata.

In privinta vitezei, cred ca ar trebui sa te preocupe corectitudinea implementarii, iar daca viteza este alta decat cea asteptata, abia atunci sa-ti pui problema optimizarilor.


Succes.

[•wefgef]

Variabilele globale nu sunt alocate pe stiva sau heap; este folosita o zona de memorie dedicata. In c++ utilizarea variabilelor globale este descurajata.

Asa este, dar concursurile de programare sunt alta mancare de peste. Daca vei scrie codul conform standardelor acceptate in programare uneori vei fi ineficient.

[•Dddarius95]

si pentru complexitate ?
eu programez in pascal:d

[•fdproxy]

Daca vei scrie codul conform standardelor acceptate in programare uneori vei fi ineficient.

Nu am participat la vreun concurs, asa ca nu-mi pot da cu parerea, dar: daca concursul este despre algoritmi si este analizata altceva in afara complexitatii algoritmului, atunci ceva nu-i in regula. Una e sa folosesti un ciclu pentru a calcula suma primelor 100 de numere si alta e sa folosesti formula lui Gauss. In primul caz poti folosi orice artificiu de programare, ca nu vei ajunge la performantele formulei. Nu pot fi de acord cu: "scrie-l oricum, numai sa fie rapid". Aplicatiile reale sunt mari si astfel de "solutii" duc la cod greu de intretinut/inteles si in final la aplicatii ratate. Viteza nu trebuie sa vina din artificii de programare, ci din algoritm. Artificiile de programare adauga un plus de viteza si ininteligibilitate, de cele mai multe ori.

Ce ma nemultumeste total este tendinta profeorilor de a lucra cu mijloace invechite. Angajatorii nu asta asteapta. Doar un exemplu: iostream.h in loc de iostream, asa cum prevede standardul curent.

[•fdproxy]

si pentru complexitate ?
eu programez in pascal:d

Nu am folosit Pascal de foarte mult timp. Pot spune ca nu mai stiu nimica. In general, din punctul de vedere al complexitatii algoritmului, ar trebui sa le vezi la fel. In realitate alocarea pe heap necesita un timp mai mare (ce nu poate fi controlat de client). Imagineaza-ti ca ai un raft de cutii inchise si-ti trebuie o cutie goala; stii ca exista, dar nu stii unde: poate-i prima, poate-i ultima.

[•wefgef]

Nu am participat la vreun concurs, asa ca nu-mi pot da cu parerea, dar: daca concursul este despre algoritmi si este analizata altceva in afara complexitatii algoritmului, atunci ceva nu-i in regula.

Si eu sunt de acord ca in general toate programele implementate corect care au complexitatea dorita de autori ar trebui sa obtina punctaj maxim. Prin ineficienta eu ma refeream la efortul/timpul necesar implementarii.

Nu pot fi de acord cu: "scrie-l oricum, numai sa fie rapid".

Nu programul trebuie sa fie rapid, ci timpul de implementare sa fie scurt. Un sfat pe care l-am primit in liceu (nu mai tin minte de la cine) era sa scriu cea mai scurta sursa care trece toate testele . Toata povestea asta despre cum e cel mai bine sa implementezi in regim concurs este extrem de subiectiva, si daca ne uitam pe TopCoder la cei mai buni din lume vedem stiluri complet diferite. Totusi, exista lucruri care in programarea reala sunt descurajate, dar care apar foarte des prin sursele concurentilor de la concursurile de programare. Exemple bune ar fi existenta variabilelor globale, sau folosirea excesiva a STL-ului.

Aplicatiile reale sunt mari si astfel de "solutii" duc la cod greu de intretinut/inteles si in final la aplicatii ratate. Viteza nu trebuie sa vina din artificii de programare, ci din algoritm. Artificiile de programare adauga un plus de viteza si ininteligibilitate, de cele mai multe ori.

Desigur, doar ca unui olimpic ii va fi extrem de usor sa scrie cod bun . Nu trebuie invinuite competitiile de algoritmi, care uneori incurajeaza "artificiile".

Ce ma nemultumeste total este tendinta profeorilor de a lucra cu mijloace invechite. Angajatorii nu asta asteapta. Doar un exemplu: iostream.h in loc de iostream, asa cum prevede standardul curent.

Inertie mare, interes mic, etc.