Diferente pentru 12-ponturi-pentru-programatorii-cc intre reviziile #2 si #18

Nu exista diferente intre titluri.

Diferente intre continut:

h1. 12 ponturi pentru programatorii C/C++
 
(Creat de '_domino_':user/domino la data de _2004-11-08_ categoria _Limbaje_, autor(i) _Alexandru Mosoi_)
 
*Continut scurt:*
 In urmatoarele cateva randuri am sa incerc sa va arat cateva metode de a scrie.... mai bine. Cea mai mare parte este pentru programatorii C.
 
Inainte ati putea citi si "Documentation/CodingStyle" aflat in sursa de kernel a Linux-ului. Scuzati-ma daca ma inspir putin. Manualul gcc este si el binevenit.
 
 
*Continut lung:*
In urmatoarele cateva randuri am sa incerc sa va arat cateva metode de a scrie.... mai bine. Cea mai mare parte este pentru programatorii C.
 
Inainte ati putea citi si "Documentation/CodingStyle" aflat in sursa de kernel a Linux-ului. Scuzati-ma daca ma inspir putin. Manualul gcc este si el binevenit.
 
0
 
Prefer C in loc de C++: e mai robust putin ceea ce ma fereste cateodata de greseli. Incercati sa nu folositi un IDE cu debugging inclus (cum ar fi RHIDE sau Borland C++ 3.1). La inceput o sa va vina greu, dar va obisnuiti... si deveniti mai atenti cand scrieti surse. Puteti sa folositi Kate, un editor de text asemanator lui EditPlus de sub Windows. Vim este deasemenea un editor foarte puternic, dar pentru cine stie sa-l foloseasca.
 
1
 
Impartiti programul dumneavoastra in functii, fiecare sa nu depaseasca mai mult de 30-50 de linii (aproximativ 2 ecrane ANSI 80x25). Este important sa aveti mereu o viziune asupra intregii functii. Regula este: complexitatea unei functii trebuie sa fie invers proportionala cu lungimea ei. Puteti sa declarati functiile "inline" (nu pe toate !) pentru a nu pierde din viteza.
 
2
 
Macro-urile nu le recomand. Daca le folositi ca functii aveti grija. Unul dintre colegii mei de la lot a pierdut multe puncte pentru ceva asemanator.
 
#define MAX(a, b) ((a) < (b) ? (b) : (a))
 
 
 
int query(int a, int b)
{
int k, l, r;
 
....
res = MAX(k, query(l, r));
....
 
return res;
}
 
Daca observati, exista cazuri cand query(l, r) era apelata de 2 ori, ceea ce nu se doreste. In schimb, putea sa declare MAX ca o functie inline.
 
inline int MAX(int a, int b)
{
if(a > b) return a;
return b;
}
 
3
 
Cand accesati un element din memorie, procesorul citeste de fapt 32 bytes (sau cat de mare e linia de cache, dar o putere a lui 2). Recomand ca structurile voastre sa aiba de asemenea ca dimensiune o putere a lui 2 pentru a nu forta procesorul sa citeasca de 2 ori. O extensie GNU a standardului ANSI C sunt atributele. Pentru structuri, una din cele mai folosite (de mine) este packed ce instruieste compilatorul se nu mai adauge "padding bytes".
 
struct foo { int a; char b; int c; };
/* sizeof(struct foo) == 12 */
struct bla { int a; char b; int c; }
 
__attribute__((packed));
/* sizeof(struct bla) == 9 */
 
Pentru mai multe informatii executati consultati manualul gcc. ("info gcc").
 
a
 
De asemenea, e bine sa nu spargeti aceasta line de cache prea des. Uitati un exemplu:
 
#define maxN 1000
#define maxM 1000
 
 
 
int t[maxN][maxM];
 
int f(void)
{
int i, j;
int s = 0;
for(i = 0; i < maxM; ++ i)
for(j = 0; j < maxN; ++ j)
s += t[j][i];
return s;
}
 
Pentru 1024 de apelari, pe calculatorul meu, acesta functie consuma cam 18.85s. In schimb, daca as fi scris
 
for(i = 0; i < maxN; ++ i)
for(j = 0; j < maxM; ++ j)
s += t[i][j];
 
... functia s-ar fi executat de ~3 ori mai repede (doar 6.05s) iar rezultatul era acelasi. De ce? pentru ca in primul caz la fiecare accesare a t[j][i] procesorul era nevoit sa acceseze memoria, iar in cazul al doilea cand citea t[i][j], erau citite de fapt si t[i][j+1], t[i][j+2], t[i][j+3]. Si sa nu uitam viteza memoriei este mult mai mica decat cea a procesorului.
 
 
 
4
 
Variabilele globale sa nu fie folosite in scop local. Daca as modifica functia astfel
 
int i, j;
 
int f(void)
{
int s = 0;
for(i = 0; i < maxM; ++ i)
for(j = 0; j < maxN; ++ j)
s += t[i][j];
}
 
... timpul de executie s-ar fi marit la 6.44s. Nu e prea mult... dar se aduna.
 
5
 
Stack-ul (locul unde se pastreaza toate variabilele locale) este foarte rapid. Modificam acelasi program astfel:
 
#define maxN 1000
#define maxM 1000
 
int main(void)
{
int i, j, k;
int N, M, t[maxN][maxM];
 
N = maxN; M = maxM;
 
 
 
for(k = 0; k < 1024; ++ k) {
int s;
for(i = 0; i < N; ++ i)
for(j = 0; j < M; ++ j)
s += t[i][j];
}
 
 
 
return 0;
}
 
Ignorand faptul ca t nu este initializat (e doar un program de test, nici inainte nu era :D) timpul de executie scade la 1.2s, Wow! Insa aveti grija sa nu o luati pe urmele lui Silviu: sizeof(t) ~= 4Mb care e mult peste limita de 1Mb ce se impune de obicei in concursuri (si asta daca folositi gcc). Cel mai probabil veti primi "Killed by signal 11".
 
a
 
++ i e preferabil i ++ (unde nu complica lucrurile).
 
b
 
Nu va feriti sa folositi "const" si "static". "Const" chiar poate sa faca diferenta ca timp si vizibilitate.
 
c
 
Utilizati si literele mari pentru anumite variabile mai importante (poate si macro-uri).
 
 
 
7
 
O alta extensie GNU sunt "zero-length arrays". Se folosesc in general la skiplist-uri pentru a declara un array de dimensiune variabila intr-o structura.
 
typedef struct bla bla;
 
struct bla {
int levels;
bla *next[0];
};
 
...
 
bla *temp = (bla *)malloc(sizeof(bla)
 
+ no_levels*sizeof(bla *));
 
8
 
a
 
Folositi-va de utilitarele puse la dispozitie de sistemul de operare (linux in cazul meu). RTFM :)
 
* bc - pentru calcule cu numere cu precizie multipla (eg. 2^1024).
* octave - pentru calcule matematice mai complicate.
* gprof - determina cat timp a necesitat executia fiecarei functii sau linii.
* gcov - determina de cateori a fost apelata o anumita linie.
* time - pentru aflarea timpului executiei unui program.
* factor - descompune in factori un numar (eg. factor 666).
* splint - o versiune free a programului lint: va da foarte multe warning-uri.
* bash - putin scripting
 
b
 
Compilati-va sursele cu -W -Wall (tot pentru warning-uri)
 
c
 
Generatorul de teste si sursa dumneavoastra trebuie sa fie doua programe diferite !
 
d
 
Pentru debugging folositi fprintf(stderr, ...). Daca se intampla sa uitati, macar nu primiti "wrong answer" din cauza unui printf.
 
9
 
a
 
int t[666];
 
 
 
/* toate elementele lui t vor fi -1 */
 
memset(t, 0xff, sizeof(t));
 
b
 
Pentru valoarea infinit folosesc o constanta
 
#define INFI 0x3f3f3f3f
 
din mai multe motive:
 
