OOP Matrix Challenge¶
Download exercises zip¶
We want to model operations on IMMUTABLE matrices, the object oriented way.
You have a generic interface called Matrix
in file matrix.py
, and you have to implement two descendants of the interface, DenseMatrix
and SparseMatrix
.
IMPORTANT: work in group and share tests!
You will make a lot of mistakes, some hard to debug: help yourself by writing test cases, we also invite you to share the tests (not the solutions!) with your fellow students.
Please note there are many cornercases, even if stuff seems to work there will probably occasions where it fails - you won’t probably be able to find them all on your own.
What to do¶
unzip exercises in a folder, you should get something like this:
oop
matrix.py
oop-matrix-chal.ipynb
.
.
You can ignore the notebook, and edit .py
files in Visual Studio Code.
DenseMatrix¶
Let’s begin with the simpler implementation, which is DenseMatrix
: you will code it by storing data inside lists of lists.
Create a new file dense_matrix.py
and declare a class DenseMatrix
which inherits from Matrix
. Copy inside all the methods definitions from Matrix
.
from matrix import Matrix
class DenseMatrix(Matrix):
""" A Matrix represented internally as a list of lists
When creating it from list of lists, perform a DEEP COPY of the input
and store it inside a private field you will call _cells (use ONE underscore)
"""
Constructors and printing¶
Generally first methods we implement are the constructor and methods to show the class content such as __str__
and __repr__
. All methods are documented in the matrix.py
interface, let’s see now the constructor. Copy paste the following inside your DenseMatrix
class.
def __init__(self, *args):
"""Initializes the Matrix with either:
One argument: a list of lists
Three arguments: number of rows
number of columns
a list of cell triplets (row_index,col_index,value)
- if number of rows or columns is less than indeces found
in triplets, raise Value Error
In both cases, provided data must allow the creation of a matrix with
at least one row and a column, otherwise raise ValueError
"""
raise Exception("Should be implemented in a descendant of Matrix!")
Constructor as list of lists¶
We see the the constructor takes the special *args
argument, which means it can accept a variable number of arguments. To check for the two cases, you might write something like this:
class DenseMatrix(Matrix):
def __init__(self, *args):
if len(args) == 1: # list of lists
rows = args[0]
# do something ...
elif len(args) == 3:
n,m,triplets = args
# do something
else:
raise ValueError('Expected one or three args!')
You can start by handling only the one argument case, which we will interpret as a list of lists. You can store a deep copy of the list of lists in a private field you can call _cells
. Why should we store a deep copy? It’s a form a so-called defensive-programming: if we store a copy, it’s less likely that a user of our class will later mess with the instance internal data. If we store the data in a field beginning with one underscore _
, we will signal external users we do not want
them to directly access it (notice if they really want they will still be able to do it)
[1]:
from dense_matrix_chal_sol import *
from sparse_matrix_chal_sol import *
[2]:
dma = DenseMatrix([ [0,6,8,0],
[0,0,0,5],
[9,0,7,0] ])
[3]:
dma
[3]:
DenseMatrix([[0, 6, 8, 0], [0, 0, 0, 5], [9, 0, 7, 0]])
[4]:
type(DenseMatrix)
[4]:
type
str and repr¶
Implement __str__
and __repr__
def __str__(self):
""" RETURN a nice human-readable formatted string, possibly like this:
Matrix [ [5,2,6,3],
[8,4,7,4],
[2,1,9,8] ]
- substitute Matrix with the descendant class name
- NOTE: sometimes this representation is impractical (i.e. sparse matrices
with large n/m), in that case use another format of your choice
"""
raise Exception("Should be implemented in a descendant of Matrix!")
def __repr__(self):
""" RETURN one-line string representing a Python expression which would recreate the atrix
"""
raise Exception("Should be implemented in a descendant of Matrix!")
[5]:
str(dma)
[5]:
'DenseMatrix [ [0, 6, 8, 0]\n [0, 0, 0, 5]\n [9, 0, 7, 0] ]'
[6]:
print(dma)
DenseMatrix [ [0, 6, 8, 0]
[0, 0, 0, 5]
[9, 0, 7, 0] ]
[7]:
repr(dma)
[7]:
'DenseMatrix([[0, 6, 8, 0], [0, 0, 0, 5], [9, 0, 7, 0]])'
[8]:
dma
[8]:
DenseMatrix([[0, 6, 8, 0], [0, 0, 0, 5], [9, 0, 7, 0]])
constructor as list of triplets¶
Now extend the constructor to handle also the list of triplets case:
[9]:
dmb = DenseMatrix(3,4, [(0,1,6),(0,2,8),(1,3,5),(2,0,9),(2,2,7)])
[10]:
dmb
[10]:
DenseMatrix([[0, 6, 8, 0], [0, 0, 0, 5], [9, 0, 7, 0]])
[11]:
print(dmb)
DenseMatrix [ [0, 6, 8, 0]
[0, 0, 0, 5]
[9, 0, 7, 0] ]
shape¶
Implement shape
method:
def shape(self):
"""RETURN the number of rows and columns as a tuple
"""
[12]:
dma.shape() # NOTE the ()
[12]:
(3, 4)
Brackets operator¶
Override the square bracket operator by reimplementing the method __getitem__
IMPORTANT: Read carefully Python documentation!!
def __getitem__(self, key):
"""Overrides default bracket access behaviour.
key is whatever the user passes within the brackets, in our case
we want user to be able to write
my_mat[2,5] to access element at row 2 and column 5
NOTE 1: if the user types 2,5 inside the brackets, Python will actually
generate a TUPLE (2,5) so that is the key type you should
accept (a tuple of *exactly two* integers)
NOTE 2: Since this method signature is defined by Python documention:
https://docs.python.org/3/reference/datamodel.html#object.__getitem__
you MUST write it respecting ALL the indications of the docs, in particular
think also about what should happen in undesired scenarios when
the user enters a key of wrong type, wrong value, etc as described
in the documentation
"""
[13]:
print(dma)
DenseMatrix [ [0, 6, 8, 0]
[0, 0, 0, 5]
[9, 0, 7, 0] ]
[14]:
dma[0,1]
[14]:
6
[15]:
dma[0,2]
[15]:
8
Negative indeces should also be supported:
[16]:
dma[0,-3]
[16]:
6
nonzero¶
def nonzero(self):
"""Return a list of triplets (row index, column index, value) of non-zero cells,
in no particular order.
"""
Since we stored the rows in a private field _cells
, we have to offer users other ways to access data. For example, by calling nonzero()
method users should be able to obtain non-zero values, as a list of triplets with row index, column index and value of cells. You might wonder what the utility is, after we already implemented the brackets operator: the reason will become clearer when you start implementing methods that need to visit a generic Matrix
, like the following ones.
[17]:
print(dma)
DenseMatrix [ [0, 6, 8, 0]
[0, 0, 0, 5]
[9, 0, 7, 0] ]
[18]:
dma.nonzero()
[18]:
[(0, 1, 6), (0, 2, 8), (1, 3, 5), (2, 0, 9), (2, 2, 7)]
isclose¶
Implement this method:
DO NOT MAKE ASSUMPTIONS ABOUT other
CLASS!
In the implementation, use other
like if it were a generic Matrix
, it might not always be a DenseMatrix
. So the only way to access elements will be either by using the brackets operator or by calling nonzero()
def isclose(self, other, delta):
""" RETURN True if each cell in this matrix is within a delta distance
from other Matrix. RETURN False if any cell couple differs more than delta.
- if matrices have different dimensions, raise ValueError
"""
[19]:
print(dma)
DenseMatrix [ [0, 6, 8, 0]
[0, 0, 0, 5]
[9, 0, 7, 0] ]
[20]:
dmd = DenseMatrix([ [0, 5.9, 8, 0],
[0, 0, 0.1, 5],
[9.15, -0.1, 7, 0.1] ])
dma.isclose(dmd, 0.2)
[20]:
True
[21]:
dma.isclose(dmd, 0.05)
[21]:
False
Equality¶
Override ==
operator:
[22]:
dma = DenseMatrix([ [0,6,8,0],
[0,0,0,5],
[9,0,7,0] ])
dmb = DenseMatrix(3,4, [(0,1,6),(0,2,8),(1,3,5),(2,0,9),(2,2,7)])
dma == dmb
[22]:
True
Notice in this case, since we want in general to check equality to the last bit, we will want to check that other
is actually a DenseMatrix
, otherwise we will return False
[23]:
dma == 'ciao'
[23]:
False
Equality with a different shape should just return False
, without raising exceptions:
[24]:
dma == DenseMatrix([[2,4],
[9,3]])
[24]:
False
Equality with different numbers:
[25]:
dmc = DenseMatrix([ [1,2,3,4],
[6,7,8,9],
[10,11,12,13] ])
dma == dmc
[25]:
False
Sum¶
Override +
operator so can sum other Matrix
instances:
DO NOT MAKE ASSUMPTIONS ABOUT other
CLASS!
In the implementation, use other
like if it were a generic Matrix
, it might not always be a DenseMatrix
. So the only way to access elements will be either by using the brackets operator or by calling nonzero()
[26]:
dma = DenseMatrix([ [0,6,8,0],
[0,0,0,5],
[9,0,7,0] ])
dmc = DenseMatrix([ [1,2,3,4],
[6,7,8,9],
[10,11,12,13] ])
[27]:
print(dma + dmc)
DenseMatrix [ [1, 8, 11, 4]
[6, 7, 8, 14]
[19, 11, 19, 13] ]
Note dma
and dmc
where not modified:
[28]:
print(dma)
DenseMatrix [ [0, 6, 8, 0]
[0, 0, 0, 5]
[9, 0, 7, 0] ]
[29]:
print(dmc)
DenseMatrix [ [1, 2, 3, 4]
[6, 7, 8, 9]
[10, 11, 12, 13] ]
Multiplication¶
Override *
operator so we can multiply by a scalar:
[30]:
print(dma * 2)
DenseMatrix [ [0, 12, 16, 0]
[0, 0, 0, 10]
[18, 0, 14, 0] ]
DO NOT MAKE ASSUMPTIONS ABOUT other
CLASS!
In the implementation, use other
like if it were a generic Matrix
, it might not always be a DenseMatrix
. So the only way to access elements will be either by using the brackets operator or by calling nonzero()
Again multiplication by a scalar does not modify the original:
[31]:
print(dma)
DenseMatrix [ [0, 6, 8, 0]
[0, 0, 0, 5]
[9, 0, 7, 0] ]
Multiplying a scalar by a matrix should also work:
[32]:
print(2 * dma)
DenseMatrix [ [0, 12, 16, 0]
[0, 0, 0, 10]
[18, 0, 14, 0] ]
Again original dma
was not changed:
[33]:
print(dma)
DenseMatrix [ [0, 6, 8, 0]
[0, 0, 0, 5]
[9, 0, 7, 0] ]
Matrix vector multiplication¶
Next implement support for multiplication of a matrix by a properly dimensioned vector on the right, which must have the same number of rows as the matrix number of columns:
matrix vector result
\j 012
i 0 aaa v0 a00*v0 + a01*v1 + a02*v2
1 aaa v1 a10*v0 + a11*v1 + a12*v2
2 aaa v2 a20*v0 + a21*v1 + a22*v2
3 aaa a30*v0 + a31*v1 + a32*v2
The result will have the same number of rows as the matrix.
DO NOT MAKE ASSUMPTIONS ABOUT other
CLASS!
In the implementation, use other
like if it were a generic Matrix
, it might not always be a DenseMatrix
. So the only way to access elements will be either by using the brackets operator or by calling nonzero()
[34]:
dmveca = DenseMatrix([[1],[2],[3],[4]])
[35]:
print(dmveca)
DenseMatrix [ [1]
[2]
[3]
[4] ]
[36]:
print(dma)
DenseMatrix [ [0, 6, 8, 0]
[0, 0, 0, 5]
[9, 0, 7, 0] ]
[37]:
print(dma * dmveca)
DenseMatrix [ [36]
[20]
[30] ]
Multiplication by a vector does not modify the originals:
[38]:
print(dmveca)
DenseMatrix [ [1]
[2]
[3]
[4] ]
Notice dimensions must be compatible, this should not work:
>>> print(dma*DenseMatrix([[1],[2]]))
---------------------------------------------------------------------------
TypeError Traceback (most recent call last)
<ipython-input-33-bc850efec5f1> in <module>()
----> 1 print(dma*DenseMatrix([[1],[2]]))
TypeError: unsupported operand type(s) for *: 'DenseMatrix' and 'DenseMatrix'
Vector matrix multiplication¶
Next implement support for multiplication of a matrix by a properly dimensioned horizontal vector on the left, which must have the same number of columns as the matrix number of rows:
ector matrix result
\j 012 0123 0123
i vvv 0 aaaa rrrr
1 aaaa
2 aaaa
res = a00*v0+a10*v1+a20*v2, a01*v0+a11*v1+a21*v2, a02*v0+a12*v1+a22*v2, a03*v0+a13*v1+a23*v2
The result will have the same number of columns as the matrix.
DO NOT MAKE ASSUMPTIONS ABOUT other
CLASS!
In the implementation, use other
like if it were a generic Matrix
, it might not always be a DenseMatrix
. So the only way to access elements will be either by using the brackets operator or by calling nonzero()
[39]:
print(dma)
DenseMatrix [ [0, 6, 8, 0]
[0, 0, 0, 5]
[9, 0, 7, 0] ]
[40]:
dmvecb = DenseMatrix([[1,2,3]])
[41]:
print(dmvecb * dma)
DenseMatrix [ [27, 6, 29, 10] ]
Matrix matrix multiplication¶
This would be the general problem but for the purposes of this challenge, it is not mandatory to support multiplication by a matrix, even if they have compatible dimensions:
>>> print(dma*DenseMatrix([[3,2],
[3,7],
[2,8],
[9,3],]))
---------------------------------------------------------------------------
TypeError Traceback (most recent call last)
<ipython-input-34-ed1ad440c418> in <module>()
2 [3,7],
3 [2,8],
----> 4 [9,3],]))
TypeError: unsupported operand type(s) for *: 'DenseMatrix' and 'DenseMatrix'
SparseMatrix¶
If you’ve arrived so far, congratulations, that was quite a journey. But only half of it! We’ve seen matrices as lists of lists for a long time, let’s now see if we can save some space. Many real-world matrices have often most cells set to zero, so it would be convenient to avoid storing in memory those cells, and reserve space only for non-zero valued cells. There are many ways to do it (see Wikipedia), in this challenge we will adopt the simplest which is the so-called Dictionary of Keys (DOK in short). DOK consists of a dictionary that maps (row, column)-pairs to the value of the elements. Elements that are missing from the dictionary are assumed to be zero.
Now we can see the real reason why we supported also a constructor with triplets: if the goal of using a SparseMatrix is to avoid creating huge tables in memory, initializing it with a list of lists would defeat the purpose! In what follows, sometimes we may still use the list of lists initialization, but that would only be for clarity purposes.
Sparse constructors and printing¶
Create a new file sparse_matrix.py
and copy inside this with the method definitions you find in matrix.py
as done before.
from matrix import Matrix
class SparseMatrix(Matrix):
""" A SparseMatrix is a matrix which contains very few non-zero elements.
In this implementation, storage is modelled as a dictionary of keys (DOK in short),
where each key is a tuple of cell coordinates which maps to a non-zero cell value.
NOTE: *NEVER* store zero-valued cells.
"""
Ffollow the same implementation order as before, so start with the constructor __init__
, __str__
and __repr__
overrides. Note this time our class implementation will have a dictionary as private _cells
field.
With sparse matrices we can have a big 30x20 matrix and occupy very little memory:
[42]:
sma = SparseMatrix(30,20, [(26,17,3),(24,11,5)])
You can save the shape inside a private _shape
field.
Since shape can be much bigger than atcual data, with __str__
you must show the internal dictionary and the shape:
[43]:
print(sma)
SparseMatrix {
(24, 11): 5,
(26, 17): 3
}
shape: (30, 20)
__repr__
will show the triplets constructor:
[44]:
repr(sma)
[44]:
'SparseMatrix(30,20, [(24, 11, 5), (26, 17, 3)])'
[45]:
sma
[45]:
SparseMatrix(30,20, [(24, 11, 5), (26, 17, 3)])
Sparse Brackets operator¶
Override the square bracket operator by reimplementing the method __getitem__
CAREFUL!
Even more than before, you have to super-carefully read Python documentation!!
To respect Python documentation, this time you can’t rely on built-in errors and features of lists as you probably did in the DenseMatrix
case, so you will have to write a lot of if
that check for various possible errors (bad types, values, etc) and raise the appropriate errors (IndexError
, TypeError
, KeyError
, etc)
Implement brackets operator:
[47]:
sma[24,11]
[47]:
5
[48]:
sma[26,17]
[48]:
3
[49]:
sma[29,3] # shouldn't explode
[49]:
0.0
Support negative numbers:
[50]:
sma[-6,11]
[50]:
5
[51]:
sma[29,-2]
[51]:
0.0
Sparse nonzero¶
This is very important, as it allows iterating the data structure in an efficient way - depending on the shape, trying all the couples i
, j
with the square brackets might be prohibitively costly.
[52]:
sma.nonzero()
[52]:
[(24, 11, 5), (26, 17, 3)]
Sparse isclose¶
Be careful to write generic code, and avoid iterating all possible i,j couples - you should only look into nonzero ones.
[53]:
print(sma)
SparseMatrix {
(24, 11): 5,
(26, 17): 3
}
shape: (30, 20)
[54]:
sma.isclose(SparseMatrix(30,20, [(24, 11, 4.9), (26, 17, 3.1)]), 0.2)
[54]:
True
[55]:
sma.isclose(SparseMatrix(30,20, [(24, 11, 4.9), (26, 17, 3.1)]), 0.05)
[55]:
False
[56]:
sma.isclose(SparseMatrix(30,20, [(24, 11, 4.9), (26, 17, 3.1), (13,18,0.5)]), 0.2)
[56]:
False
[57]:
sma.isclose(SparseMatrix(30,20, [(24, 11, 4.9), (26, 17, 3.1), (13,18,0.1)]), 0.2)
[57]:
True
[58]:
sma.isclose(SparseMatrix(30,20, [(24, 11, 4.9), (26, 17, 3.1), (13,18,-0.1)]), 0.2)
[58]:
True
The interesting part comes when we try isclose
with another class, like DenseMatrix
. If you wrote general enough code, only assuming other
is a generic Matrix
the following should work without particular effort:
[59]:
smp = SparseMatrix([[1, 0, 3],
[4, 5, 0]])
dmp = DenseMatrix( [[1.1, 0.1, 2.9],
[4.05, 4.9, -0.05]])
[60]:
smp.isclose(dmp, 0.2)
[60]:
True
[61]:
smp.isclose(dmp, 0.05)
[61]:
False
[62]:
dmp.isclose(smp, 0.2)
[62]:
True
[63]:
dmp.isclose(smp, 0.05)
[63]:
False
Sparse equality¶
Be careful to write generic code, and avoid iterating all possible i,j couples - you should only look into nonzero ones.
[64]:
sma
[64]:
SparseMatrix(30,20, [(24, 11, 5), (26, 17, 3)])
[65]:
smb = SparseMatrix(30,20, [(24, 11, 5), (26, 17, 3)])
[66]:
sma == sma
[66]:
True
[67]:
sma == smb
[67]:
True
[68]:
sma == SparseMatrix(30,20, [(24, 11, 5), (26, 17, 123)])
[68]:
False
[69]:
sma == SparseMatrix(30,20, [(24, 11, 5), (26, 17, 3), (5,10,6)])
[69]:
False
Equality among different types should always be False
, even if they descend from the same ancestor:
[70]:
SparseMatrix([[1,2],[3,4]]) == DenseMatrix([[1,2],[3,4]])
[70]:
False
[71]:
DenseMatrix([[1,2],[3,4]]) == SparseMatrix([[1,2],[3,4]])
[71]:
False
Sparse sum¶
Be careful to write generic code, and avoid iterating all possible i,j couples - you should only look into nonzero ones.
[72]:
smq = SparseMatrix([[1,2,0],
[4,0,6]])
dmq = DenseMatrix([[0,8,0],
[0,7,3]])
[73]:
print(smq + smq)
SparseMatrix {
(0, 1): 4,
(1, 2): 12,
(1, 0): 8,
(0, 0): 2
}
shape: (2, 3)
Again the interesting bit is when you try summing among different classes:
[74]:
print(smq + dmq)
SparseMatrix {
(0, 1): 10,
(1, 2): 9,
(1, 0): 4,
(0, 0): 1,
(1, 1): 7
}
shape: (2, 3)
[75]:
print(dmq + smq)
DenseMatrix [ [1, 10, 0.0]
[4, 7.0, 9] ]
Sparse multiplication¶
As always, be careful writing general code, and avoid iterating all possible i,j couples - you should only look into nonzero ones.
Sparse matrix vector multiplication¶
[76]:
smq = SparseMatrix([[1,0,3],
[4,5,0]])
smvecq = SparseMatrix([[1],
[0],
[3]])
print(smq * smvecq)
SparseMatrix {
(1, 0): 4.0,
(0, 0): 10
}
shape: (2, 1)
Let’s try mixing types:
[77]:
dmq = DenseMatrix([[1,0,3],
[4,5,0]])
dmvecq = DenseMatrix([[1],
[0],
[3]])
print(smq * dmvecq)
SparseMatrix {
(1, 0): 4,
(0, 0): 10
}
shape: (2, 1)
[78]:
print(dmq * smvecq)
DenseMatrix [ [10.0]
[4.0] ]
Sparse vector matrix multiplication¶
[79]:
smvecr = SparseMatrix([[1,2,0]])
smr = SparseMatrix([ [0, 6, 8, 0],
[0, 0, 0, 5],
[9, 0, 7, 0] ])
print(smvecr * smr)
SparseMatrix {
(0, 1): 6,
(0, 3): 10,
(0, 2): 8.0
}
shape: (1, 4)
Let’s mix types:
[80]:
dmvecr = DenseMatrix([[1,2,0]])
dmr = DenseMatrix([ [0, 6, 8, 0],
[0, 0, 0, 5],
[9, 0, 7, 0] ])
print(smvecr * dmr)
SparseMatrix {
(0, 1): 6,
(0, 3): 10,
(0, 2): 8.0
}
shape: (1, 4)
[81]:
print(dmvecr * smr)
DenseMatrix [ [0, 6, 8, 10] ]
[ ]: