O matrice rară este o reprezentare abstractă a unui tablou obișnuit , în care datele nu sunt prezentate continuu, ci fragmentate; majoritatea elementelor sale iau aceeași valoare (valoarea implicită, de obicei 0 sau nulă). Mai mult, stocarea unui număr mare de zerouri într-o matrice este ineficientă atât pentru stocarea, cât și pentru procesarea matricei.
O matrice rară poate accesa elemente nedefinite. În acest caz, matricea va returna o valoare implicită.
Cea mai simplă implementare a acestei matrice alocă spațiu pentru întreaga matrice, dar când există puține valori care nu sunt implicite, această implementare este ineficientă. Funcțiile pentru lucrul cu matrice obișnuite nu sunt aplicate acestei matrice în cazurile în care sparsitatea este cunoscută dinainte (de exemplu, la stocarea datelor în blocuri).
O matrice rară este de obicei reprezentată ca o matrice asociativă :
Sparse_Array[{pos1 -> val1, pos2 -> val2,…}]sau Sparse_Array[{pos1, pos2,…} -> {val1, val2,…}],unde fiecare pozitie pos i corespunde valorii val i . Această metodă este folosită pentru a economisi memorie (atât cheia, cât și valoarea transportă informații).
O listă legată este folosită aici în loc de o matrice obișnuită, deoarece, mai întâi, o matrice obișnuită necesită spațiu pentru a stoca valori nedefinite. De exemplu, atunci când se declară:
double arr[1000][1000];8 MB de memorie vor fi alocați o dată (8 octeți per valoare × 1.000.000 de valori), ceea ce reprezintă o risipă nejustificată de memorie. În cazul unei liste legate, valorile goale nu sunt stocate, iar spațiul pentru noile valori este alocat automat atunci când elementele sunt adăugate sau eliminate (în acest caz, putem vorbi despre alocarea dinamică a memoriei ).