# CS 101 Lab: Week # 10 (Lists, sorting, and matrices) <ul class="pager"> <li><a href="../w09/">← Previous lab</a></li> <li><a href="../w11/">Next lab →</a></li> </ul> It is planned to cover the following during the 10th week of CS101 labs. --- ## Outline: Lists, sorting, and matrices 1. First, **conclude the last assignment from week 9 about lists and sorting algorithms**, 2. Problem 9 given below will introduce you to **matrices computation** with Python, by representing a matrix as a **list of list** (list of line vectors). You will have to write two functions, one for **adding** two matrices together (`add_matrix`) and one for multiplying two matrices (`product_matrix`). The goal is to observe how the computation times of the two operations on matrices increase when their sizes increase. 3. The bonus assignment is using the `product_matrix` function to raise a matrix $M$ to an integer power $k$, with two approaches. --- ## Assignments (for today): ### Problem 1 to 8 Use the assignment sheet from last week (week 9) about lists and sorting algorithms. ------ ### Problem 9 Today we will introduce matrices in Python, by representing a matrix as a **list of list** (list of line vectors). For example, the matrix $M = \left[\\begin{matrix} 1 & 2 & 3 \\\\ 4 & 5 & 6 \\\\ 7 & 8 & 9 \\end{matrix}\right]$ has three line vectors, $x\_1 = [1 ~ 2 ~ 3], x\_2 = [4 ~ 5 ~ 6], x\_3 = [7 ~ 8 ~ 9]$. So in Python, this matrix can be written as `M = [x_1, x_2, x_3]`, ie `M = [ [1, 2, 3], [4, 5, 6], [7, 8, 9] ]` is a list of $3$ lists (each of the same size, $3$ also here). > **Be cautious** about the number of commas `,`, and opening and closing square brackets `[` and `]`. You will have to write two functions, one for **adding** two matrices together (`add_matrix`) and one for multiplying two matrices (`product_matrix`). . 1. Write one function that will **add** two matrices together (you can call it `add_matrix`). We remind that if $C = A + B$, then each of its coefficient is given by $C\_{i, j} = A\_{i, j} + B\_{i, j}$ (for $0 \\leq i \\leq n-1$, $0 \\leq j \\leq n-1$). 2. Write a second function that will **multiply** two matrices together (you can call it `add_matrix`). We remind that if $C = A \\times B$, then each of its coefficient is given by $C\_{i, j} = \\sum\\limits\_{k = 0}^{n-1} \\left(A\_{i, k} \\times B\_{k, j} \\right)$. 3. *Hint:* for 1. and 2., you can begin by assuming that $A$ and $B$ are both squares and of the same size $n \\in \\mathbb{N}^{\*}$. After, try to improve your two functions so that they will accept non-square matrices ($A, B$ of common size $(n, m)$ for `add_matrix` and $A$ of size $(n, m)$ and $B$ of size $(m, p)$ for `product_matrix`). 4. By using the `random` module (as seen last week) and its function `randint`, write a function called `random_matrix` that shall take one argument ($n$), the size of the random matrix _we want to produce_. For example, `random_matrix(2)` will generate a matrix $M$ of size $(n, n)$, filled with **random integers** (given by $n^2$ calls to the function `random.randint`). Use the Python documentation to understand by yourself about this `random.randint` function. Finally, try your `random_matrix` function for small sizes ($1, 2, 3$), and bigger sizes ($n = 100$, $n = 1000 ?$). 5. Conclude by evaluating the computation time needed to *add* two random matrices (with your function `add_matrix`) and to *multiply* them. Try to see how these two computation times increase when $n$ increases (see below to know how to measure this execution time). ------ ### How to measure the execution time of a function? In the IPython console or when your script is executing in the IPython console under the Spyder, the best solution is to use a *magic* command called `%timeit` (the `%` symbol is important!). It is an excellent and simple way te measure the execution time of any *one-line statement*. #### Examples with `add_matrix` <blockquote><pre><code class="language-python" style="font-size:130%;">>>> %timeit add_matrix(random_matrix(100), random_matrix(100)) 10 loops, best of 3: 33.7 ms per loop </code></pre></blockquote> This tells you that it took about $34 \\mathrm{ms}$ to add two (random) matrices of size $(100, 100)$. <blockquote><pre><code class="language-python" style="font-size:130%;">>>> %timeit add_matrix(random_matrix(1000), random_matrix(1000)) 1 loops, best of 3: 3.42 s per loop </code></pre></blockquote> This second example tells you that it took about $3.42 \\mathrm{s}$ to add two (random) matrices of size $(1000, 1000)$. Our addition functon is in $O(n^2)$, so going from $n=100$ to $n=1000$ corresponds to multiply $n^2$ by $10^2 = 100$. Therefore, we can be proud to see that the computation time has also been multiplied by $100$ ! (indeed $3.4 \\mathrm{s} = 100 \\times 34 \\mathrm{ms} \\dots$). > You can do more examples like this if you want to practice, or observe the same effect for other values (try to go from $n=500$ to $n=1000$, it will also take a time $4$ times greater). > It took 1.06 seconds for $n=500$ on my laptop, and 4.28 seconds for $n=1000$ : nice right? --- #### Examples with `product_matrix` <blockquote><pre><code class="language-python" style="font-size:130%;">>>> %timeit product_matrix(random_matrix(100), random_matrix(100)) 1 loops, best of 3: 263 ms per loop </code></pre></blockquote> This tells you that it took about $265 \\mathrm{ms}$ to multiply two (random) matrices of size $(100, 100)$. For this `product\_matrix` function, you now need to figure out **by yourself** what is its order of complexity: - You can first do this *analytically*, based either on the mathematical formula for the product (given above), or the Python code of your functions (count the number and sizes of interlaced loops). - And then verify *concretely* (with this `%timeit` command, as for `add\_matrix`) that the order of time complexity you found is correct\footnote{It will probably be one of $O(1)$, $O(n)$, $O(n \\log(n))$, $O(n^2)$, $O(n^2 \\log(n))$, $O(n^3)$ or $O(n^4)$ $\\dots$}. - You can take three values for $n$ (e.g. $100, 200$ and $400$), and try to see how the computation time evolves. ----- #### Solution <blockquote><pre><code class="language-python" style="font-size:130%;">>>> %timeit product_matrix(random_matrix(200), random_matrix(200)) 1 loops, best of 3: 2.1 s per loop </code></pre></blockquote> This second example tells you that it took about $2.1 s$ to multiply two (random) matrices of size $(200, 200)$. Our multiplication function is in $O(n^3)$, so going from $n=100$ to $n=200$ corresponds to multiply $n^2$ by $2^3 = 8$. <div style="overflow:hidden; display:block; margin-left: auto; margin-right:auto; text-align:center; "> <img style="width: 100%;" alt="%timeit magic command in IPython" src="timeit.png" /> <p>Demo of the `%timeit` magic command in IPython.</p> </div> Therefore, we can be proud to see that the computation time has also been multiplied by $8$ ! (indeed $2.1 s = 8 \\times 263 ms \\dots$). > You can do more examples like this if you want to practice, or observe the same effect for other values (try to go from $n=200$ to $n=400$, it should also take a time $8$ times greater). > It took 39 seconds for $n=500$ on my laptop, and 5 minutes 24 seconds for $n=1000$ : nice right? ------ ### Bonus (if you are *really in advance*) about **matrix exponentation** 1. _Bonus:_ after writing the product of two matrices (Problem 9 Question 2), write a small function `square_matrix` that will raise a matrix $M$ to the power $2$ (ie. computes $M^2 = M \\times M$), 2. _Bonus:_ write a function `pow_matrix` that raises its first argument $M$ to the power of any non-negative integer, $k$ (its second argument). Calling this function with `pow_matrix(M, k)` will compute (and _return_) $M^k$. 3. _Bonus:_ what is the time complexity of this function `pow_matrix`? (in term of size $n$ of $M$ and in term of $k$). Can you improve it? _Hint:_ remember the recursive algorithm for quick exponentation saw in Prof. Arya's lecture? You could adapt it here ($M^{2k} = {(M^k)}^{2}$ and $M^{2k+1} = M {(M^k)}^{2}$). --- ## Example programs > All this will also be on Moodle by next Friday, along with the solution for lab #9. #### For the problem 9.1 <blockquote><pre><code class="language-python" style="font-size:130%;">def add_matrix(A, B): """ Add two square matrices A and B (of the same size). There is O(n^2) elementary additions, and O(n^2) memory accesses (then all take a worst case time of O(n) because all the lists are of size n). The function uses an extra matrix C of size O(n^2). """ n = len(A) # We create an empty matrix of size (n, n), filled with zero C = [ [0]\*n ]\*n # We assume that A and B are square matrices for i in xrange(n): for j in xrange(n): C[i][j] = A[i][j] + B[i][j] # Finally this matrix C is returned return C </code></pre></blockquote> We can do this in one line also! We use a **lambda** statement, with two arguments, and two **list comprehension** : <blockquote><pre><code class="language-python" style="font-size:130%;">add_matrix = lambda A, B: [ [ A[i][j] + B[i][j] for j in xrange(len(A)) ] for i in xrange(len(A)) ] </code></pre></blockquote> #### For the problem 9.2 <blockquote><pre><code class="language-python" style="font-size:130%;">def product_matrix(A, B): """ Multiply two square matrices A and B (of the same size). There is O(n^2) additions and O(n^3) multiplications, and O(n^3) memory accesses (then all take a worst case time of O(n) because all the lists are of size n) The function uses an extra matrix C of size O(n^2). """ n = len(A) # We create an empty matrix of size (n, n), filled with zero C = [ [0]\*n ]\*n # We assume that A and B are square matrices for i in xrange(n): for j in xrange(n): C[i][j] = sum([ A[i][k] * B[k][j] for k in xrange(n) ]) # We use the builtin sum function, with a list comprehension to avoid a 3rd loop # Finally this matrix C is returned return C </code></pre></blockquote> We can again do this in one line also: <blockquote><pre><code class="language-python" style="font-size:130%;">product_matrix = lambda A, B: [ [ sum([ A[i][k] * B[k][j] for k in xrange(len(A)) ]) for j in xrange(len(A)) ] for i in xrange(len(A)) ] </code></pre></blockquote> #### For the problem 9.4 <blockquote><pre><code class="language-python" style="font-size:130%;">import random def random_matrix(n): """ Random matrix of size (n, n) filled with integers taken in [-10, 10]. """ # We create an empty matrix of size (n, n), filled with zero C = [ [0]\*n ]\*n for i in xrange(n): for j in xrange(n): C[i][j] = random.randint(-10, 10) return C </code></pre></blockquote> We can again do this in two lines also: <blockquote><pre><code class="language-python" style="font-size:130%;">from random import randint random_matrix = lambda n: [ [ random.randint(-10, 10) for j in xrange(n) ] for i in xrange(n) ] </code></pre></blockquote> --- <div class="alert"> <h3>This outline might change</h3> <p>This outline for the lab #10 is a preliminary version, it might change.<br> If needed, please <a href="https://bitbucket.org/lbesson/cs_101/issues/new" title="It's free, open to anyone, quick and easy!">fill a bug report</a>?</p> </div> --- <ul class="pager"> <li class="previous"><a href="../w09/">← Previous lab</a></li> <li class="next"><a href="../w11/">Next lab →</a></li> </ul>