Optimizarea programelor folosind operaţii pe biţi

Operaţii pe biţi

h1. Optimizarea programelor folosind operaţii pe biţi

h1. Operaţii pe biţi

== include(page="template/implica-te/scrie-articole" user_id="GheorgheMihai") ==

* 'Aplicaţia 4':operatii-pe-biti#aplicatia-4
* 'Aplicaţia 5':operatii-pe-biti#aplicatia-5
* 'Aplicaţia 6':operatii-pe-biti#aplicatia-6

* 'O altă abordare: preprocesarea':operatii-pe-biti#preprocesare
* 'Rezolvarea aplicaţiei 1':operatii-pe-biti#aplicatia-p1
* 'Rezolvarea aplicaţiei 2':operatii-pe-biti#aplicatia-p2
* 'Rezolvarea aplicaţiei 3':operatii-pe-biti#aplicatia-p3
* 'Rezolvarea aplicaţiei 4':operatii-pe-biti#aplicatia-p4
* 'Rezolvarea aplicaţiei 5':operatii-pe-biti#aplicatia-p5
* 'Algoritmi mai serioşi':operatii-pe-biti#algoritmi

* 'Preprocesare':operatii-pe-biti#preprocesare
* 'Preprocesare aplicatia 1':operatii-pe-biti#aplicatia-p1
* 'Preprocesare aplicatia 2':operatii-pe-biti#aplicatia-p2
* 'Preprocesare aplicatia 3':operatii-pe-biti#aplicatia-p3
* 'Preprocesare aplicatia 4':operatii-pe-biti#aplicatia-p4
* 'Preprocesare aplicatia 5':operatii-pe-biti#aplicatia-p5
* 'Algoritmi mai seriosi':operatii-pe-biti#algoritmi

* 'Ciurul lui Eratostene':operatii-pe-biti#ciur
* 'Bibliografie':operatii-pe-biti#bibliografie

De cele mai multe ori, atât în concursuri cât şi în viaţa de zi cu zi a programatorului, atunci când implementăm o metodă care este folosită de o aplicaţie şi vrem să facem această metodă eficientă ca timp de execuţie, suntem învăţaţi din şcoală (sau ar trebui sã fim învăţaţi, chiar dacă unii dintre profesori consideră că cel mai important algoritm învăţat în liceu este _backtraking_-ul, soluţia tuturor problemelor) să ne uităm la complexitatea algoritmului implementat şi dacă observăm că în practică algoritmul este mai încet decât ne dorim noi să fie să încercăm să găsim un algoritm cu un ordin de complexitate mai mic.

Nu trebuie să uităm că ceea ce numim complexitatea unui algoritm este o aproximare a vitezei unui algoritm şi nu o măsură absolută. Pentru dimensiuni mici ale datelor, câteodată nu se observă diferenţă dintre $O(n)$ şi $O(n log n)$ sau $O(n^3/2^)$. Autorului i s-a întâmplat ca la implementarea soluţiei unei probleme care în engleză se numeşte "_Bottleneck Minimal Spanning Tree_" să observe că rezolvarea în $O(m log m)$ (folosind algoritmul de găsire a arborelui parţial de cost minim al lui Kruskal) să fie mai rapidă decât rezolvarea mai laborioasă în $O(m)$ a acestei probleme. Deci trebuie dată o atenţie egală cu cea acordată complexităţii algoritmului şi dimensiunii factorilor constanţi care apar.

Nu trebuie să uităm că ceea ce numim complexitatea unui algoritm este o aproximare a vitezei unui algoritm şi nu o măsură absolută. Pentru dimensiuni mici ale datelor, câteodată nu se observă diferenţă dintre $O(n)$ şi $O(n · log n)$ sau $O(n^3/2^)$. Mie personal mi s-a întâmplat ca la implementarea soluţiei unei probleme care în engleză se numeşte "_Bottleneck Minimal Spanning Tree_" să observ că rezolvarea în $O(m · log m)$ (folosind algoritmul de găsire a arborelui parţial de cost minim al lui Kruskal) să fie mai rapidă decât rezolvarea mai laborioasă în $O(m)$ a acestei probleme. Deci trebuie dată o atenţie egală cu cea acordată complexităţii algoritmului şi dimensiunii factorilor constanţi care apar.

În continuare vom încerca să găsim soluţii mai rapide decât cele naive pentru unele operaţii de bază (toate operaţiile vor fi implementate pentru întregi pozitivi reprezentaţi pe 32 de biţi).

Rezolvarea naivă a acestei probleme ar consta în parcurgerea secvenţială a biţilor lui n. În continuare vă prezint această rezolvare:
==code(cpp)|

