ACADEMIA DE STUDII ECONOMICE

FACULTATEA DE CIBERNETICa, STATISTICa si INFORMATICA ECONOMICA

Structuri de date

PROIECT

[Modalitati de stocare a matricelor particulare in memorie utilizand diverse structuri de date.

Aplicatie pe MATRICE RARE

Introducere

Obiectivul proiectului de fata este realizarea compresiei datelor dintr-o matrice rara memorata dinamic. Stiind ca se da o matrice rara A cu N linii si M coloane alocata dinamic, cu un numar mare de elemente nenule, se doreste stocarea acesteia ca o matrice particulara din punct de vedere al memorarii, folosind diverse structuri de date. Prin variatele modalitati de memorare a matricei rare, implementate in programul de fata, se evidentiaza reducerea resurselor necesare pentru lucrul si operatiile pe matrice rare.

Ca mijloace de rezolvare a problemei, se considera 3 structuri principale de date: vector, lista si liste de liste, structuri prin intermediul carora vom realiza compresia datelor din matricea rara alocata dinamic.

Reducerea zonelor de memorie uilizate si timpul mai mic de executie prin eliminarea operatiilor cu elementele nule sunt doua dintre cele mai importante avantaje ale stocarii masivelor de acest tip prin intermediul structurilor mentionate. Iar necesitatea acestor implementari o reprezinta in principal tocmai atingerea acestor doua obiective. De asemenea, in aplicatiile economice, este ineficient sa lucram cu matrice in care numarul de elemente nenule este mare deoarece acestea sunt tratate in acelasi mod ca si celelalte elemente. Din acest motiv, implementarea operatiilor de baza este mult mai dificil de realizat.

Structura programului

Definirea problemei

Se pune problema gasirii unor diverse modalitati de stocare a matricilor rare astfel incat sa se evite toate dezavantajele generate de prezenta numarului mare de elemente nenule, si al dimensiunilor considerabile ale masivului, dezavantaje evidente mai ales atunci cand se efectueaza operatii(adunare, scadere, cautare element) asupra acestor tipuri de masive.

In cazul matricelor rare, matrice care au mai putin de 30% din totalul elementelor, elemente nenule, realizarea de operatii prin folosirea structurii standard de matrice si a algoritmilor aplicati pe aceasta, este in general foarte inceata si consuma mari resurse de memorie, mai ales cand lucram cu dimensiuni foarte mari.

Structura de date obisnuita pentru o matrice este masivul bidimensional. Fiecare pozitie din matrice reprezinta un element ce este accesat utilizand indici de linie si coloana pentru pozitionare. Pentru o matrice de dimensiuni NxM, in care un element ocupa Q baiti, lungimea zonei de memorie necesara pentru stocarea matricii este de Q*M*N baiti. In cazul matricelor rare majoritatea elementelor sunt egale cu 0. Cum elementele nule sunt stocate in acelasi mod in care sunt stocate toate celelalte elemente, se observa usor ca acestea ocupa cel mai mare spatiu de memorie si ingreuneaza viteza de executie in efectuarea operatiilor.

Date de intrare si rezultate:

In implementarea proiectului, datele de intrare, citite din fisier, sunt numarul de linii, numarul de coloane si matricea rara, pe care am alocat-o dinamic in programul principal. Folosind aceste date de intrare am realizat transformarea matricii rare in:

structuri de tip vector (au rezultat trei vectori dintre care: unul memoreaza indicele de linie, altul indicele de coloana, iar al treilea valoarea elementului nenul)

structuri de tip lista (a rezultat o lista ce are ca informatie: un camp ce retine linia pe care se afla elementul, unul retine coloana acestuia, iar cel din urma valoarea nenula a elementului)

structuri de tip lista de liste (ce contine un camp de informatie in care memoram linia pe care se gaseste elementul nenul, un pointer catre o alta lista, un pointer catre elementul urmator al listei curente).

Aceste structuri fiind si rezultatele programului implementat.

Grupul tinta, colectivitatea careia se adreseaza

Matricile rare pot fi folosite in diverse situatii in practica, grupul tinta si colectivitatile carora se adreseaza fiind din  cele mai diverse. Cateva exemple sunt:

in practica pentru stocarea unei imagini bitmap cu doar doua culori (dintre care una dominanta, primara, iar a doua, utilizata mai putin, secundara) se va utiliza reprezentarea prin matrice rare. In acest caz, o modalitate eficienta de stocare a acestora este urmatoarea: vom stoca doar linia si coloana pixelilor din imaginea bitmap ce contin doar culoarea secundara. 

matricea diagonala este matricea ce are elemente nenule numai pe diagonala principala. O metoda foarte eficienta de stocare a acesteia este construirea unui vector de dimensiune n in care vom memora doar elementele diagonalei principale.

o matrice banda este matricea ce are elemente nenule numai in jurul diagonalei. Acest tip de matrice va fi tratata ca marice rara, datorita numarului mare de elemente nenule. O solutie de stocare a acesteia este reprezentarea prin 3 vectori, reducand considerabil spatiul de memorie. Astfel in locul stocarii celor Q*M*N, vom necesita numai 3*Nenul*Q baiti, unde Nenul reprezinta numarul de elemente nenule. Reducerea spatiului de memorie este evidenta.

Date de intrare

Datele de intrare vor fi preluate dintr-un fisier txt ce va contine numarul de linii, numarul de coloane si elementele matricii rare. Elementele din fisierul text vor fi generate prin intermediul altui program c++, atasat ca si anexa acestui proiect.

Pentru o mai mare acuratete a testelor asupra reprezentarilor prin diverse structuri de date a matricilor rare, am creat un program ale carui date de intrare sunt numarul de linii, numarul de coloane si procentul de elemente nenule care sunt preluate de la tastaura si pe care utilizatorul doreste sa le aiba in testele sale. Am uitilizat functia rand() din biblioteca <stdlib.h> pentru a genera indicele de linie, indicele de coloana si valoarea elementului nenul. Numarul de elemente nenule din matricea generata este egal cu procentul dorit de utilizator.

Va fi generata o matrice de NxM dimensiuni, de tip integer, in care elementele nenule pot lua valori in intervalul [0-100]. De asemenea am presupus ca dimensiunile matricei se incadreaza tot in intervalul [0-100].

Pentru generarea indicelui de linie s-a folosit comanda: rand()*(n/(RAND_MAX+1.0) pentru a pastra indicele de linie in intervalul [0-N]. Functia rand() returneaza un numar intreg aleator din intervalul [0, RAND_MAX]. Asadar, aceasta poate returna RAND_MAX+1 valori diferite, unde RAND_MAX reprezinta valoarea maxima pe care o poate lua functia rand().

Analog s-a procedat pentru generarea indicelui de coloana: rand()*(m/(RAND_MAX+1.0) pentru a pastra indicele de coloana in intervalul [0-M], precum si pentru generarea valorii elementului nenul: rand()*(100/(RAND_MAX+1.0) pentru a pastra valoarea elemntului nenul in intervalul [0-100].

Pentru teste diferite, se apeleaza mai intai programul de generare si scriere a matricii in fisier, dupa care se apeleaza programul ce implementeaza compresia datelor din matricea rara. Testele se fac pentru procente diverse, preferabil sub 30% elemente nenule.

Structurile de date utilizate intern

Pentru implementarea conceptului acestui proiect, am folosit urmatoarele structuri de date, cu semnificatia:

1) Structura utilizata pentru memorarea matricii rare initiale. Se retin prin intermediul structurii numarul de linii, numarul de coloane si matricea propriu zisa alocata dinamic. In programul principal se va lucra cu un pointer la o structura de tip matrice.

struct matrice;

Alocarea se face utilizand urmatoarea bucata de cod in programul principal:

matrice *a=(matrice*) malloc(sizeof(matrice));

fscanf(f,'%d',&a->nrLin);

fscanf(f,'%d',&a->nrCol);

//alocare matrice

a->rara=(int **) malloc(a->nrLin * sizeof(int*));

for(int i=0;i<a->nrLin;i++)

2) Structura utilizata pentru memorarea unui vector. Se retine numarul de elemente al vectorului si vectorul propriu zis alocat dinamic.

struct vector;

Alocarile celor 3 vectori ce vor retine linia, coloana si valoarea elementelor nenule se realizeaza in maniera urmatoare:

*v1=(vector *) malloc(sizeof(vector));

*v2=(vector *) malloc(sizeof(vector));

*v3=(vector *) malloc(sizeof(vector));

(*v1)->nrElem=(*v2)->nrElem=(*v3)->nrElem=nenul;

(*v1)->vect= (int*) malloc((*v1)->nrElem*sizeof(int));

(*v2)->vect= (int*) malloc((*v2)->nrElem*sizeof(int));

(*v3)->vect= (int*) malloc((*v3)->nrElem*sizeof(int));

3) Structura utilizata pentru memorarea unei liste simple. Lista va fi o succesiune de noduri ce vor avea structura: o informatie pentru memorarea liniei, una pentru memorarea coloanei, si una pentru memorarea valorii elementului nenul. Prin pointerul next se va face legatura intre nodurile listei, iar accesul la informatie se va face, ca in orice lista secvential.  Adaugarea elementelor se va face prin inserare de nod la sfarsitul listei.

struct nodLS;

4) Structura pentru memorarea listei de liste. Lista de liste pe care am cosntruit-o este tot o structura de tip lista in care unul dintre pointeri directeaza la capul unei alte structuri de tip lista simpla.  Campurile listei de liste vor fi o informatie, reprezentand linia pe care se afla elementul nenul din matrice si doi pointeri. Unul dintre ei va fi folosit pentru a parcurge lista de liste(structura curenta si va pointa catre urmatorul element de acelasi tip), iar celalalt va fi folosit pentru a parcurge lista simpla, adiacenta nodului cu elemente de tipul nodLLA, descrisa de structura prezentata mai jos. Accesul la elemente listei de baza se face de asemenea secvential, prin parcurgerea listei de liste pana la gasirea elementului dorit, iar adaugarea de noduri se face la sfarsitul listei. Accesul la elementele listei adiacente unui nod se face in aceeasi maniera, parcurgand pentru nodul curent al listei de liste, lista lui adiacenta.

