Matrius disperses

L’objectiu d’aquest exercici és definir la classe MatriuDispersa que permeti representar una matriu de dimensions grans en la qual la majoria dels valors són nuls (zeros) sense utilitzar gaire memòria, emmagatzemant només els valors no nuls.

Especificació de la classe MatriuDispersa

class matrius.MatriuDispersa(nfiles, ncolumnes)

Matriu dispersa de nfiles x ncolumnes elements.

Atributs:

nfils

Nombre de files de la matriu (enter).

ncols

Nombre de columnes de la matriu (enter).

Aquesta classe ha de suportar les operacions següents:

Operació	Resultat
m[f, c]	retorna el valor de la matriu m a la fila f i columna c
m[f, c] = valor	assigna valor a l’element de la fila f i columna c de la matriu m
m2 = k * m1	la matriu resultant del producte de l’escalar k per m1 (vegeu [1]).
m3 = m1 + m2	la matriu resultant de la suma de m1 i m2 (vegeu [2]).
m3 = m1 * m2	la matriu resultant del producte de m1 per m2 (vegeu [3]).

La classe suporta, a més, les funcions: len() i str.

Implementació de la classe MatriuDispersa

Deseu la implementació de la classe MatriuDispersa al fitxer matrius.py (mòdul matrius).

Per implementar aquesta classe, haureu de dissenyar els mètodes que donen suport a les operacions i funcions esmentades a l’apartat anterior. Cal que tingueu en compte les següents observacions:

1. Per representar els valors diferents de zero de la matriu caldrà un atribut addicional, per exemple:

   matrius.MatriuDispersa.vals

   Diccionari que conté únicament les posicions amb els valors no nuls de la matriu. En aquest diccionari, la clau serà una tupla amb els índexs enters (i,j) de cada posició no nul·la i el valor associat serà el real no nul \(m_{i,j}\) que hi ha a la posició \((i,j)\) de la matriu. Per exemple, el diccionari {(2, 2): 9.4, (2, 9): -0.4, (3, 1): -0.04, (4,5): 1.2} representa una matriu amb només quatre termes no nuls. Si es tracta d’una matriu de 5 files i 10 columnes, la matriu corresponent és aquesta:

   \[\begin{split}\begin{pmatrix} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 9.4 & 0 & 0 & 0 & 0 & 0 & 0 & -0.4 & 0 \\ -0.04 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1.2 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{pmatrix}\end{split}\]

2. Quan es crea una instància a la classe MatriuDispersa, aquesta representa una matriu amb tots els valors iguals a zero. Per exemple:

   >>> from matrius import MatriuDispersa
   >>> m  = MatriuDispersa(3, 4)
   >>> m[1, 1]
   0.0
   

3. El mètode __init__ haurà d’inicialitzar els atributs nfils i ncols a partir dels paràmetres nfiles i ncolumnes. També haurà d’inicialitzar el diccionari vals tenint en compte el que s’ha explicat en el punts anteriors.

4. La consulta i l’assignació a una posició de la matriu m[f, c] provoquen un error de tipus: IndexError si no es compleix que \(1 \le f \le\) nfils i \(1 \le c \le\) ncols.

   Per exemple:

   >>> m[0, 0]
   Traceback (most recent call last):
     File "<stdin>", line 1, in <module>
     File "/home/my_user/matrius.py", line 13, in __getitem__
       raise IndexError
   IndexError
   

5. Quan s’assigna un valor a una posició de la matriu m[f, c] = c, cal tenir en compte que en el diccionari vals hi ha només els valors no nuls de la matriu.

6. La función len() aplicada a una matriu dispersa retorna el nombre de valors diferents de zero de la matriu, és a dir el nombre d’elements emmagatzemats en el diccionari vals. Per exemple:

   >>> m  = MatriuDispersa(3, 4)
   >>> m[2, 3] = 23
   >>> len(m)
   1
   

7. La funció str aplicada a una matriu dispersa retorna un string amb tots els valors de la matriu. Cada fila es representa en una línia de text i cada valor està separat per un únic espai en blanc. Els valors es mostren sempre amb un únic decimal. Per exemple:

   >>> m  = MatriuDispersa(3, 4)
   >>> m[1, 1] = 23
   >>> m[3, 4] = 67
   >>> str(m)
   '23.0 0.0 0.0 0.0\n0.0 0.0 0.0 0.0\n0.0 0.0 0.0 67.0'
   

La funció identitat()

Al fitxer matrius.py, però fora de la classe MatriuDispersa, definiu-hi la funció següent:

matrius.identitat(n)

Retorna la MatriuDispersa identitat de dimensió n.

Nota

Disposeu dels fitxers matrius-1.txt i matrius-2.txt amb jocs de prova.

Solució

Disposeu d’una solució al fitxer matrius.py.