STABILIREA LUNGIMII INFORMATIEI UTILE




1. Constituirea vocabularului

Pentru rezolvarea unei probleme P se definesc datele de intrare, DI.
Orice problema face referire la o colectivitate.
Pentru calculul de salarii se face referire la colectivitatea CS a salariatilor, avand NS componente, cati salariati are organizatia.
Pentru gestiunea stocurilor de materiale se face referire la colectivitatea CM a materialelor, care are CM componente, adica tipuri de materiale.
Pentru o biblioteca, se face referire la:
- colectivitatea cartilor existente in rafturi
- colectivitatea cititorilor.
Pentru alocarea de camere la hoteluri se face referire la colectivitatile:
- camerelor existente in hoteluri
- persoanelor care fac rezervari
- consumabilelor pentru asigurarea confortului
- personalului de serviciu
. Pentru o agentie imobiliara colectivitatile sunt:
- spatiile disponibile, oferite spre vanzare
- spatiile oferite spre inchiriere
- terenurile oferite spre vanzare
- solicitarile de spatii pentru cumparare
- solicitarile de spatii pentru inchiriere
- solicitarile de terenuri pentru a fi cumparate.
Toate colectivitatile se descriu cat mai complet folosind caracteristici, grupate in sabloane care se regasesc in fisiere sau in baze de date sub forma de inregistrari.
Fiecarei caracteristici ii corespunde un camp.
Fiecarui camp ii corespunde o zona de memorie.
De la problema la problema este necesara mai multa sau mai putina zona de memorie alocata.
Fisierele sau bazele de date sunt mai mari sau mai mici.
Este necesar ca zonele de memorie odata definite si alocate sa nu mai fie nevoie sa se redefineasca datorita faptului ca apar situatii in care definirile nu mai corespund.
In cazul cantitatilor daca un camp are 5 pozitii si apare o situatie in care cantitatea este formata din 6 pozitii, este nevoie sa se inlocuiasca in toate programele definirea cu 5 pozitii, cu definirea cu 6 pozitii.
Problema anului 200 nu trebuie uitata prea repede, deoarece a aparut dintr-o eroare de previzionare a duratei de executie a programelor.
Se considera problema imobiliara.
In tabel sunt date cuvintele ce descriu tipul de componente care fac obiectul tranzactiilor imobiliare.
Nr.
crt. 		Termenul
utilizat

Ci 		Lungime
numar
caractere
Li 		Frecventa
aparitiilor

Fi
1 casa 4 120
2 baie 4 300
3 garsoniera 10 170
4 bloc 4 130
5 hol 3 200
6 mansarda 8 70
7 vila 4 200
8 dormitor 8 300
9 bucatarie 9 400
10 sufragerie 10 330
11 debara 6 180
12 supraetajare 12 250
13 intravilan 10 100
14 deschidere 10 150
15 lungime 7 310
16 teren 5 80
17 ultracentral 12 370
18 balcon 5 100
19 terasa 6 420
20 birou 5 30
. TOTAL . 4210

Campul cel mai scurt are 3 caractere.
Campul cel mai lung are 12 caractere.

Prea putini isi imaginau ca o baza de date va include atat date referitoare la anul 1900 si la anul 2000 sau date referitoare la anul 1901 si la anul 2001.
Alocarea a doua pozitii pentru an a fost o eroare cu costuri imense...
2. Indicatorii cantitativi

Se considera urmatorii indicatori:
V - vocabularul format din cuvintele ce desemneaza termenii utilizati in a defini elementele colectivitatii
NCV - numar de cuvinte distincte din vocabular
NCC - numar componente ale colectivitatii
Li - lungimea cuvantului i dintre termenii utilizati la definirea datelor
Lmax - lungimea maxima a cuvantului din vocabular
Lmin - lungimea minima a cuvantului din vocabular
LE - lungimea efectiva a tuturor cuvintelor
Fi- frecventa de aparitie a cuvantului i
LAS - lungimea standard de zona de memorie alocata astfel incat sa incapa toate cuvintele din vocabular
NART - numar de articole sau numar de inregistrari
GOS - gradul de ocupare standard a zonei de memorie.
Pentru aplicatia de tranzactii imobiliare:
NCV=20
Lmax=12
NART=4210cuvinte
LE=31920baiti
LAS=50520baiti
rezulta gradul de ocupare a zonei de memorie
GOS = 63,18%