* INFI + INFI ramane pozitiv
* in general e destul de mare
 
/* toate elementele lui t devin INFI */
 
memset(t, 0x3f, sizeof(t));
 
c
 
Daca avem de comparat doua siruri (s1, s2) a caror lungime o stim (len_s1, respectiv len_s2) este mai rapid
 
memcmp(s1, s2, MIN(len_s1, len_s2)+1)
 
decat
 
strcmp(s1, s2);
 
d
 
scanf(" %c", &ch) citeste primul caracter dupa spatiile albe (daca exista).
 
 
 
10
 
Daca programati in C++ fara sa folositi STL incercati sa renuntati la C++. Unul dintre motive: clasele (implicit iostream: cin, cout, cerr) incetinesc mult executia programului.
 
11
 
In final, o intrebare pentru cei ce folosesc C++ (asta e un hint). Cum se calculeaza factorial la compilare? (fara a scrie efectiv 1*2*3...*n)
 
Raspuns
 
Utilizand templaturi. Avem nevoie doar de o constanta N.
 
#include <stdio.h>
 
 
 
template<int N>
 
struct Factorial {
enum {
 
value = Factorial<N-1>::value * N
 
};
};
 
 
 
template<>
struct Factorial<0> {
enum { value = 1 };
};
 
 
 
int main(void)
{
int i = Factorial<4>::value;
char c[Factorial<5>::value];
 
printf("%d ",i);
printf("%d ",sizeof(c));
}
 
PS: nu dau $2.56 pentru fiecare greseala descoperita in acest articol.
 
h1. 12 ponturi pentru programatorii C/C++
 
(Categoria _Limbaje de programare_, Autor _Alexandru Mosoi_)
 
In urmatoarele cateva randuri am sa incerc sa va arat cateva metode de a scrie.... mai bine. Cea mai mare parte este pentru programatorii C.
 
Inainte ati putea citi si "Documentation/CodingStyle" aflat in sursa de kernel a Linux-ului. Scuzati-ma daca ma inspir putin. Manualul gcc este si el binevenit.
 
 
h2. Pont #0
 
Prefer C in loc de C++: e mai robust putin ceea ce ma fereste cateodata de greseli. Incercati sa nu folositi un IDE cu debugging inclus (cum ar fi RHIDE sau Borland C++ 3.1). La inceput o sa va vina greu, dar va obisnuiti... si deveniti mai atenti cand scrieti surse. Puteti sa folositi Kate, un editor de text asemanator lui EditPlus de sub Windows. Vim este deasemenea un editor foarte puternic, dar pentru cine stie sa-l foloseasca.
 
h2. Pont #1
 
Impartiti programul dumneavoastra in functii, fiecare sa nu depaseasca mai mult de 30-50 de linii (aproximativ 2 ecrane ANSI 80x25). Este important sa aveti mereu o viziune asupra intregii functii. Regula este: complexitatea unei functii trebuie sa fie invers proportionala cu lungimea ei. Puteti sa declarati functiile "inline" (nu pe toate !) pentru a nu pierde din viteza.
 
h2. Pont #2
 
Macro-urile nu le recomand. Daca le folositi ca functii aveti grija. Unul dintre colegii mei de la lot a pierdut multe puncte pentru ceva asemanator.
 
== code(cpp) |#define MAX(a, b) ((a) < (b) ? (b) : (a))
 
int query(int a, int b)
{
    int k, l, r;
    ...
    res = MAX(k, query(l, r));
    ....
    return res;
}
==
 
Daca observati, exista cazuri cand $query(l, r)$ era apelata de $2$ ori, ceea ce nu se doreste. In schimb, putea sa declare $MAX$ ca o functie inline.
 
== code(cpp)|inline int MAX(int a, int b)
{
    if(a > b)
        return a;
    return b;
}
==
 
h2. Pont #3
 
