Optimizarea programelor folosind operaţii pe biţi

Acest articol a fost adăugat de GheorgheMihaiMihai Gheorghe GheorgheMihai
Intră aici dacă doreşti să scrii articole sau află cum te poţi implica în celelalte proiecte infoarena!

(Categoria Algoritmi, Autor Cosmin Negruşeri)

În cadrul acestui articol vă vom prezenta câteva metode prin care programele se pot optimiza dacă utilizăm eficient operaţiile pe biţi sau folosim operaţii pe biţi în locuri în care, la prima vedere, nu s-ar părea că ar fi necesare.

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(n3/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.

Î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).

Aplicaţia #1

Să se determine numărul de biţi de 1 din reprezentarea binară a lui n.

Rezolvare

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

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:

110111010100002 = n
110111010011112 = n - 1
110111010000002 = n & (n - 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:

Dar este acest algoritm mai rapid? Am testat pentru toate numerele de la 1 la 224 ş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ă.

Aplicaţia #2

Să se determine paritatea numărului de biţi de 1 din reprezentarea binară a unui număr n.

Rezolvare

Din cele prezentate mai sus se pot determina două metode evidente:

Putem obţine o a treia rezolvare făcând câteva observaţii pe un exemplu. Considerăm n = 110110112. 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:

Deşi constanta multiplicativa este mai mare, numărul de operaţii are ordin logaritmic faţă de numărul de biţi ai unui cuvânt al calculatorului.

Aplicaţia #3

Să se determine cel mai puţin semnificativ bit de 1 din reprezentarea binară a lui n.

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:

Exemplu:

110110002 = n
110101112 = n - 1
110100002 = n & (n - 1)
110110002 = n
000010002 = n ^ (n & (n - 1))

Această funcţie este foarte importantă pentru structura de date arbori indexaţi binar prezentată într-un un articol mai vechi din GInfo.

Aplicaţia #4

Să se determine cel mai semnificativ bit cu valoarea 1 din reprezentarea binară a lui n.

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.

Aplicaţia #5

Să se determine indexul celui mai semnificativ bit de 1 din reprezentarea binară a lui n.

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 = 100000002
n = n | (n >> 1)
n = 110000002
n = n | (n >> 2)
n = 111100002
n = n | (n >> 4)
n = 111111112

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...

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

Aplicaţia #6

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

Rezolvare

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.

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

Rezolvarea aplicaţiei #1

Determinăm, pentru numerele de la 0 la 216 - 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...

Rezolvarea aplicaţiei #2

Determinăm, pentru numerele de la 0 la 216 - 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...

Rezolvarea aplicaţiei #3

Determinăm, pentru numerele de la 0 la 216 - 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...

Rezolvarea aplicaţiei #4

Determinăm, pentru numerele de la 0 la 216 - 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...

Rezolvarea aplicaţiei #5

Determinăm, pentru numerele de la 0 la 216 - 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...

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(n2m) ar fi fost următorul: se consideră fiecare pereche formată din două linii şi se numără câte perechi (Mi,k, Mj,k) pentru care Mi,k = 1 şi Mj,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...

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).

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...

  1. cmmdc(a, b) = 2 * cmmdc(a / 2, b / 2), dacă a şi b sunt numere pare;
  2. cmmdc(a, b) = cmmdc(a, b / 2), dacă a este impar;
  3. 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.

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ţ...

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:

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...

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...

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.

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.

Bibliografie

  1. James A. Storer, An Introduction to Data Structures and Algorithms, Springer Verlag, 2001;
  2. T. H. Cormen, C. E. Leiserson, R. R. Rivest, Introducere în algoritmi, Editura Computer Libris Agora, 2000;
  3. The Aggregate Magic Algorithms
  4. TopCoder
remote content