1CC1000 - Systèmes d'Information et Programmation - TD : Introduction à Matplotlib et Numpy

Table des matières

L'objectif de ce TD est d'introduire la visualisation avec Matplotlib et le calcul scientifique avec Numpy. Nous implémenterons une fonction simple avec différentes méthodes de programmation, mesurerons les performances de chacune et visualiserons les résultats.

Méthodes de programmation classiques

Récursion

Développez une fonction fibonacci_rec(n) qui calcule la valeur du n-ième terme de la suite de Fibonacci. Cette fonction doit être récursive. Les résultats attendus pour les premières valeurs sont : {$ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181... $}

Analyse du temps d'exécution

La fonction timeit, définie dans le package homonyme, est utilisée pour mesurer le temps d'exécution d'un code Python. Dans l'exemple suivant, timeit renvoie le temps total de 100 exécutions du code Python pour lisser les résultats.

Les temps d'exécution peuvent varier d'une machine à l'autre ; vous devez vous attendre à un temps d'exécution de quelques millièmes de seconde. Essayez-le.

from timeit import timeit
timeit(lambda : fibonacci_rec(10), number=100)

Nous avons défini une fonction measure() qui détermine le temps d'exécution d'une fonction pour une séquence de valeurs.
Lorsque nous mesurons les performances de fibonacci() avec différentes valeurs de {$n$}, nous devrions observer un temps d'exécution élevé pour des valeurs au-delà de {$n = 20$}.

def measure(func, values, number=100):
    m = []
    for i in values :
        m.append(timeit(lambda : func(i), number=number))
    return m

measure(fibonacci_rec, [1, 2, 3, 5, 10, 20, 25])

Itération

Développez une fonction fibonacci_iter(n) qui calcule la valeur du n-ième terme de la suite de Fibonacci. Cette fonction doit être itérative.
Remarque pour les étudiants avancés : ne pas utiliser la mémoïsation.

Mesurez le temps d'exécution de fibonacci_iter(n). Il devrait être significativement plus rapide que la version récursive.

Visualisation

Nous allons maintenant tracer ces valeurs. Nous utilisons le module pyplot de la bibliothèque matplotlib. Les instructions suivantes tracent une série de points définis par deux listes de coordonnées x et y.

import matplotlib.pyplot as plt
plt.plot(xvalues, yvalues, label="name for legend")
plt.legend()
plt.show()

Le graphique doit toujours contenir un titre et une légende, avoir des axes étiquettés, l'échelle de l'axe des y doit être logarithmique, l'échelle de l'axe des x doit commencer à 0. Voici quelques fonctions utiles.

plt.yscale("log")
plt.xlabel("Name")
plt.ylabel("Name")
plt.title("Name")

N'oubliez pas les daltoniens (environ 1 personne sur 20) et choisissez des styles de ligne qui peuvent être différenciés sans utiliser de couleurs. Les styles de ligne peuvent être définis à l'aide des codes suivants : ":", "-", "-." et "--".

plt.plot(xvalues, yvalues, "--", label="Dashed line")

Tout mettre en place

Définissez une fonction main() qui mesure le temps d'exécution de fibonacci_rec() et fibonacci_iter(), et trace les courbes de performance.

Méthode alternative

Une méthode alternative pour calculer la suite de Fibonacci consiste à utiliser des matrices. La suite de Fibonacci peut être représentée sous forme matricielle de la manière suivante :

{$$ \left( \begin{matrix} F_1 \\ F_2 \end{matrix} \right) = \left( \begin{matrix} 0 & 1 \\ 1 & 1 \end{matrix} \right) * \left( \begin{matrix} F_0 \\ F_1 \end{matrix} \right) $$}

et en général :

{$$ \left( \begin{matrix} F_n \\ F_{n+1} \end{matrix} \right) = \left( \begin{matrix} 0 & 1 \\ 1 & 1 \end{matrix} \right)^n * \left( \begin{matrix} F_0 \\ F_1 \end{matrix} \right) $$}

Nous allons utiliser numpy pour calculer des opérations sur des matrices. Voici quelques étapes simples pour vous aider.

Création de matrices et de vecteurs.

