[Tech] Matrici sparse [domanda semidifficile]

[Leonardo Boselli]

Ho un programma che legge una serie di file (quali legge dipende dal
comando in input).
Una volta che ha caricato in memoria questi file si trova un array di
circa 800000 record del tipo:
struct { short min, short max , short posizione , short blocco ; }
li deve quindi scorrere tutti e per ogni coppia blocco:posizione trovarmi
il valore in cui max-min sia minimo.
Quindi ho una matrice del tipo
typedef struct { long index, short delta } cella ;
cella array[??????] ;
ecco ... visto che posizione so essere tra 1 e 16383 e blocco lo stesso
potrei definire array[16384][16384] ma la memoria mi comincierebbe a
mancare !
Io so però che, salvo dati palesemente incongruenti, i record che carico
su cui debbo fare la ricerca appartengono al massimo a 7 blocchi diversi
(e questi li conosco mentre carico i file).
quindi potrei avere un array ausiliario mmu[16384] che ha lunghezza 16384
e valore compreso tra 0 e 6 a seconda di dove si trova allocato il blocco.
Avrei quindi array[7][16384] con dimensione quindi ben più ragionevoli.
ma con un passaggio in più. ( array[mmu[blocco]][posizione] )
Dal punto di vista prestazionali come si comporta la MMU del sistema se
facessi l'array da 1 GB di cui uso solo 7 blocchi da ?? come fa ad
accorgersene che il grosso dell'array non viene mai usato ?
come prestaziobni quale è il sistema migliore ?