sparse matrix (tsz. sparse matrixes)
A sparse matrix vagy magyarul ritka mátrix olyan mátrix, amelyben az elemek többsége nulla. Ezek az adatszerkezetek különösen fontosak a nagy méretű matematikai modellezés, tudományos számítások, gépitanulás, és gráfalgoritmusok esetén. A ritka mátrixok hatékony kezelése memória- és számítási időmegtakarítást tesz lehetővé.
Egy mátrix akkor számít ritkának, ha elemeinek jelentős része zéró, jellemzően több mint 90%-uk nulla. Például egy 1000x1000-es mátrixban 1 millió elem van. Ha ebből csak 10 000 nem nulla, az arány 1%, vagyis ez egy tipikus ritka mátrix.
Ezzel szemben a sűrű mátrix (dense matrix) olyan, ahol az elemek többsége nem nulla.
A = [ , , , , ]
Ebben az 5x5-ös mátrixban 25 elem van, de csak 3 nem nulla – ez 12% kitöltöttség.
Egy hagyományos mátrixot 2D tömbként tárolunk, minden elemet memóriában tartva – függetlenül attól, hogy nulla-e. Ritka mátrixoknál ez pazarló, ezért speciális adattárolási módokat alkalmazunk.
Minden nemnulla elemet koordinátapárral (sor, oszlop) és értékkel együtt tárolunk.
Példa:
Sor Oszlop Érték 0 4 5 2 2 3 4 0 7
A mátrixot három tömb segítségével tároljuk:
values tömbben
Hasonló a CSR-hez, de oszlopokra optimalizált.
Egy szótárban kulcsként (i,j) párokat tárolunk, értékként pedig a megfelelő számokat.
Ritka mátrixokra a szokásos mátrixműveletek végrehajthatók, de optimalizált algoritmusokat használnak.
Csak a nem nulla elemeket kell egyeztetni és módosítani.
Adatszerkezettől függően egyszerű lehet, pl. COO-t csak az indexeket kell felcserélni.
Számos könyvtár támogatja a ritka mátrixokat:
scipy.sparse modul – támogatja CSR, CSC, COO, DOK stb.
sparse() függvény – automatikusan optimalizál
dgCMatrix típus
import numpy as np
from scipy.sparse import csr_matrix
# 3x3 mátrix:
data =
rows =
cols =
A = csr_matrix((data, (rows, cols)), shape=(3,3))
v = np.array()
result = A.dot(v)
print(result) #
Ha egy mátrixban a nemnulla elemek aránya 30–50% feletti, a ritka mátrix formátum több memóriát is foglalhat, mivel extra indexeket kell tárolni. Ilyenkor a sűrű tárolás hatékonyabb.
A ritka mátrix az egyik legfontosabb adatstruktúra a modern számítástechnikában, amikor nagy, de nagyrészt üres (nullákkal teli) adatstruktúrákkal dolgozunk. A speciális tárolási formák és algoritmusok lehetővé teszik a hatékony műveletvégzést, jelentős memória- és időmegtakarítással. Ez különösen kritikus az olyan területeken, mint a gépi tanulás, grafikus számítások, vagy fizikai szimulációk.