import numpy as np
mat1 = np.array([[5,6],[10,3]])
vec = np.array([[9],[2]])

Accès à un élément.

mat1[1,0]     # => 10

Quelques opérations terme à terme.

mat2 = mat1 + mat1  # => mat2[i,j] = mat1[i, j] + mat1[i,j]
mat3 = mat1 * 2     # => mat3[i,j] = mat1[i,j] * 2
 ...

Quelques opérations matricielles.

mat4 = np.matmul(mat1, mat1)      # matrix product
mat5 = mat1 @ mat1            # abbreviated product syntax
mat6 = np.linalg.matrix_power(mat1, 2)   # mat1**2

Prenez un moment pour vous familiariser avec les opérations matricielles numpy dans un shell Python.

ATTENTION : vous avez peut-être déjà utilisé np.matrix au lieu de np.array. Leur fonctionnement est légèrement différent. En particulier, des opérations comme M ** 2 ou M * vec sont disponibles pour np.matrix et cela semble assez pratique. CEPENDANT, la documentation de numpy est claire, l'objet np.matrix sera bientôt retiré de la bibliothèque, vous devez donc cesser de les utiliser : "Il n'est plus recommandé d'utiliser cette classe, même pour l'algèbre linéaire. Utilisez plutôt des tableaux normaux. La classe pourrait être supprimée dans le futur".

Matrice

Développez une fonction fibonacci_mat(n) permettant de calculer la valeur du n-ième terme de la suite de Fibonacci. Cette fonction doit utiliser des fonctions numpy.

Incluez cette fonction dans votre analyse de performances.

Grandes valeurs de {$n$}

Votre fonction récursive est probablement beaucoup plus lente que les deux autres variantes. Le temps d'exécution semble augmenter de façon exponentielle avec la valeur de {$n$}. Et c'est le cas. Testez vos fonctions avec des valeurs plus importantes de {$n$}. Commencez par range(1, 20, 2), puis range(1, 30, 3) et ainsi de suite jusqu'à ce que le temps d'exécution de fibonacci_rec devienne trop long.

Testez les trois fonctions.

Le diable se cache dans les détails

Comparez les résultats de fibonacci_iter(93) et fibonacci_mat(93). D'où vient le problème ?

Bravo

Vous avez terminé la première partie de ce TD. Vous avez étudié les bases de la visualisation avec matplotlib et, pour la première fois, vous avez touché du doigt la simplicité des calculs matriciels avec numpy. S'il vous reste du temps, vous voudrez peut-être répondre aux questions suivantes.

Questions facultatives

Le problème de la fonction récursive vient du nombre exponentiellement grand d'appels récursifs. La fonction peut être appelée plusieurs fois avec la même valeur en argument. Il est possible de contourner ce problème grâce à la mémoïsation. Le principe de la mémoïsation est de stocker les résultats intermédiaires dans un dictionnaire et de ne faire un appel récursif que si le résultat de l'appel n'est pas encore dans le dictionnaire.

Mémoïsation

Modifiez l'implémentation de votre fonction récursive pour utiliser la mémoïsation et comparez ses performances avec celles des deux autres fonctions.

Vous pouvez en savoir plus sur la mémoïsation ici.

Très grandes valeurs de {$n$}

Jusqu'à quelle valeur de {$n$} pouvez-vous calculer des résultats ? Cela dépend de votre machine. Augmentez la plage de valeurs de mesure, par exemple de {$0$} à {$20,000$} avec un pas de {$1,000$}. Une des fonctions devrait générer un message d'erreur pour des valeurs trop grandes de {$n$}.

A votre avis

Pourquoi fibonacci_mat(n) a un temps d'exécution qui augmente pour de petites valeurs de {$n$} et semble ensuite constant ?
Que signifie le message d'erreur fibonacci_rec(n) pour de grandes valeurs de {$n$} ?

Essayez le calcul matriciel à votre façon

Puisque le calcul matriciel avec Numpy génère des débordements, vous pouvez créer votre propre méthode en utilisant des listes d'entiers natifs de Python. Pour cela, vous avez besoin d'une fonction de produit matriciel (basée sur des listes de listes) et d'une fonction d'exponentiation rapide.