int count(long n) {
    int num = 0;
    for (int i = 0; i < 32; i++)
        if (n & (1 << i)) num++;
    return num;

int count(long n){
  int num = 0;
  for (int i = 0; i < 32; i++)
     if (n & (1 << i)) num++;
  return num;

}
==
Dacă ne uităm cu atenţie şi analizăm rezultatul operaţiei $n & (n - 1)$ putem obţine o soluţie mai bună. Să luăm un exemplu:

$n           = 11011101010000{~2~}$
$n - 1       = 11011101001111{~2~}$
$n & (n - 1) = 11011101000000{~2~}$

$11011101010000{~2~} = n$
$11011101001111{~2~} = n - 1$
$11011101000000{~2~} = n & (n - 1)$
 
Se vede clar de aici că efectul operaţiei $n & (n - 1)$ este anularea celui mai nesemnificativ bit cu valoarea $1$.
 

Se vede clar de aici că efectul operaţiei $n & (n - 1)$ este anularea celui mai nesemnificativ bit cu valoarea 1.

De aici ideea algoritmului:

==code(cpp)|

int count(long n) {
    int num = 0;
    if (n)
        do num++; while (n &= n - 1);
    return num;

int count(long n){
   int num = 0;
   if (n)
      while (n &= n - 1) num++;
   return num;

}
==

Dar este acest algoritm mai rapid? Am testat pentru toate numerele de la $1$ la $2^24^$ şi rezultatele au fost $2,654$ secunde folosind metoda naivă şi $0.821$ folosind a doua metodă. Rezultatul mult mai bun al celei de-a doua metode se bazează în principal pe faptul că ea execută un număr de paşi egali cu numărul de biţi cu valoarea 1 din număr, deci în medie jumătate din numărul de paşi efectuaţi de prima metodă.

Dar este acest algoritm mai rapid? Am testat pentru toate numerele de la $1$ la $2^24^$ şi rezultatele au fost $2,654$ secunde folosind metoda naivă şi $0.821$ folosind a doua metodă.
Rezultatul mult mai bun al celei de-a doua metode se bazează în principal pe faptul că ea execută un număr de paşi egali cu numărul de biţi cu valoarea 1 din număr, deci în medie jumătate din numărul de paşi efectuaţi de prima metodă.

h2(#aplicatia-2). Aplicaţia #2

Din cele prezentate mai sus se pot determina două metode evidente:
==code(cpp)|

int parity(long n) {
    int num = 0;
    for (int i = 0; i < 32; i++)
        if (n & (1 << i)) num ^= 1;
    return num;

int parity(long n){
  int num = 0;
  for (int i = 0; i < 32; i++)
     if (n & (1 << i)) num ^= 1;
  return num;

}
==
==code(cpp)|

int parity(long n) {
    int num = 0;
    if (n)
        do num ^= 1; while (n &= n - 1);
    return num;

int parity(long n){
   int num = 0;
   if (n)
      while (n &= n - 1) num ^= 1;
   return num;

}
==

Putem obţine o a treia rezolvare făcând câteva observaţii pe un exemplu. Considerăm $n = 11011011{~2~}$. Rezultatul căutat este dat de valoarea $1 ^ 1 ^ 0 ^ 1 ^ 1 ^ 0 ^ 1 ^ 1$. Împărţim pe $n$ în partea lui superioară şi partea lui inferioară: $1 1 0 1 ^ 1 0 1 1 = 0 1 1 0$. Aplicăm asupra rezultatului acelaşi procedeu: $0 1 ^ 1 0 = 1 1$ şi $1 ^ 1 = 0$.

Putem obţine o a treia rezolvare făcând câteva observaţii pe un exemplu:
Considerăm $n = 11011011{~2~}$. Rezultatul căutat este dat de valoarea @1 ^ 1 ^ 0 ^ 1 ^ 1 ^ 0 ^ 1 ^ 1@.
Împărţim pe n în partea lui superioară şi partea lui inferioară:
1 1 0 1 ^ 1 0 1 1 = 0 1 1 0
Aplicăm asupra rezultatului acelaşi procedeu:
0 1 ^ 1 0 = 1 1
şi
1 ^ 1 = 0

Să scriem algoritmul care reiese din acest exemplu, luând în considerare faptul că numărul n este reprezentat pe 32 de biţi:

==code(cpp)|

int parity(long n) {
    n = ((0xFFFF0000 & n) >> 16) ^ (n & 0xFFFF);
    n = ((0xFF00 & n) >> 8) ^ (n & 0xFF);
    n = ((0xF0 & n) >> 4) ^ (n & 0xF);
    n = ((12 & n) >> 2) ^ (n & 3);
    n = ((2 & n) >> 1) ^ (n & 1);
    return n;

int parity(long n){
   n = ((0xFFFF0000 & n) >> 16) ^ (n & 0xFFFF);
   n = ((0xFF00 & n) >> 8) ^ (n & 0xFF);
   n = ((0xF0 & n) >> 4) ^ (n & 0xF);
   n = ((12 & n) >> 2) ^ (n & 3);
   n = ((2 & n) >> 1) ^ (n & 1);
   return n;

}
==

h3. Rezolvare
Rezolvarea naivă se comportă bine în medie, deoarece numărul de cicluri până la găsirea unui bit cu valoarea 1 este de obicei mic, dar din cele discutate mai sus putem găsi ceva mai bun.

Asa cum am arătat $n & (n - 1)$ are ca rezultat numărul $n$ din care s-a scăzut cel mai puţin semnificativ bit. Folosind această idee obţinem următoarea funcţie:

==code(cpp)|

int low1(long n) {
    return n ^ (n & (n - 1));

int low1(long n){
   return n ^ (n & (n - 1));

}
==
Exemplu:

$n                 = 11011000{~2~}$
$n-1               = 11010111{~2~}$
$n & (n - 1)       = 11010000{~2~}$
$n                 = 11011000{~2~}$
$n ^ (n & (n - 1)) = 00001000{~2~}$

$11011000{~2~} = n$
$11010111{~2~} = n - 1$
$11010000{~2~} = n & (n - 1)$
$11011000{~2~} = n$
$00001000{~2~} = n ^ (n & (n - 1))$
 
Această funcţie este foarte importantă pentru structura de date 'arbori indexaţi binar':problema/aib prezentată într-un un articol mai vechi din 'GInfo':http://www.ginfo.ro/revista/13_1/focus.pdf.

Această funcţie este foarte importantă pentru structura de date 'Arbori Indexaţi Binar':problema/aib prezentată într-un un articol mai vechi din 'GInfo':http://www.ginfo.ro/revista/13_1/focus.pdf.

h2(#aplicatia-4). Aplicaţia #4

h3. Rezolvare
Putem aplica şi aici ideile prezentate mai sus: cea naivă şi cea cu eliminarea biţilor, dar putem găsi şi ceva mai bun.

 
O abordare ar fi cea a căutării binare (aplicabilă şi în problema anterioară). Verificăm dacă partea superioară a lui $n$ este $0$. Dacă nu este $0$, atunci căutăm bitul cel mai semnificativ din ea, iar dacă este, ne ocupăm de partea inferioară, deci reducem la fiecare pas problema la jumătate.
 

O abordare ar fi cea a căutării binare (aplicabilă şi în problema anterioară). Verificăm dacă partea superioară a lui n este 0. Dacă nu este 0, atunci căutăm bitul cel mai semnificativ din ea, iar dacă este, ne ocupăm de partea inferioară, deci reducem la fiecare pas problema la jumătate.

==code(cpp)|
int high1(long n) {

    long num = 0;
    if (!n) return -1;
    if (0xFFFF0000 & n) {
        n = (0xFFFF0000 & n)>>16;
        num += 16;
    }
    if (0xFF00 & n) {
        n = (0xFF00 & n) >> 8;
        num += 8;
    }
    if (0xF0 & n) {
        n = (0xF0 & n) >> 4;
        num += 4;
    }
    if (12 & n) {
        n = (12 & n) >> 2;
        num += 2;
    }
    if (2 & n) {
        n = (2 & n) >> 1;
        num += 1;
    }
    return 1 << num;

   long num = 0;
   if (!n) return -1;
   if (0xFFFF0000 & n) {
     n = (0xFFFF0000 & n)>>16;
     num += 16;
   }
   if (0xFF00 & n) {
      n = (0xFF00 & n) >> 8;
      num += 8;
   }
   if (0xF0 & n) {
      n = (0xF0 & n) >> 4;
      num += 4;
   }
   if (12 & n) {
      n = (12 & n) >> 2;
      num += 2;
   }
   if (2 & n) {
      n = (2 & n) >> 1;
      num += 1;
   }
   return 1 << num;

}
==
h2(#aplicatia-5). Aplicaţia #5
bq. Să se determine indexul celui mai semnificativ bit de 1 din reprezentarea binară a lui $n$.

h3. Rezolvare
Metodele prezentate la rezolvarea problemei 4 pot fi folosite şi aici, dar vom prezenta o nouă rezolvare. Să luăm următorul şir de operaţii pentru un exemplu:

$n = n | (n >> 4)$
$n = 11111111{~2~}$

Se observă că aplicând o secvenţă asemănătoare de instrucţiuni cu cea de mai sus putem face ca un număr $n$ să se transforme în alt număr care are un număr de biţi de $1$ egal cu $1$ plus indexul celui mai semnificativ bit cu valoarea $1$ din $n$. De aici algoritmul este următorul...
 

Se observă că aplicând o secvenţă asemănătoare de instrucţiuni cu cea de mai sus putem face ca un număr $n$ să se transforme în alt număr care are un număr de biţi de 1 egal cu 1 + indexul celui mai semnificativ bit cu valoarea 1 din $n$. De aici algoritmul este următorul:

==code(cpp)|

int indexHigh1(long n) {
    n = n | (n >> 1);
    n = n | (n >> 2);
    n = n | (n >> 4);
    n = n | (n >> 8);
    n = n | (n >> 16);
    return count(n) - 1;
}

int indexHigh1(long n){
  n = n | (n >> 1);
  n = n | (n >> 2);
  n = n | (n >> 4);
  n = n | (n >> 8);
  n = n | (n >> 16);
  return count(n) - 1;

==
Pentru ca această metodă să fie eficientă ne trebuie o metodă *count* eficientă.

bq. Să se determine dacă $n$ este o putere a lui 2 (întrebare interviu Microsoft).

h3. Rezolvare
 

==code(cpp)|

int isTwoPower(long n) {
    return ( n & (n - 1) ) == 0 ;

int isTwoPower(long n){
  return (n & (n-1) == 0);

}
==

h2(#preprocesare). _O altă abordare: preprocesarea_

h2(#preprocesare). O altă abordare: preprocesarea

Operaţiile prezentate mai sus sunt implementate în limbajele de asamblare, dar câteodată se folosesc algoritmi naivi şi atunci o implementare inteligentă ajunge să fie mai rapidă decât instrucţiunea din limbajul de asamblare. Pentru unele supercalculatoare aceste instrucţiuni sunt instrucţiuni ale procesorului.

 
Se pot găsi alţi algoritmi mai rapizi decât cei de mai sus, dar de obicei găsirea unui algoritm mai inteligent este mai grea decât folosirea unei abordări banale care aduce un câştig foarte mare: _preprocesarea_.
 

Se pot găsi alţi algoritmi mai rapizi decât cei de mai sus, dar de obicei găsirea unui algoritm mai inteligent este mai grea decât folosirea unei abordări banale care aduce un câştig foarte mare: preprocesarea.

În continuare vom rezolva problemele prezentate anterior folosindu-ne de preprocesarea datelor.

h3(#aplicatia-p1). Rezolvarea aplicaţiei #1

h3(#aplicatia-p1). Aplicaţia #1

Determinăm, pentru numerele de la $0$ la $2^16^ - 1$, un tablou $num$, în care $num[i]$ este egal cu numărul de biţi de $1$ din reprezentarea binară a lui $i$. De aici obţinem soluţia...

bq. Determinăm, pentru numerele de la 0 la $2^16^ - 1$, un tablou $num$, în care $num[i]$ este egal cu numărul de biţi de 1 din reprezentarea binară a lui $i$.
De aici obţinem soluţia:

==code(cpp)|

int count(long n) {
    return num[n & 0xFFFF] + num[n >> 16];

int count(long n){
  return num[n & 0xFFFF] + num[n >> 16];

}
==

h3(#aplicatia-p2). Rezolvarea aplicaţiei #2

h3(#aplicatia-p2). Aplicaţia #2

Determinăm, pentru numerele de la $0$ la $2^16^ - 1$, un tablou $par$, în care $par[i]$ este egal cu paritatea numărului de biţi de $1$ din reprezentarea binară a lui $i$. De aici obţinem soluţia...

bq. Determinăm, pentru numerele de la 0 la $2^16^ - 1$, un tablou $par$, în care $par[i]$ este egal cu paritatea numărului de biţi de 1 din reprezentarea binară a lui $i$.
De aici obţinem soluţia:

==code(cpp)|

int parity(long n) {
    return par[n & 0xFFFF] ^ par[n >> 16];

int parity(long n){
  return par[n & 0xFFFF] ^ par[n >> 16];

}
==

h3(#aplicatia-p3). Rezolvarea aplicaţiei #3

h3(#aplicatia-p3). Aplicaţia #3

Determinăm, pentru numerele de la $0$ la $2^16^ - 1$, un tablou $l$, în care $l[i]$ este egal cu cel mai nesemnificativ bit de $1$ din reprezentarea binară a lui $i$. De aici obţinem soluţia...

bq. Determinăm, pentru numerele de la 0 la $2^16^ - 1$, un tablou $l$, în care $l[i]$ este egal cu cel mai nesemnificativ bit de 1 din reprezentarea binară a lui $i$.
De aici obţinem soluţia:

==code(cpp)|

int low(long n) {
    if (l[n & 0xFFFF]) return l[n & 0xFFFF];
    else return l[n >> 16] << 16;

int low(long n){
  if (l[n & 0xFFFF]) return l[n & 0xFFFF];
  else return l[n >> 16] << 16;

}
==

h3(#aplicatia-p4). Rezolvarea aplicaţiei #4

h3(#aplicatia-p4). Aplicaţia #4

Determinăm, pentru numerele de la $0$ la $2^16^ - 1$, un tablou $h$, în care $h[i]$ este egal cu cel mai semnificativ bit de $1$ din reprezentarea binară a lui $i$. De aici obţinem soluţia...

bq. Determinăm, pentru numerele de la 0 la $2^16^ - 1$, un tablou $h$, în care $h[i]$ este egal cu cel mai semnificativ bit de 1 din reprezentarea binară a lui i.
De aici obţinem soluţia:

==code(cpp)|

int high(long n) {
    if (h[n >> 16]) return h[n >> 16] << 16;
    else return h[n & 0xFFFF];

int high(long n){
  if (h[n >> 16]) return h[n >> 16] << 16;
  else return h[n & 0xFFFF];

}
==

h3(#aplicatia-p5). Rezolvarea aplicaţiei #5

h3(#aplicatia-p5). Aplicaţia #5

Determinăm, pentru numerele de la $0$ la $2^16^ - 1$, un tablou $iH$, în care $iH[i]$ este egal cu indexul celui mai semnificativ bit de $1$ din reprezentarea binară a lui $i$ şi este egal cu $-1$ pentru $0$. De aici obţinem soluţia...

bq. Determinăm, pentru numerele de la 0 la $2^16^ - 1$, un tablou $iH$, în care $iH[i]$ este egal cu indexul celui mai semnificativ bit de 1 din reprezentarea binară a lui $i$ şi este egal cu -1 pentru 0.
De aici obţinem soluţia:

==code(cpp)|
int indexHigh(long n) {

    if (iH[n >> 16] != -1) return iH[n >> 16] + 16;
    else return iH[n & 0xFFFF];

  if (iH[n >> 16] != -1) return iH[n >> 16] + 16;
  else return iH[n & 0xFFFF];

}
==

h2(#algoritmi). _Algoritmi mai serioşi_

h2(#algoritmi). Algoritmi mai serioşi

Deşi ceea ce am prezentat mai sus sunt mai degrabă trucuri de implementare decât algoritmi serioşi şi în general nu se acordă aşa mare importanţă detaliilor de genul acesta, câteodată asemenea trucuri se pot dovedi importante mai ales în timpul concursurilor.

 
Un exemplu ar fi problema rundei 12 de la concursul de programare Bursele Agora. Acolo se cerea găsirea numărului de dreptunghiuri conţinute de o matrice binară $M$ care au în colţuri $1$. Un algoritm de complexitate $O(n^2^m)$ ar fi fost următorul: se consideră fiecare pereche formată din două linii şi se numără câte perechi $(M{~i,k~}, M{~j,k~})$ pentru care $M{~i,k~} = 1$ şi $M{~j,k~} = 1$ există. Fie acest număr $x$. Atunci numărul de dreptunghiuri care au colţurile pe aceste două linii va fi $x(x - 1) / 2$.
 
Un asemenea algoritm ar fi luat numai $64$ de puncte deoarece restricţiile date erau mari $(n ≤ 200, m ≤ 2500)$. Putem rescrie condiţia $M[i][k] == 1 && M[j][k] == 1$ ca şi $M[i][k] ^ M[j][k] == 1$, deci putem modifica rezolvarea anterioară în modul următor...
 

Un exemplu ar fi problema rundei 12 de la concursul de programare Bursele Agora. Acolo se cerea găsirea numărului de dreptunghiuri conţinute de o matrice binară $a$ care au în colţuri 1. Un algoritm de complexitate $O(n^2^ · m)$ ar fi fost următorul: se consideră fiecare pereche formată din două linii şi se numãrã câte perechi ( $a{~i,k~}$, $a{~j,k~}$ ) pentru care $a{~i,k~}$ = 1 şi $a{~j,k~}$ = 1 există. Fie acest număr $x$. Atunci numărul de dreptunghiuri care au colţurile pe aceste două linii va fi $x · (x - 1)$ / 2.
Un asemenea algoritm ar fi luat numai 64 de puncte deoarece restricţiile date erau mari ( $n ≤ 200$ , $m ≤ 2500$ ). Putem rescrie condiţia  a[i][k] $= =$ 1 && a[j][k] $= =$ 1 ca şi ( a[i][k] ^ a[j][k] $= =$ 1 ), deci putem modifica rezolvarea anterioară în modul următor:

==code(cpp)|
pentru fiecare i
  pentru fiecare j > i

    L = M[i] ^ M[j];

    b = a[i] ^ a[j];

  sfârşit pentru
sfârşit pentru

  numaraBitiUnu(L)

  numaraBitiUnu(b)

==

Dacă în loc să păstrăm în $M[i][j]$ un element al matricei binare, păstrăm $16$ elemente, atunci în linia $L$ = $M[i] ^ M[j]$ se efectuează cel mult $2500/16$ calcule în loc de $2500$ de calcule. Acum, ce a rămas de optimizat este metoda _numaraBitiUnu_. Dacă folosim preprocesarea, atunci această metodă va fi compusă şi ea din $2500/16$ calcule. Se observă că în acest fel am mărit viteza de execuţie a algoritmului cu un factor de $16$.
 
Alt exemplu ar fi problema rundei 17. În acea problemă se cere determinarea numărului de sume distincte care se pot obţine folosind nişte obiecte cu valori date folosind fiecare obiect pentru o sumă cel mult o dată. Din nou o rezolvare directă, folosind marcarea pe un şir de valori logice n-ar fi obţinut punctaj maxim. Pentru obţinerea punctajului maxim următoarea idee ar fi putut fi folosită cu succes: şirul de valori logice se condensează într-un şir de întregi reprezentaţi pe $16$ biţi, şi acum actualizarea se face asupra a $16$ valori deodată. Deci şi aici se câştiga un factor de viteză egal cu $8$ (datorită detaliilor de implementare).

Dacă în loc să păstrăm în $a[i][j]$ un element al matricei binare, păstram 16 elemente, atunci în linia $b$ = $a[i] ^ a[j]$ se efectuează cel mult $2500 / 16$ calcule în loc de $2500$ de calcule. Acum ce a rămas de optimizat este metoda numaraBitiUnu. Dacă folosim preprocesarea, atunci această metodă va fi compusă şi ea $2500/16$ calcule. Se observă că în acest fel am mărit viteza de execuţie a algoritmului cu un factor de $16$.

Un al treilea exemplu ar fi problema _Viteza_ de la a 9-a rundă a concursului organizat de _.campion_ anul acesta. Acolo se cerea determinarea celui mai mare divizor comun a două numere binare de cel mult $10 000$ de cifre. După cum se ştie, complexitatea algoritmului de determinare a celui mai mare divizor comun a două numere este logaritmică, acest fapt este adevărat atunci când operaţiile efectuate sunt constante, dar în rezolvarea noastră apar numere mari, deci o estimare a numărului de calcule ar fi $maxn * maxn * log maxn$ (împărţirea are în medie costul $maxn * maxn$ dacă nu implementăm metode mai laborioase). Acest număr este prea mare pentru timpul de rezolvare care ne este cerut. Pentru a evita împărţirea, care este operaţia cea mai costisitoare, putem folosi algoritmul de determinare a celui mai mare divizor comun binar care se foloseşte de următoarele proprietăţi...

Alt exemplu ar fi problema rundei 17. În acea problemă se cere determinarea numărului de sume distincte care se pot obţine folosind nişte obiecte cu valori date folosind fiecare obiect pentru o sumă cel mult o dată. Din nou o rezolvare directă, folosind marcarea pe un şir de valori logice n-ar fi obţinut punctaj maxim. Pentru obţinerea punctajului maxim următoarea idee ar fi putut fi folosită cu succes: şirul de valori logice se condensează într-un sir de întregi reprezentaţi pe $16$ biţi, şi acum actualizarea se face asupra a 16 valori deodată. Deci şi aici se câştiga un factor de viteză egal cu 8 (datorită detaliilor de implementare).

# $cmmdc(a, b) = 2 * cmmdc(a / 2, b / 2)$, dacă $a$ şi $b$ sunt numere pare;
# $cmmdc(a, b) = cmmdc(a, b / 2)$, dacă $a$ este impar;
# $cmmdc(a, b) = cmmdc(a - b, b)$, dacã $a$ este impar, $b$ este impar şi $a$ > $b$.

Un al treilea exemplu ar fi problema Viteza de la a 9-a rundă a concursului organizat de *.campion* anul acesta. Acolo se cerea determinarea celui mai mare divizor comun a două numere binare de cel mult 10000 de cifre. După cum se ştie, complexitatea algoritmului de determinare a celui mai mare divizor comun a două numere este logaritmică, acest fapt este adevărat atunci când operaţiile efectuate sunt constante, dar în rezolvarea noastră apar numere mari, deci o estimare a numărului de calcule ar fi $maxn$ · $maxn$ · $log maxn$ (împărţirea are în medie costul $maxn$ · $maxn$ dacă nu implementăm metode mai laborioase). Acest număr este prea mare pentru timpul de rezolvare care ne este cerut. Pentru a evita împărţirea, care este operaţia cea mai costisitoare, putem folosi algoritmul de determinare a celui mai mare divizor comun binar care se foloseşte de următoarele proprietăţi:
$cmmdc(a, b)$ = 2 * $cmmdc(a / 2, b / 2)$, dacă $a$ si $b$ sunt numere pare;
$cmmdc(a, b)$ = $cmmdc(a, b / 2)$, dacã $a$ este impar;
$cmmdc(a, b)$ = $cmmdc(a - b, b)$, dacã $a$ este impar, $b$ este impar şi $a$ > $b$.

Aplicând acest algoritm numărul de calcule s-a redus la $maxn * log maxn$, dar nici acest număr nu este suficient de mic, şi deci
pentru accelerarea algoritmului folosim ideea utilizată în cele două probleme de mai sus. Împachetăm numărul în întregi, în pachete de câte $30$ de biţi, şi atunci deplasarea la stânga (adică împărţirea la $2$) şi scăderea vor fi de $30$ de ori mai rapide.

Aplicând acest algoritm numărul de calcule s-a redus la $maxn$ · $log maxn$, dar nici acest număr nu este suficient de mic, şi deci
pentru accelerarea algoritmului folosim ideea utilizată în cele două probleme de mai sus. Împachetăm numărul în întregi, în pachete de câte 30 de biţi, şi atunci deplasarea la stânga (adică împărţirea la 2) şi scăderea vor fi de 30 de ori mai rapide.

Să încercăm acum rezolvarea unei probleme în care eficienţa este cea mai importantă, mai importantă decât lizibilitatea codului obţinut. Problema are următorul enunţ...

Să încercăm acum rezolvarea unei probleme în care eficienţa este cea mai importantă, mai importantă decât lizibilitatea codului obţinut. Problema are următorul enunţ:

bq(#ciur). Se consideră un număr $n$. Să se determine numerele prime mai mici sau egale cu $n$, unde $n ≤ 10 000 000$.

bq(#ciur). Se consideră un număr $n$. Să se determine numerele prime mai mici sau egale cu $n$, unde $n$ ≤ 10.000.000.

Practic această problemă ne va fi utilă în testarea rapidă a primalităţii numerelor mai mici sau egale cu $n$.

Putem încerca mai multe rezolvări, dar în practică cea mai rapidă se dovedeşte de obicei cea numită _ciurul lui Eratostene_. Implementarea banală a algoritmului ar fi următoarea:

Putem încerca mai multe rezolvări, dar în practică cea mai rapidă se dovedeste de obicei cea numită ciurul lui Eratostene. Implementarea banală a algoritmului ar fi urmãtoarea:

==code(cpp)|
define maxsize 10000000

char at[maxsize]; // vector de valori logice în care numerele prime vor fi marcate cu 0
int n;

char at[maxsize]; //vector de valori logice în care numerele prime vor fi marcate cu 0

int isPrime(int x) {
    return (!at[x]) ;

int n;
int isPrime(int x){
return (!at[x]) ;

}

void sieve() {
    int i, j;
    memset(at,0,sizeof(at)) ;
    for (i = 2; i <= maxsize; i++) if (!at[i])
        for (j = i + i; j <= maxsize; j += i)
            at[j] = 1; // marcăm toţi multipli lui i ca fiind numere prime

void sieve(){
  int i, j;
  memset(at,0,sizeof(at)) ;
  for (i = 2; i <= maxsize; i++)
     if (!at[i])
       for (j = i + i; j <= maxsize; j += i)
          at[j]=1; //marcam toti multipli lui i ca fiind numere prime

}
==

Observăm că jumătate din timpul folosit de noi la preprocesare este pierdut cu numerele pare. Marcându-le de la început vom putea ignora numerele pare în preprocesare...
 

Observăm că jumătate din timpul folosit de noi la preprocesare este pierdut cu numerele pare. Marcându-le de la început vom putea ignora numerele pare în preprocesare:

==code(cpp)|
#define maxsize 10000000

char at[maxsize];
int n;

 
int isPrime(int x) {
    return (!at[x]) ;

int isPrime(int x){
  return (!at[x]) ;

}

 
void sieve() {
    int i, j;
    memset(at,0,sizeof(at));
    for (i = 4; i <= maxsize; i += 2)
        at[i] = 1;
    for (i = 3; i <= maxsize; i += 2) if (!at[i])
        for (j = i + i + i; j <= maxsize; j += i + i)
            at[j] = 1;

void sieve(){
  int i, j;
  memset(at,0,sizeof(at));
  for (i = 4; i <= maxsize; i += 2)
     at[i] = 1;
  for (i = 3; i <= maxsize; i += 2)
     if (!at[i])
       for (j = i + i + i; j <= maxsize; j += i + i)
          at[j] = 1;

}
==

La marcarea multiplilor numărului prim $i$ toate numerele până la $i * i$ au fost deja marcate deoarece $i * i$ este cel mai mic număr care nu este divizibil cu numere naturale mai mici sau egale cu $i - 1$. Deci, avem o a treia versiune a programului...
 

La marcarea multiplilor numărului prim $i$ toate numerele până la $i · i$ au fost deja marcate deoarece $i · i$ este cel mai mic număr care nu este divizibil cu numere naturale mai mici sau egale cu $i - 1$, deci, avem o a treia versiune a programului:

==code(cpp)|

void sieve() {
    int i, j;
    memset(at,0,sizeof(at));
    for (i = 4; i <= maxsize; i += 2)
        at[i] = 1;
    for (i = 3; i <= maxsize; i += 2) if (!at[i])
        for (j = i * i; j <= maxsize; j += i + i)
            at[j] = 1;

void sieve(){
  int i, j;
  memset(at,0,sizeof(at));
  for (i = 4; i <= maxsize; i += 2)
     at[i] = 1;
  for (i = 3; i <= maxsize; i += 2)
     if (!at[i])
       for (j = i * i; j <= maxsize; j += i + i)
          at[j] = 1;

}
==

Ultima optimizare este optimizarea spaţiului necesar. Într-un tip de date _char_ putem împacheta opt valori logice şi punând un test suplimentar în metoda _isPrime_ putem elimina şi numerele pare, astfel vom avea nevoie de un spaţiu de _16_ ori mai mic.

Ultima optimizare este optimizarea spaţiului necesar. Într-un tip de date char putem împacheta opt valori logice şi punând un test suplimentar în metoda isPrime putem elimina şi numerele pare, astfel vom avea nevoie de un spaţiu de 16 ori mai mic.

==code(cpp)|
#define maxsize 10000000

char at[maxsize / 16];

char at[maxsize/16];

int n;
int isPrime(int x) {

    if (!(x & 1))
        if (x == 2) return 0 ;
        else return 1 ;
        else return (at[((x - 3) >> 1) >> 8] & (1 << (((x - 3) >> 1) & 7))) ;

  if (!(x & 1))
     if (x==2) return 0 ;
     else return 1 ;
     else return (at[((x - 3) >> 1) >> 8] &
                       (1 << (((x - 3) >> 1) & 7))) ;

}

void sieve() {

    int i, j;
    memset(at, 0, sizeof(at)) ;
    for (i = 3; i <= maxsize; i += 2)
        if (!at[((i - 3) >> 1) >> 8] & (1 << (((i - 3) >> 1) & 7)))
            for (j = i * i ; j <= maxsize ; j += i + i)
                at[((i - 3) >> 1) >> 8] |= (1 << (((i - 3) >> 1) & 7))) ;

  int i, j;
  memset(at, 0, sizeof(at)) ;
  for (i = 3; i <= maxsize; i += 2)
     if (!at[((i - 3) >> 1) >> 8] &
                         (1 << (((i - 3) >> 1) & 7)))
       for (j=i * i ; j <= maxsize ; j += i + i)
          at[((i - 3) >> 1) >> 8] |=
                       (1 << (((i - 3) >> 1) & 7))) ;

}
==
h2. Concluzie

Asemenea optimizări ca şi cele prezentate în cadrul acestui articol se pot dovedi foarte utile în unele cazuri, dar ele fac programul ilizibil, tocmai din acest motiv, asemenea trucuri trebuie aplicate numai în locurile critice ale codurilor sursă pentru a duce la o creştere semnificativă de viteză a aplicaţiilor şi trebuie documentate foarte bine, mai ales dacă se doreşte sau este necesar ca alt programator să poată lucra cu codul respectiv mai târziu.
 
h2(#bibliografie). Bibliografie
 
# James A. Storer, _An Introduction to Data Structures and Algorithms_, Springer Verlag, 2001;
# T. H. Cormen, C. E. Leiserson, R. R. Rivest, _Introducere în algoritmi_, Editura Computer Libris Agora, 2000;
# 'The Aggregate Magic Algorithms':http://www.aggregate.org/MAGIC/
# 'TopCoder':http://www.topcoder.com/tc

Asemenea optimizări ca şi cele prezentate în cadrul acestui articol se pot dovedi foarte utile în unele cazuri, dar ele fac
programul ilizibil, tocmai din acest motiv, asemenea trucuri trebuie aplicate numai în locurile critice ale codurilor sursă pentru a
duce la o creştere semnificativă de viteză a aplicaţiilor şi trebuie documentate foarte bine, mai ales dacă se doreşte sau este necesar ca alt programator să poată lucra cu codul respectiv mai târziu.
 
h3(#bibliografie). Bibliografie
 
# James A. Storer, An Introduction to Data Structures and Algorithms, Springer Verlag, 2001
# T. H. Cormen, C. E. Leiserson, R. R. Rivest, Introducere în algoritmi, Editura Computer Libris Agora, 2000
# http://www.aggregate.org/MAGIC/
# http://www.topcoder.com/tc
 

4400