Cand accesati un element din memorie, procesorul citeste de fapt $32$ bytes (sau cat de mare e linia de cache, dar o putere a lui {$2$}). Recomand ca structurile voastre sa aiba de asemenea ca dimensiune o putere a lui $2$ pentru a nu forta procesorul sa citeasca de $2$ ori. O extensie GNU a standardului ANSI C sunt atributele. Pentru structuri, una din cele mai folosite (de mine) este packed ce instruieste compilatorul se nu mai adauge "padding bytes".
 
== code(cpp) |struct foo { int a; char b; int c; };
/* sizeof(struct foo) == 12 */
struct bla { int a; char b; int c; }
 
__attribute__((packed));
/* sizeof(struct bla) == 9 */
==
 
h3. Update
 
Se pare ca pentru ultimele versiuni ale compilatorului aceasta recomandare nu mai este valabila. Structurile de date de dimensiuni 2^k^ au tendinta de a incetini executia programului.
'Sursa 1':http://infoarena.ro/job_detail/371232
'Sursa 2':http://infoarena.ro/job_detail/371233
 
 
Pentru mai multe informatii executati consultati manualul gcc. ("info gcc").
 
De asemenea, e bine sa nu spargeti aceasta line de cache prea des. Uitati un exemplu:
 
== code(cpp) |#define maxN 1000
#define maxM 1000
 
int t[maxN][maxM];
 
int f(void)
{
    int i, j;
    int s = 0;
    for(i = 0; i < maxM; ++ i)
        for(j = 0; j < maxN; ++ j)
            s += t[j][i];
    return s;
}
==
 
Pentru $1024$ de apelari, pe calculatorul meu, acesta functie consuma cam {$18.85$}s. In schimb, daca as fi scris
 
== code(cpp)|for(i = 0; i < maxN; ++ i)
    for(j = 0; j < maxM; ++ j)
        s += t[i][j];
==
 
... functia s-ar fi executat de ~{$3$} ori mai repede (doar {$6.05$}s) iar rezultatul era acelasi. De ce? pentru ca in primul caz la fiecare accesare a $t[j][i]$ procesorul era nevoit sa acceseze memoria, iar in cazul al doilea cand citea {$t[i][j]$}, erau citite de fapt si {$t[i][j+1]$}, {$t[i][j+2]$}, {$t[i][j+3]$}. Si sa nu uitam viteza memoriei este mult mai mica decat cea a procesorului.
 
h2. Pont #4
 
Variabilele globale sa nu fie folosite in scop local. Daca as modifica functia astfel
 
== code(cpp) |int i, j;
 
int f(void)
{
    int s = 0;
    for(i = 0; i < maxM; ++ i)
        for(j = 0; j < maxN; ++ j)
            s += t[i][j];
    return s;
}
==
 
... timpul de executie s-ar fi marit la {$6.44$}s. Nu e prea mult... dar se aduna.
 
h2. Pont #5
 
Stack-ul (locul unde se pastreaza toate variabilele locale) este foarte rapid. Modificam acelasi program astfel:
 
== code(cpp) |#define maxN 1000
#define maxM 1000
 
int main(void)
{
    int i, j, k;
    int N, M, t[maxN][maxM];
    N = maxN; M = maxM;
    for(k = 0; k < 1024; ++ k) {
        int s;
        for(i = 0; i < N; ++ i)
            for(j = 0; j < M; ++ j)
                s += t[i][j];
    }
    return 0;
}
==
 
Ignorand faptul ca $t$ nu este initializat (e doar un program de test, nici inainte nu era :D) timpul de executie scade la {$1.2$}s, Wow! Insa aveti grija sa nu o luati pe urmele lui Silviu: {$sizeof(t)$} ~= {$4$}Mb care e mult peste limita de {$1$}Mb ce se impune de obicei in concursuri (si asta daca folositi gcc). Cel mai probabil veti primi "Killed by signal 11".
 
h2. Pont #6
 
h3. 6.a
 
{$++i$} e preferabil in locul lui {$i ++$} (unde nu complica lucrurile).
 
h3. 6.b
 
Nu va feriti sa folositi "{$const$}" si "{$static$}". "{$const$}" chiar poate sa faca diferenta ca timp si vizibilitate.
 