struct nodLL;

5) Structura pentru memorarea listelor adiacente nodurilor din lista de liste. Aceasta contine o varabila ce va memora coloana pe care se afla elementul nenul, precum si o alta variabila ce memoreaza valoarea elementului. Trecerea de la un element la altul se realizeaza prin intermediul pointerului next.  Structura este practic tot o lista simpla, cu doua campuri de informatie.

struct nodLLA;

Descrierea implementarii operatiilor de baza

Prin intermediul lucrarii de fata am realizat reprezentarea unei matrice rare, alocata dinamic prin diverse structuri de date: vector, lista, lista de liste, alocate si ele tot dinamic.

Bibliotecile utilizate in cadrul proiectului:

#include<iostream> - pentru functiile de intare/ iesire

#include<malloc.h> - pentru functia malloc cu ajutorul careia am alocat masivele si listele

Initial, am citit dintr-un fisier de tip txt matricea rara pe care am alocat-o dinamic in interiorul programului principal.

Apoi, i-am dat utilizatorului posibilitatea de a alege intre a face reprezentarea acestei matrice prin 3 vectori, liste, sau lista de liste(folosind comanda switch). Utilizatorul alege optiunea dorita, iar dupa apelarea procedurii care face reprezentarea matricii rare prin structura pe care o doreste, dezaloca spatiul de memorie utilizat de matricea rara. Din acest punct, utilizatorul nu va mai folosi in prelucrari matricea rara, ci reprezentarea ei prin structura dorita.