3. Alocarea respectand conditia de maxim

Presupune sa se ia ca zona de memorie pentru tipul de obiect al tranzactiei Lmax si sa se calculeze lungimea alocata standard a zonei de memorie LAS.
Rezulta ca pentru cuvintele cu lungimea maxima, gradul de ocupare este 100%, in schimb pentru cuvinte scurte, gradul de ocumare este sub 50%, ceea ce afecteaza gradul de ocupare a zonei de memorie alocata structurii de date.
Pentru aplicatia de tranzactii imobiliare, pentru cuvintul ultracentral alocarea este integral ocupata, adica 100%, in timp ce pentru cuvantul hol agradul de ocupare GO=(3/12)*100=25%,
pentru celelalte cuvinte ocuparea este de asemenea redusa.
4. Alocarea cu acoperirea majoritara

Se considera o lungime care permite includerea unei mari majoritati a cuvintelor din vocabular.
In ipoteza ca aceasta lungime, Lfrq permite reprezentarea a peste PRO=90% dintre termenii din baza de date, adica pentru un numar de cuvinte
NCPR = (PRO/100)*NART
lungimea totala a zonei de memorie alocata LAPR, are valoarea ......
iar gradul de utilizare GOP are valoarea de ......
Daca se ia lungimea zonei de memorie LPR=10 baiti, din cele 4210 cuvinte se includ complet 3590 cuvinte, adica 85,27% dintre cuvinte.
Pentru cele 620 cuvinte fiind necesare zone de depasire, fiecare avand 3 baiti.
Sunt necesari pentru zonele de depasire 620*3 baiti adica 1860 baiti.
Lungimea zonei de memorie necesara include:
- zona alocata pentru a acoperi cei 85,27% din termeni, adica 3590*10 = 35900 baiti
- zona de depasire pentru cele 620 cuvinte care nu incap in 10 baiti, adica 620*3=1860 baiti
Se obtine LAPR= 35900+1860 = 37760 baiti.
Gradul de ocupare este: 84,53% suprior situatiei in care toate campurile au alocate cate 12 baiti.
5. Utilizarea de dictionare

Se construieste vocabularul.
Fiecare cuvant din vocabular este pus in corespondenta cu un numar.
In baza de date se stocheaza numere.
Pentru aplicatia impbiliara se procedeaza stfel:
- se construieste vocabularul care are 20 de cuvinte diferite
- cuvintele se memoreaza in zone de memorie de Lmax baiti, unde lungimea maxima are 12 baiti, intreg vocabularul necesitand 12*20 = 240 baiti
- cand apare un cuvant, acesta este inlocuit cu un numar de la 1 la 20 care ocupa un bait in baza de date si care indica pozitia cuvantului utilizat, in vocabular
- celor 4210 cuvinte din baza de date le vor corespunde pozitiile cuvintelor, adica 4210 baiti
- pentru a utiliza datele sunt necesari doi pasi: primul de a extrage pozitia si al doilea de a merge in vocabular pentru a incarca cuvantul de la pozitia specificata
- zona de memorie alocata folosind dictionare LAD include ceea ce este alocat pentru dictionar, adica 240 baiti la care se adauga cei 4210 baiti din baza de date, in total fiind necesari 4450 baiti
- gradul de ocupare bazat pe dictionare este GAD = (LAD/LE)*100 = 13,94% ceea ce reprezinta un scor foarte bun.
Dezavantajul este dat de volumul mare de prelucrari ce corespunde regasirii cuvintelor din vocabular dupa pozitiile acestora.
daca se construies structuri arborescente si se iau in considerare plasarea nodurilor tinand seama de frecventele de aparitie a cuvintelor in baza de date, se produc ameliorari semnificative la nivelul volumului de prelucrari.
6. Optimizare

