{"cells": [{"cell_type": "markdown", "metadata": {}, "source": ["# 1A - Enonc\u00e9 3 novembre 2021\n", "\n", "Correction de l'examen du 3 novembre 2021."]}, {"cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [{"data": {"text/html": ["\n", ""], "text/plain": [""]}, "execution_count": 2, "metadata": {}, "output_type": "execute_result"}], "source": ["from jyquickhelper import add_notebook_menu\n", "add_notebook_menu()"]}, {"cell_type": "markdown", "metadata": {}, "source": ["## Exercice 1 : multiplication de matrices\n", "\n", "On a besoin d'une fonction qui mesure le temps d'ex\u00e9cution d'une fonction."]}, {"cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [{"data": {"text/plain": ["0.10280692000000005"]}, "execution_count": 3, "metadata": {}, "output_type": "execute_result"}], "source": ["import time\n", "\n", "def mesure_temps_fonction(fct, N=100):\n", " begin = time.perf_counter()\n", " for i in range(N):\n", " fct()\n", " return (time.perf_counter() - begin) / N\n", "\n", "mesure_temps_fonction(lambda: time.sleep(0.1), N=10)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["### Q1 : Pourquoi (m1 @ m2) @ m3 est-il plus lent que m1 @ (m2 @ m3) ? (2 points)\n", "\n", "Il y a deux options possible. Il suffit de compter le nombre d'op\u00e9rations dans chaque option. Le co\u00fbt d'une multiplication $M_{ab} \\times m_{bc}$ est de l'ordre de $O(abc)$. Donc :\n", "\n", "* cout((m1 @ m2) @ m3) ~ O(997 * 93 * 1003 + 997 * 1003 * 97) = 189998290\n", "* cout(m1 @ (m2 @ m3)) ~ O(93 * 1003 * 97 + 997 * 93 * 97) = 18042000\n", "\n", "La seconde option est dix fois plus rapide."]}, {"cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["189998290 18042000\n"]}], "source": ["print(997 * 93 * 1003 + 997 * 1003 * 97, 93 * 1003 * 97 + 997 * 93 * 97)"]}, {"cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [{"data": {"text/plain": ["0.009560690999999987"]}, "execution_count": 5, "metadata": {}, "output_type": "execute_result"}], "source": ["import numpy\n", "\n", "m1 = numpy.random.randn(997, 93)\n", "m2 = numpy.random.randn(93, 1003)\n", "m3 = numpy.random.randn(1003, 97)\n", "\n", "mesure_temps_fonction(lambda: m1 @ m2 @ m3)"]}, {"cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [{"data": {"text/plain": ["0.009846866999999992"]}, "execution_count": 6, "metadata": {}, "output_type": "execute_result"}], "source": ["mesure_temps_fonction(lambda: (m1 @ m2) @ m3)"]}, {"cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [{"data": {"text/plain": ["0.001004321000000008"]}, "execution_count": 7, "metadata": {}, "output_type": "execute_result"}], "source": ["mesure_temps_fonction(lambda: m1 @ (m2 @ m3))"]}, {"cell_type": "markdown", "metadata": {}, "source": ["### Q2 : Ecrire une fonction qui calcule le nombre d'operations dans une multiplication de deux matrices (2 points)"]}, {"cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [{"data": {"text/plain": ["185998326"]}, "execution_count": 8, "metadata": {}, "output_type": "execute_result"}], "source": ["def n_ops(m1_shape, m2_shape):\n", " return m1_shape[0] * m2_shape[1] * m1_shape[1] * 2\n", "\n", "n_ops(m1.shape, m2.shape)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["### Q3 : Ecrire une fonction qui retourne le meilleur co\u00fbt d'une multiplication de deux matrices et la meilleure option (2 points)"]}, {"cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [{"data": {"text/plain": ["(36084000, 1)"]}, "execution_count": 9, "metadata": {}, "output_type": "execute_result"}], "source": ["def n_ops_3(sh1, sh2, sh3):\n", " m1_m2m3 = n_ops(sh1, (sh2[0], sh3[1])) + n_ops(sh2, sh3)\n", " m1m2_m3 = n_ops(sh1, sh2) + n_ops((sh1[0], sh2[1]), sh3)\n", " if m1m2_m3 < m1_m2m3:\n", " return m1m2_m3, 2\n", " else:\n", " return m1_m2m3, 1\n", " \n", "n_ops_3(m1.shape, m2.shape, m3.shape)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["### Q4 : Ecrire une fonction qui effectue le produit de trois matrices le plus rapidement possible (2 points)"]}, {"cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [], "source": ["from numpy.testing import assert_almost_equal\n", "\n", "def produit3(m1, m2, m3):\n", " cout, meilleur = n_ops_3(m1.shape, m2.shape, m3.shape)\n", " if meilleur == 2:\n", " return (m1 @ m2) @ m3\n", " else:\n", " return m1 @ (m2 @ m3)\n", "\n", "\n", "assert_almost_equal(produit3(m1, m2, m3), m1 @ (m2 @ m3))"]}, {"cell_type": "markdown", "metadata": {}, "source": ["### Q5 : V\u00e9rifiez que vous retrouvez les m\u00eames r\u00e9sultats avec la fonction `mesure_temps` (2 points)"]}, {"cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [{"data": {"text/plain": ["0.0011657070000000048"]}, "execution_count": 11, "metadata": {}, "output_type": "execute_result"}], "source": ["mesure_temps_fonction(lambda: produit3(m1, m2, m3))"]}, {"cell_type": "markdown", "metadata": {}, "source": ["On v\u00e9rifie que c'est \u00e9gal \u00e0 :"]}, {"cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [{"data": {"text/plain": ["0.0011010209999999887"]}, "execution_count": 12, "metadata": {}, "output_type": "execute_result"}], "source": ["mesure_temps_fonction(lambda: m1 @ (m2 @ m3))"]}, {"cell_type": "markdown", "metadata": {}, "source": ["**Ici, vous avez le choix entre faire les questions 6 \u00e0 9 ou les questions 9 et 10.**"]}, {"cell_type": "markdown", "metadata": {}, "source": ["### Q6 : Ecrire une fonction qui retourne le meilleur co\u00fbt d'une multiplication de 4 matrices et la meilleure option (3 points)"]}, {"cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [], "source": ["m4 = numpy.random.randn(97, 20)"]}, {"cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [{"data": {"text/plain": ["(11331640, 1)"]}, "execution_count": 14, "metadata": {}, "output_type": "execute_result"}], "source": ["def n_ops_4(sh1, sh2, sh3, sh4):\n", " m1_m2m3m4 = n_ops(sh1, (sh2[0], sh4[1])) + n_ops_3(sh2, sh3, sh4)[0]\n", " m1m2_m3m4 = n_ops(sh1, sh2) + n_ops((sh1[0], sh2[1]), (sh3[0], sh4[1])) + n_ops(sh3, sh4)\n", " m1m2m3_m4 = n_ops_3(sh1, sh2, sh3)[0] + n_ops((sh1[0], sh3[1]), sh4)\n", " m = min(m1_m2m3m4, m1m2_m3m4, m1m2m3_m4)\n", " if m == m1_m2m3m4:\n", " return m, 1\n", " if m == m1m2_m3m4:\n", " return m, 2\n", " return m, 3\n", "\n", "n_ops_4(m1.shape, m2.shape, m3.shape, m4.shape)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["### Q7 : Ecrire une fonction qui effectue le produit de 4 matrices le plus rapidement possible (3 points)"]}, {"cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [{"data": {"text/plain": ["0.000988687999999982"]}, "execution_count": 15, "metadata": {}, "output_type": "execute_result"}], "source": ["def produit4(m1, m2, m3, m4):\n", " cout, meilleur = n_ops_4(m1.shape, m2.shape, m3.shape, m4.shape)\n", " if meilleur == 1:\n", " return m1 @ produit3(m2, m3, m4)\n", " if meilleur == 2:\n", " return (m1 @ m2) @ (m3 @ m4)\n", " return produit3(m1, m2, m3) @ m4\n", "\n", "mesure_temps_fonction(lambda: produit4(m1, m2, m3, m4))"]}, {"cell_type": "markdown", "metadata": {}, "source": ["### Q8 : V\u00e9rifiez que vous retrouvez les m\u00eames r\u00e9sultats avec la fonction mesure_temps et la matrice m4. (2 points)"]}, {"cell_type": "code", "execution_count": 15, "metadata": {}, "outputs": [{"data": {"text/plain": ["0.010446371000000027"]}, "execution_count": 16, "metadata": {}, "output_type": "execute_result"}], "source": ["mesure_temps_fonction(lambda: ((m1 @ m2) @ m3) @ m4)"]}, {"cell_type": "code", "execution_count": 16, "metadata": {}, "outputs": [{"data": {"text/plain": ["0.008082993999999956"]}, "execution_count": 17, "metadata": {}, "output_type": "execute_result"}], "source": ["mesure_temps_fonction(lambda: (m1 @ m2) @ (m3 @ m4))"]}, {"cell_type": "code", "execution_count": 17, "metadata": {}, "outputs": [{"data": {"text/plain": ["0.0008713240000000155"]}, "execution_count": 18, "metadata": {}, "output_type": "execute_result"}], "source": ["mesure_temps_fonction(lambda: m1 @ (m2 @ (m3 @ m4)))"]}, {"cell_type": "code", "execution_count": 18, "metadata": {}, "outputs": [{"data": {"text/plain": ["0.0009054390000000013"]}, "execution_count": 19, "metadata": {}, "output_type": "execute_result"}], "source": ["mesure_temps_fonction(lambda: produit4(m1, m2, m3, m4))"]}, {"cell_type": "markdown", "metadata": {}, "source": ["### Q9 : On se penche sur le cas \u00e0 une multiplication de N matrices, combien y a-t-il de multiplications de 2 matrices ? (2 points)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Il y a en toujours *N-1*. On consid\u00e8re le produit $M_1 \\times... \\times M_n$. La multiplication commence toujours par une multiplication de deux matrices cons\u00e9cutives quelles qu'elles soient. On les suppose aux positions $(i, i+1)$. On note le r\u00e9sultat $MM_i$. Apr\u00e8s ce produit, il faudra faire : $(M_1 \\times ... \\times M_{i-1} \\times MM_i \\times M_{i+2} \\times ... \\times M_n$, soit une multiplication de $N-2$ matrices. On obtient le r\u00e9sultat par r\u00e9currence."]}, {"cell_type": "code", "execution_count": 19, "metadata": {}, "outputs": [], "source": []}, {"cell_type": "markdown", "metadata": {}, "source": ["**Ici s'arr\u00eate l'\u00e9nonc\u00e9 pour ceux qui ont choisit de r\u00e9pondre aux question 6 \u00e0 9.**"]}, {"cell_type": "markdown", "metadata": {}, "source": ["### Q10 : R\u00e9soudre l'optimisation de multiplication de N matrices.\n", "\n", "On l'envisage de fa\u00e7on r\u00e9cursive. La premi\u00e8re solution effectue plein de calculs en double mais nous verront comment la modifier."]}, {"cell_type": "code", "execution_count": 20, "metadata": {}, "outputs": [{"data": {"text/plain": ["(11331640, 1)"]}, "execution_count": 21, "metadata": {}, "output_type": "execute_result"}], "source": ["def n_ops_N(shapes):\n", " if len(shapes) <= 1:\n", " raise RuntimeError(\"Unexpected list of shapes: %r.\" % shapes)\n", " if len(shapes) == 2:\n", " return n_ops(*shapes), 1\n", " if len(shapes) == 3:\n", " return n_ops_3(*shapes)\n", " best_cost = None\n", " best_pos = None\n", " for i in range(1, len(shapes)):\n", " if i == 1:\n", " cost = n_ops(shapes[0], (shapes[1][0], shapes[-1][1])) + n_ops_N(shapes[1:])[0]\n", " best_cost = cost\n", " best_pos = i\n", " elif i == len(shapes)-1:\n", " cost = n_ops_N(shapes[:-1])[0] + n_ops((shapes[0][0], shapes[-2][1]), shapes[-1])\n", " if cost < best_cost:\n", " best_cost = cost\n", " best_pos = i\n", " else:\n", " cost = (n_ops_N(shapes[:i])[0] + n_ops_N(shapes[i:])[0] + \n", " n_ops((shapes[0][0], shapes[i-1][1]), (shapes[i][0], shapes[-1][1])))\n", " if cost < best_cost:\n", " best_cost = cost\n", " best_pos = i\n", "\n", " if best_pos is None:\n", " raise RuntimeError(shapes)\n", " return best_cost, best_pos\n", "\n", " \n", "n_ops_N([m1.shape, m2.shape, m3.shape, m4.shape])"]}, {"cell_type": "code", "execution_count": 21, "metadata": {}, "outputs": [{"data": {"text/plain": ["(11331640, 1)"]}, "execution_count": 22, "metadata": {}, "output_type": "execute_result"}], "source": ["n_ops_4(m1.shape, m2.shape, m3.shape, m4.shape)"]}, {"cell_type": "code", "execution_count": 22, "metadata": {}, "outputs": [], "source": ["def product_N(inputs):\n", " if len(inputs) <= 1:\n", " raise RuntimeError(\n", " \"List inputs must contain at least two elements bot has %d.\" % len(inputs))\n", " cost, pos = n_ops_N([i.shape for i in inputs])\n", " if len(inputs) == 2:\n", " return inputs[0] @ inputs[1]\n", " if pos == 1:\n", " right = product_N(inputs[1:])\n", " return inputs[0] @ right\n", " if pos == len(shapes) - 1:\n", " left = product_N(inputs[:-1])\n", " return left @ inputs[-1]\n", " else:\n", " left = product_N(inputs[:pos + 1])\n", " right = product_N(inputs[pos + 1:])\n", " return left @ right\n", "\n", "\n", "assert_almost_equal(m1 @ m2 @ m3 @ m4, product_N([m1, m2, m3, m4]))"]}, {"cell_type": "code", "execution_count": 23, "metadata": {}, "outputs": [{"data": {"text/plain": ["0.0009734980000000349"]}, "execution_count": 24, "metadata": {}, "output_type": "execute_result"}], "source": ["mesure_temps_fonction(lambda: produit4(m1, m2, m3, m4))"]}, {"cell_type": "code", "execution_count": 24, "metadata": {}, "outputs": [{"data": {"text/plain": ["0.0009873739999999031"]}, "execution_count": 25, "metadata": {}, "output_type": "execute_result"}], "source": ["mesure_temps_fonction(lambda: product_N([m1, m2, m3, m4]))"]}, {"cell_type": "markdown", "metadata": {}, "source": ["**Ici s'arr\u00eate ce qui est attendu comme r\u00e9ponse \u00e0 la question 10.**\n", "\n", "**Les calculs en double...**\n", "\n", "On v\u00e9rifie en ajoutant une ligne pour afficher tous les appels \u00e0 `n_ops_N`."]}, {"cell_type": "code", "execution_count": 25, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["n_ops_N([(997, 93), (93, 1003), (1003, 97), (97, 20), (20, 17)])\n", "n_ops_N([(93, 1003), (1003, 97), (97, 20), (20, 17)])\n", "n_ops_N([(1003, 97), (97, 20), (20, 17)])\n", "n_ops_N([(93, 1003), (1003, 97)])\n", "n_ops_N([(97, 20), (20, 17)])\n", "n_ops_N([(93, 1003), (1003, 97), (97, 20)])\n", "n_ops_N([(997, 93), (93, 1003)])\n", "n_ops_N([(1003, 97), (97, 20), (20, 17)])\n", "n_ops_N([(997, 93), (93, 1003), (1003, 97)])\n", "n_ops_N([(97, 20), (20, 17)])\n", "n_ops_N([(997, 93), (93, 1003), (1003, 97), (97, 20)])\n", "n_ops_N([(93, 1003), (1003, 97), (97, 20)])\n", "n_ops_N([(997, 93), (93, 1003)])\n", "n_ops_N([(1003, 97), (97, 20)])\n", "n_ops_N([(997, 93), (93, 1003), (1003, 97)])\n"]}, {"data": {"text/plain": ["(9697854, 1)"]}, "execution_count": 26, "metadata": {}, "output_type": "execute_result"}], "source": ["def n_ops_N(shapes, verbose=False):\n", " if verbose:\n", " print(\"n_ops_N(%r)\" % shapes)\n", " if len(shapes) <= 1:\n", " raise RuntimeError(\"Unexpected list of shapes: %r.\" % shapes)\n", " if len(shapes) == 2:\n", " return n_ops(*shapes), 1\n", " if len(shapes) == 3:\n", " return n_ops_3(*shapes)\n", " best_cost = None\n", " best_pos = None\n", " for i in range(1, len(shapes)):\n", " if i == 1:\n", " cost = (n_ops(shapes[0], (shapes[1][0], shapes[-1][1])) + \n", " n_ops_N(shapes[1:], verbose=verbose)[0])\n", " best_cost = cost\n", " best_pos = i\n", " elif i == len(shapes)-1:\n", " cost = (n_ops_N(shapes[:-1], verbose=verbose)[0] + \n", " n_ops((shapes[0][0], shapes[-2][1]), shapes[-1]))\n", " if cost < best_cost:\n", " best_cost = cost\n", " best_pos = i\n", " else:\n", " cost = (n_ops_N(shapes[:i], verbose=verbose)[0] + \n", " n_ops_N(shapes[i:], verbose=verbose)[0] + \n", " n_ops((shapes[0][0], shapes[i-1][1]), (shapes[i][0], shapes[-1][1])))\n", " if cost < best_cost:\n", " best_cost = cost\n", " best_pos = i\n", "\n", " if best_pos is None:\n", " raise RuntimeError(shapes)\n", " return best_cost, best_pos\n", "\n", "\n", "m5 = numpy.random.randn(20, 17)\n", "\n", "n_ops_N([m1.shape, m2.shape, m3.shape, m4.shape, m5.shape], verbose=True)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["On voit deux appels identiques `n_ops_N([(97, 20), (20, 17)])` et `n_ops_N([(93, 1003), (1003, 97), (97, 20)])`. Ce n'est pas trop probl\u00e9matique pour un petit nombre de matrices mais cela pourrait le devenir si ce m\u00eame algorithme \u00e9tait appliqu\u00e9e \u00e0 autre chose.\n", "\n", "Plut\u00f4t que de r\u00e9\u00e9crire l'algorithme diff\u00e9remment, on se propose d'ajouter un param\u00e8tre pour garder la trace des r\u00e9sultats d\u00e9j\u00e0 retourn\u00e9s."]}, {"cell_type": "code", "execution_count": 26, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["n_ops_N([(997, 93), (93, 1003), (1003, 97), (97, 20), (20, 17)])\n", "n_ops_N([(93, 1003), (1003, 97), (97, 20), (20, 17)])\n", "n_ops_N([(1003, 97), (97, 20), (20, 17)])\n", "n_ops_N([(93, 1003), (1003, 97)])\n", "n_ops_N([(97, 20), (20, 17)])\n", "n_ops_N([(93, 1003), (1003, 97), (97, 20)])\n", "n_ops_N([(997, 93), (93, 1003)])\n", "n_ops_N([(997, 93), (93, 1003), (1003, 97)])\n", "n_ops_N([(997, 93), (93, 1003), (1003, 97), (97, 20)])\n", "n_ops_N([(1003, 97), (97, 20)])\n"]}, {"data": {"text/plain": ["(9697854, 1)"]}, "execution_count": 27, "metadata": {}, "output_type": "execute_result"}], "source": ["def n_ops_N_opt(shapes, cache=None, verbose=False):\n", " if cache is None:\n", " cache = {}\n", " key = tuple(shapes)\n", " if key in cache:\n", " # On s'arr\u00eate, d\u00e9j\u00e0 calcul\u00e9.\n", " return cache[key]\n", "\n", " if verbose:\n", " print(\"n_ops_N(%r)\" % shapes)\n", " if len(shapes) <= 1:\n", " raise RuntimeError(\"Unexpected list of shapes: %r.\" % shapes)\n", " \n", " if len(shapes) == 2:\n", " res = n_ops(*shapes), 1\n", " cache[key] = res\n", " return res\n", " \n", " if len(shapes) == 3:\n", " res = n_ops_3(*shapes)\n", " cache[key] = res\n", " return res\n", " \n", " best_cost = None\n", " best_pos = None\n", " for i in range(1, len(shapes)):\n", " if i == 1:\n", " cost = (n_ops(shapes[0], (shapes[1][0], shapes[-1][1])) + \n", " n_ops_N_opt(shapes[1:], verbose=verbose, cache=cache)[0])\n", " best_cost = cost\n", " best_pos = i\n", " elif i == len(shapes)-1:\n", " cost = (n_ops_N_opt(shapes[:-1], verbose=verbose, cache=cache)[0] + \n", " n_ops((shapes[0][0], shapes[-2][1]), shapes[-1]))\n", " if cost < best_cost:\n", " best_cost = cost\n", " best_pos = i\n", " else:\n", " cost = (n_ops_N_opt(shapes[:i], verbose=verbose, cache=cache)[0] + \n", " n_ops_N_opt(shapes[i:], verbose=verbose, cache=cache)[0] + \n", " n_ops((shapes[0][0], shapes[i-1][1]), (shapes[i][0], shapes[-1][1])))\n", " if cost < best_cost:\n", " best_cost = cost\n", " best_pos = i\n", "\n", " if best_pos is None:\n", " raise RuntimeError(shapes)\n", " \n", " res = best_cost, best_pos\n", " cache[key] = res\n", " return res\n", "\n", "\n", "n_ops_N_opt([m1.shape, m2.shape, m3.shape, m4.shape, m5.shape], verbose=True)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["La liste est moins longue et tous les appels sont uniques. On met \u00e0 jour la fonction `product_N`."]}, {"cell_type": "code", "execution_count": 27, "metadata": {}, "outputs": [], "source": ["def product_N_opt(inputs, cache=None):\n", " if len(inputs) <= 1:\n", " raise RuntimeError(\n", " \"List inputs must contain at least two elements bot has %d.\" % len(inputs))\n", " cost, pos = n_ops_N_opt([i.shape for i in inputs], cache=cache)\n", " if len(inputs) == 2:\n", " return inputs[0] @ inputs[1]\n", " if pos == 1:\n", " right = product_N_opt(inputs[1:], cache=cache)\n", " return inputs[0] @ right\n", " if pos == len(shapes) - 1:\n", " left = product_N_opt(inputs[:-1], cache=cache)\n", " return left @ inputs[-1]\n", " else:\n", " left = product_N_opt(inputs[:pos + 1], cache=cache)\n", " right = product_N_opt(inputs[pos + 1:], cache=cache)\n", " return left @ right\n", "\n", "\n", "assert_almost_equal(m1 @ m2 @ m3 @ m4, product_N([m1, m2, m3, m4]))"]}, {"cell_type": "code", "execution_count": 28, "metadata": {}, "outputs": [{"data": {"text/plain": ["0.0010903469999999516"]}, "execution_count": 29, "metadata": {}, "output_type": "execute_result"}], "source": ["mesure_temps_fonction(lambda: product_N([m1, m2, m3, m4, m5]))"]}, {"cell_type": "code", "execution_count": 29, "metadata": {}, "outputs": [{"data": {"text/plain": ["0.0009383259999999893"]}, "execution_count": 30, "metadata": {}, "output_type": "execute_result"}], "source": ["mesure_temps_fonction(lambda: product_N_opt([m1, m2, m3, m4, m5]))"]}, {"cell_type": "code", "execution_count": 30, "metadata": {}, "outputs": [{"data": {"text/plain": ["0.01018160299999991"]}, "execution_count": 31, "metadata": {}, "output_type": "execute_result"}], "source": ["mesure_temps_fonction(lambda: m1 @ m2 @ m3 @ m4 @ m5)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Tout fonctionne."]}, {"cell_type": "markdown", "metadata": {}, "source": ["## Remarques lors de la correction \n", "\n", "Il y a eu peu d'erreurs lors des premi\u00e8res questions. Par la suite des erreurs fr\u00e9quentes sont apparues.\n", "\n", "Il ne fallait pas utiliser de produits matriciel dans les fonctions de co\u00fbts. L'int\u00e9r\u00eat est d'utiliser ces fonctions pour d\u00e9cider du calcul \u00e0 faire, pour d\u00e9terminer le calcul optimal. Et le calcu de ce co\u00fbt doit \u00eatre n\u00e9gligeable par rapport au co\u00fbt matriciel lui-m\u00eame sinon l'int\u00e9r\u00eat en est fortement r\u00e9duit.\n", "\n", "Le produit de 4 matrices ne pouvait pas faire intervenir `m1 @ m2 @ m3` car cette notation ne pr\u00e9cise pas explicitement l'ordre \u00e0 suivre.\n", "\n", "Enfin, les mesures de temps \u00e9taient destin\u00e9es \u00e0 rep\u00e9rer les erreurs de code \u00e9ventuelles. Si la mesure donne l'inverse ce qui est attendu, c'est qu'il y a sans doute une erreur de code. De m\u00eame, si la mesure de temps dure tr\u00e8s longtemps, c'est aussi une indication que le code est probablement erron\u00e9."]}, {"cell_type": "code", "execution_count": 31, "metadata": {}, "outputs": [], "source": []}], "metadata": {"kernelspec": {"display_name": "Python 3", "language": "python", "name": "python3"}, "language_info": {"codemirror_mode": {"name": "ipython", "version": 3}, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.9.5"}}, "nbformat": 4, "nbformat_minor": 2}