Reprezentarea prin 3 vectori am utilizat procedura

void reprezentareVectori(matrice *a,vector **v1, vector **v2, vector** v3, int nenul)

prin intermediul careia am construit 3 vectori de dimensiune egala cu numarul elementelor nenule din matricea initiala (nenul), cu urmatoarea semnificatie: un vector v1 care retine linia pe care se gaseste elementul nenul, un vector v2 care retine coloana elementului nenul si un vector v3 ce retine valoarea nenula. Cei trei vectori sunt alocati dinamic in memorie.

Reprezentarea prin lista: am utilizat procedura:

nodLS* reprezentareListe(matrice *a, nodLS* prim)

prin intermediul careia am creat o structura de tip lista ce contine 3 campuri de informatie: unul ce retine linia pe care se afla elementul, unul retine coloana acestuia, iar cel din urma valoarea nenula a elementului. Numarul nodurilor din lista este egal cu numarul elementelor nenule din matrice. Subprogramul apeleaza procedura de creare a listei simple: nodLS * adaugareLS(nodLS *prim,int lin, int col, int val)

Reprezentarea prin lista de liste: am utilizat procedura:

nodLL* reprezentareListadeListe(matrice *a, nodLL* p)

cu ajutorul careia am contruit o structura de tip lista ce contine urmatoarele campuri cu semnificatiile: un camp de informatie in care memoram linia pe care se gaseste elementul nenul. Un pointer catre o alta lista, un pointer catre elementul urmator al listei curente. Primul pointer va directa catre o lista ce va contine: un camp ce memoreaza coloana pe care se afla elementul, un camp ce memoreaza valoarea elementului, un pointer catre elementul urmator al celei de-a doua liste. Subprogramul apeleaza

