Eliminarea subexpreiilor comune

Eliminarea subexpreiilor comune nu se explică prea bine în cuvinte, ci trebuie venit cu un exemplu. Se consideră expresia:

se vede acolo că o subexpresie notată de mine cu s se repetă

Dacă o înlocuim, expresia e devine:

Complexitatea primei expresii include:
- operanzii diferiți e, a, b, c,  3, 1, 2,4, numărul lor fiind de 8;
- operatorii diferiți sunt  =, +, *. -, /, pow numărul lor fiind 6;
- complexitatea C a expresiei este C = 8 * log2 8 + 6 * log2 6 =39,51  .
Dacă este eliminată subexpreis comună, atunci cele două expresii s și e concuc la:
- operanzi utilizați e, a, b, c, s,  3, 1, 2,4, numărul lor fiind de 9;
- operatorii diferiți sunt  =, +, *. -, /, pow numărul lor fiind 6;
- complexitatea C a expresiilor este C = 9 * log2 9 + 6 * log2 6 = 44,04 , ceea ce înseamnă că eliminarea subexpresilor comune cu complexitatea calculată luând diversitatea operanzilor și operatorilor nu este profitabilă.
Dacă însă se ține seama de operanzii și operatorii care apar efectiv în expresia inițială, se observă că:
- variabila a apare de 4 ori;
- variabila b apare de 4 ori;
- variabila c apare de 4 ori;
- variabila e  apare o dată;
- constanta 1 apare o dată;
- constanta 3 apare o dată;
- constanta 2 apare o dată;
- constanta 4 apare o dată;
- operatorul de atribuire apare o singură dată;
- operatorul de împărțire /, apare o singură dată;
- operatorul de adunare +, apare de 10 ori;
- operatorul de scădere, apare de 2 ori;
- operatorul de ridicare la putere pe care l-am notat pow, apare de 12 ori;
- operatorul de înmulțire *, apare de 2 ori.
Rezultă că expresia e are  17 operanzi și 28 de operatori ceea ce conduce la o conplexitate calculată de C = 204,075.
În cazul în care se optimizează prin înlocuirea subexpresiei comune se identifică frecvențele:
- variabila a apare  o singură dată;
- variabila b apare  o singură dată;
- variabila c apare   o singură dată;
- variabila e  apare o dată;
- variabila e  apare de 5 ori;
- constanta 1 apare o dată;
- constanta 3 apare o dată;
- constanta 2 apare o dată;
- constanta 4 apare o dată;
- operatorul de atribuire apare 2 ori;
- operatorul de împărțire /, apare o singură dată;
- operatorul de adunare +, apare de 4 ori;
- operatorul de scădere, apare de 2 ori;
- operatorul de ridicare la putere pe care l-am notat pow, apare de 3 ori;
- operatorul de înmulțire *, apare de 2 ori.
Cele două expresii au 13 operanzi și 14noperatori. Complexitatea C  după eliminarea subexpresiilor comunie este C =  13 * log2 13 + 14 * log2 14 = 101,398 care este la jumătatea complexității expresiei inițiale, ceea ce arată că eliminarea subexpresiilor comune este benefică duratei de execuție a unui program, știut fiind faptul că reducerea numărului de cicluri mașină este foarte  importantă.
Eliminarea subexpreiilor comune reprezintă o modalitate specială de a arăta că programatorul performează cu adevărat, chiar dacă viteza de calcul este acum amețitoare și n-ar mai conta o reducere cu 3-% să zicem a numărului de cicluri malșină. Numai că de aici se adună ceva, de dincolo mai se aducă și altceva și tot așa se construiește non-performanța unei aplicații dată de viteza redusă per global de a obține un rezultat complet.

(03 decembrie 2017)