Matrici Sparse¶

Una matrice è una collezione bi-dimensionale, tipicamente pensata come una collezione di righe o colonne. Uno dei modi più semplici per creare una matrice è quella di usare una lista di liste. Per esempio, consideriamo la matrice mostrata sotto.

Possiamo rappresentare questa collezione come 5 righe, ciascuna riga avente 5 colonne. Usando una lista di liste, avremo una lista di 5 elementi. La lista più esterna rappresenta le righe e le liste interne rappresentano i dati contenuti nelle colonne.

matrix = [[0, 0, 0, 1, 0],
          [0, 0, 0, 0, 0],
          [0, 2, 0, 0, 0],
          [0, 0, 0, 0, 0],
          [0, 0, 0, 3, 0]]

Notiamo che ci sono molti zeri. Questo tipo di matrici sono chiamate matrici sparse.

Dal momento che spesso non c’è bisogno di memorizzare gli zeri, la lista di liste è considerata inefficiente. Un modo alternativo di rappresentare una matrice è mediante l’uso di un dizionario. Per le chiavi, possiamo usare tuple che contengono i numeri di righe e colonne. Questa che segue è la rappresentazione della stessa matrice.

matrix = {(0, 3): 1, (2, 1): 2, (4, 3): 3}

Abbiamo bisogno solamente di tre coppie chiave-valore, una per ogni elemento nonzero della matrice. Ogni chiave è una tupla, ogni valore è un intero.

Per accedere a un elemento della matrice, possiamo usare l’operatore []:

matrix[(0, 3)]

Nota che la sintassi della rappresentazione del dizionario usa un indice che è una tupla di indici invece di due indici interi (tra quadre) come nel caso della lista di liste (ad esempio matrix[i][j])

C’è un problema. Se specifichiamo un elemento che è zero, otteniamo un errore, perché non c’è alcun elemento nel dizionario con quella chiave. La versione alternativa del get risolve questo problema. Il primo argomento è la chiave. Il secondo argomento è il valore che get deve ritornare se la chiave non è nel dizionario (che deve essere 0 dal momento che la matrice è sparsa).