nodLL* creare(nodLL *p, int lin, int col, int val) prin intermediul careia se creeaza lista de liste.  Aceasta procedura returneaza primul nod al listei de liste. In cazul in care lista este nula, se contruieste primul nod cu informatiile pe care le primeste ca parametrii. Altfel, se parcurge lista pana cand fie se gaseste un element (element=linie, pentru ca lista de liste contine liinile pe care se gasesc elementele neneule) care exista deja in lista, fie s-a ajuns la sfarsitul listei. In cazul in care elementul exista deja in lista, se adauga la lista adiacenta lui un nou element cu informatiile despre coloana noului element nenul identificat. Se utilizeaza pentru aceasta procedura creareLAD nodLLA* creareLAD( nodLLA * prim, int infoC, int infoV). In cazul in care s-a ajuns la capatul listei, se adauga un nou nod la lista de liste, iar lista lui adiacenta se completeaza cu coloana si valoarea unde s-a gasit elementul nenul.

Concluzii:

Avantajele memorarii matricelor rare prin intermediul altor structuri de date sunt evidente. Cum matricele rare se reprezinta ca masive de dimensiuni foarte mari, al caror numar de elemente nenule este mai mare ca 70% din totalul elementelor, realizarea unei compresii a datelor pentru a reduce resursele necesare memorarii acestora este extrem de necesara. Operatiile efectuate cu matrice rare sunt in general voluminoase daca ne referim la gradul de utilizare al memoriei, volumul de prelucrari, timpul si viteza de executie.

Voi incerca sa prezint cateva din avantajele si dezavantajele fiecareia dintre cele 3 structuri de date utilizate:

Prin stocarea matricilor rare ca masive bidimensionale, se efectueaza si operatiile aritmetice de baza care nu sunt necesare, precum x+0, care e intotdeauna x sau multiplicari precum x*0 care e intotdeauna 0. Utilizand cele 3 tipuri de reprezentari se evita lucrul cu elemente nenule, deci si astfel de operatii.

