Maldensa matrico
En cifereca analizo, maldensa matrico estas matrico kies plejmulto da elementoj estas nulo. Alie, ĝi estas densa. La nombro de nulaj elementoj dividita de la tuta nombro de elementoj (ekz, m × n por m × n-matrico) nomiĝas la maldenso de la matrico. Ĝia komplemento estas la denso.
Granda maldensa matrico ofte aperas en scienca kaj inĝeniera aplikado, kiam oni solvas partan diferencialan ekvacion.
Memori maldensan matricon redakti
Tipe matrico memoriĝas kiel du-dimensia tabelo, kiun oni vizitas per indeksoj i kaj j. Konvencie, i estas la horizonta indekso kaj j estas la vertikala. La memorkosto tiel por m × n matrico estas funkcio de m × n.
Por maldensa matrico, oni povas grande malmultigi la memorkoston per memori nur la nenulaĵojn. Variaj datumstrukturoj utiliĝus kondiĉe je la preciza denso kaj distribuo de la nenulaĵoj. La dilemo estas ke viziti elementojn en tiaj datumstrukturoj estos pli multekosta, kaj necesus kroma strukturo se oni volus rekonstrui la originan matricon precize.
Estas du klasoj de datumstrukturoj por memori maldensan matricon:
- Tiaj, kiuj subtenas rapidan ŝanĝon: DOK (Vortaro de klavoj), LoL (Listo de listoj), aŭ COO (Kunorda listo). Ili utilas por rekonstrui la originan matricon rapide.
- Tiaj, kiuj subtenas rapidan vizitadon kaj matrican operacion: CSR (Presita Maldensa Horizontalo) aŭ CSC (Presita Maldensa Vertikalo).