h3. 6.c
 
Utilizati si literele mari pentru anumite variabile mai importante (poate si macro-uri).
 
h2. Pont #7
 
O alta extensie GNU sunt "zero-length arrays". Se folosesc in general la skiplist-uri pentru a declara un array de dimensiune variabila intr-o structura.
 
== code(cpp) |typedef struct bla bla;
struct bla {
    int levels;
    bla *next[0];
};
...
bla *temp = (bla *)malloc(sizeof(bla) + no_levels*sizeof(bla *));
==
 
h2. Pont #8
 
h3. 8.a
 
Folositi-va de utilitarele puse la dispozitie de sistemul de operare (linux in cazul meu). RTFM :)
 
* $bc$ - pentru calcule cu numere cu precizie multipla (eg. {$2^1024^$}).
* $octave$ - pentru calcule matematice mai complicate.
* $gprof$ - determina cat timp a necesitat executia fiecarei functii sau linii.
* $gcov$ - determina de cateori a fost apelata o anumita linie.
* $time$ - pentru aflarea timpului executiei unui program.
* $factor$ - descompune in factori un numar (eg. factor {$666$}).
* $splint$ - o versiune free a programului lint: va da foarte multe warning-uri.
* $bash$ - putin scripting
 
h3. 8.b
 
Compilati-va sursele cu {$-W -Wall$} (tot pentru warning-uri)
 
h3. 8.c
 
Generatorul de teste si sursa dumneavoastra trebuie sa fie doua programe diferite !
 
h3. 8.d
 
Pentru debugging folositi {$fprintf(stderr, ...)$}. Daca se intampla sa uitati, macar nu primiti "wrong answer" din cauza unui {$printf$}.
 
h2. Pont #9
 
h3. 9.a
 
== code(cpp)|int t[666];
/* toate elementele lui t vor fi -1 */
memset(t, 0xff, sizeof(t));
==
 
h3. 9.b
 
Pentru valoarea infinit folosesc o constanta
 
== code(cpp)|#define INFI 0x3f3f3f3f
==
 
din mai multe motive:
 
* $INFI + INFI$ ramane pozitiv
* in general e destul de mare
 
== code(cpp)|/* toate elementele lui t devin INFI */
memset(t, 0x3f, sizeof(t));
==
 
h3. 9.c
 
Daca avem de comparat doua siruri ({$s{~1~}, s{~2~}$}) a caror lungime o stim ({$len_s{~1~}$}, respectiv {$len_s{~2~}$}) este mai rapid
 
== code(cpp) |memcmp(s1, s2, MIN(len_s1, len_s2)+1)
==
 
decat
 
== code(cpp) |strcmp(s1, s2);
==
 
h3. 9.d
 
== code(cpp)|scanf(" %c", &ch)
==
 
citeste primul caracter dupa spatiile albe (daca exista).
 
 
 
h2. Pont #10
 
Daca programati in C++ fara sa folositi STL incercati sa renuntati la C++. Unul dintre motive: clasele (implicit iostream: cin, cout, cerr) incetinesc mult executia programului.
 
h2. Pont #11
 
In final, o intrebare pentru cei ce folosesc C++ (asta e un hint). Cum se calculeaza factorial la compilare? (fara a scrie efectiv {$1*2*3...*n$})
Raspuns: Utilizand templaturi. Avem nevoie doar de o constanta {$N$}.
 
== code(cpp) |#include <stdio.h>
 
template<int N>
struct Factorial {
    enum {
        value = Factorial<N-1>::value * N
    };
};
 
template<>
struct Factorial<0> {
    enum { value = 1 };
};
 
int main(void)
{
    int i = Factorial<4>::value;
    char c[Factorial<5>::value];
    printf("%d ",i);
    printf("%d ",sizeof(c));
}
==
 
PS: nu dau $2.56 pentru fiecare greseala descoperita in acest articol.

Nu exista diferente intre securitate.

Diferente intre topic forum:

 
3674