Lungimea totala de memorie ocupata: (presupunem ca elementele sunt numere intregi, nenul=numarul elementelor nenule)

- reprezentarea prin vectori: LT= 3*nenul*4=12*nenul

- reprezentare prin liste: LT=nenul*(4+4+4+4)+4=nenul*16+4

- reprezentare prin lista de liste LT= nenul*(4+4+4)+4=nenul*12+4????

Lungimea totala de memorie ocupata pentru stocarea matricii rare ca masiv bidimensional ar fi: nrLinii*nrColoane*4. Se observa ca prin toate cele 3 reprezentari, comparativ cu reprezentarea prin masiv bidimensional, memoria ocupata este mult mai mica. Numarul de elemente al masivului bidimensional poate fi foarte mare, cand lucram cu dimensiuni mari, iar numarul de elemente nenule, considerabil mai mic.

Presupunem o matrice de dimensiuni foarte mari: 5000x5000. Aceasta necesita spatiu pentru 25 milioane numere, chiar daca sa presupunem ca numai 50000 au valori diferite de 0.

• In reprezentarea cu vectori, spatiul ocupat va fi de 50000 pentru valorile complexe si 50000 pentru perechile de indici intregi. Deci spatiul ocupat va fi considerabil mai mic.
• In reprezentarea cu liste si liste de liste, spatiul ocupat va fi putin mai mare decat in reprezentarea cu vectori, din cauza prezentei pointerilor. Totusi si aceste reprezentari sunt o varianta mai buna reprezentarii prin masiv bidimensional.

Asa cum am mentionat mai sus, fiecare dintre cele 3 reprezentari au atat avantaje, cat si dezavantaje.

reprezentarea prin vectori:

a.  daca alocarea vectorilor nu s-ar face dinamic, gradul de incarcare al vectorilor nu ar fi maxim, existand diferente intre numarul elementelor nenule si numarul maxim de elemente care se memoreaza efectiv pentru fiecare vector. Aceasta diferenta poate fi uneori considerabila, ocupand mai multa memorie decat este necesar.

b. Daca alocarea vectorilor se face dinamic, apar probleme atunci cand numarul elementelor nenule se modifica. Alocarea vectorilor se face la inceput, iar daca va creste numarul de elemente nenule( in urma operatiilor efectuate pe matrici), vectorul trebuie dezalocat si alocat din nou.

reprezentarea prin liste:

a.  pointerii ocupa destul de mult spatiu, probleme putand aparea mai ales atunci cand dimensiunile masivului sunt foarte mari iar numarul de elemente nenule se aproprie de 30% din totalul elementelor.

b. Accesul la elemente se face secvential. Daca lista are dimensiuni considerabile si trebuie sa parcurgem mare parte din ea pentru a gasi un element cu o anumita valoare, operatiile sunt ingreunate, ca si timp de executie

reprezentare prin lista de liste:

a.  numarul de pointeri utilizati in cazul listei de liste este foarte ridicat( atat pentru lista de liste cat si pentru lista adiacenta fiecarui nod), fiind chiar total ineficienta in cazul dimensiunilor mari.

b. Cu toate ca procesul de cautare este mai bun, un alt dezavantaj este legat de faptul lista fiecarui nod adiacent are dimensiuni diferite, aparand situatii cand pe linii exista un singur element nenul, deci listele adiacente vor avea numai un singur element.

Asadar, diversele tipuri de reprezentari cu ajutorul altor structuri de date aduc fiecare, propriile imbunatiri ale acestor variabile de executie si memorare. Desigur, fiecare dintre aceste reprezentari are si propriile dezavantaje. Totusi, aceste dezavantaje sunt surclasate de avantajele pe care ele le prezinta atunci cand efectuam operatii asupra matricilor rare de dimensiuni foarte mari, fiind evident faptul ca lucrul cu vectori, liste, sau lista de liste este mult mai eficient decat lucrul cu masive bidimensionale.

Bibliografie