Optimizarea presupune gasirea unui mod de alocare care sa:
- reduca lungimea zonei de memorie alocata
- conduca la un timp de prelucrare cat mai convenabil.
Daca se considera cele doua variante, prin comparatie se obtin rezultatele:
-
-
-
- ....
Printr-un sondaj efectuat printre specialisti, rezulta coeficientul de importanta pentru utilizarea resursei zona de memorie p1 = 0.3 si pentru durata de executie p2 = 0.7, p1 + p2 = 1
Functia agregata de optim aplicata celor doua variante indica utilizarea alocarii de zona de memorie maxima pentru a reduce durata de executie si utilizarea zonei de depasire atunci cand se urmareste un echilibru in derularea prelucrarilor.
Pentru arborele binar de cautare cu 20 noduri organizat pe 5 niveluri, numarul de comparari NCOMPi pentru a gasi un nod si numarul total de comparari pentru a referi termenul in intreava baza de date , fiecare de NCOMPi * Fi ori sunt necesare 15540 comparari, adica 777 comparari in medie.
Nr.
crt.
POZi 		Termenul
utilizat

Ci 		Lungime
numar
caractere
Li 		Frecventa
aparitiilor

Fi 		Numar
comparari
in arbore
NCOMPi 		Numar total
comparari
pe nod
NCOMPi * Fi 		Numar comparari
in element
vector
NCOMPVi*POZi
1 casa 4 120 4 480 120
2 baie 4 300 3 900 600
3 garsoniera 10 170 5 850 510
4 bloc 4 130 4 520 520
5 hol 3 200 5 1000 1000
6 mansarda 8 7 5 140 420
7 vila 4 200 4 800 1400
8 dormitor 8 300 3 900 900
9 bucatarie 9 400 4 1600 3600
10 sufragerie 10 330 1 330 3300
11 debara 6 180 4 720 1980
12 supraetajare 12 250 3 750 3000
13 intravilan 10 100 4 400 1300
14 deschidere 10 150 2 300 2100
15 lungime 7 310 5 1550 4650
16 teren 5 80 4 320 1850
17 ultracentral 12 370 5 1850 6290
18 balcon 5 100 3 300 1800
19 terasa 6 420 4 1680 7980
20 birou 5 30 5 150 600
. TOTAL . 4210 . 15540 44850

Daca cei 20 de termeni ai vocabularului se stocheaza intr-un masiv unidimensional, numarul total de comparari se obtine din insumarea produselor POZi* NCOMPi i=1,2,3,..., 20.
Numarul total de comparari daca se utilizeaza masiv unidimensional TCOMPV este de 44850, iar numarul mediu de comparari, NCmed = TCOMV / NC, este de 2242,5 cu mult mai mare daca se lucreaza cu un arbore de cautare unde numarul mediu de comparari este de 777.

7. Concluzii

Pentru alegerea zonei de memorie sunt urmatoarele modalitati:
- zona cu lungimea egala cu lungimea celui mai lung cuvant din vocabular; se iau cuvintele care apar in campul analizat pentru toata baza de date, se determina vocabularul, se stabilesc lungimile cuvintelor din vocabular si se ia cea mai mare lungime; aceasta este lungimea zonei de memorie; este usor de obtinut un astfel de rezultat dar gradul de utilizare a zonei de memorie este mic;
- zona de memorie de lungimea celui mai lung cuvant din vocabular, majorata cu un procent pentru a acoperi riscul aparitiei unui nou cuvant cu lungime mai mare in vocabular; daca zona de memorie are Lmax baiti, prin inmultirea cu 1,5 va acoperi acel risc, gradul de utilizare insa se reduce foarte mult; volum de comparari foarte bun dar ceva mai greu de implementat; aparitia a doi pointeri in nod redug cu putin gradul de utilizare a zonei de memorie din punct de vedere a informatiei utile;
- utilizarea de zone de depasire
- utilizarea de dictionar cu regasire in arbore de cautare;
- utilizaree de dictionar ci regasire in masiv unidimensional, usor de implementat dar cu volum de comparari foarte mare si grad de ocupare bun pentru zona de memorie.