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... $}
Remarque pour les étudiants avancés : ne pas utiliser la mémoïsation.
Une fonction récursive est une fonction qui s’appelle elle-même pour résoudre un problème. Elle se compose de deux parties principales :
1. Cas de base. C’est la condition qui arrête la récursion. Sans cas de base, la fonction s’appellerait indéfiniment. Le cas de base traite généralement l’instance la plus simple du problème et renvoie une réponse directe. Par exemple, pour Fibonacci, F(0) = 0 et F(1) = 1 sont des cas de base.
2. Cas de propagation, où la fonction s’appelle elle-même sur une version plus petite ou plus simple du problème, réduisant progressivement le problème jusqu’à atteindre le cas de base.
La mémoïsation est une technique qui consiste à stocker les résultats déjà calculés, ce qui évite les calculs redondants et rend la récursion beaucoup plus efficace.
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])
Lorsque qu’une fonction s’appelle elle-même (récursion), l’ordinateur doit se souvenir du point de retour après chaque appel. Cela est géré grâce à la pile d’exécution (call stack en anglais), qui est une zone de la mémoire de l’ordinateur. En fait, la pile d’appels est utilisée pour tout appel de fonction, y compris les fonctions non récursives.
Voici comment la récursion est implémentée en interne :
1. Chaque appel récursif crée une petite « boîte » en mémoire appelée stack frame. Le stack frame stocke les paramètres de la fonction, ses variables locales, ainsi que l’endroit où revenir (l’adresse de retour) après l’appel.
2. Chaque fois que la fonction s’appelle elle-même, un nouveau stack frame est ajouté au sommet de la pile. La pile fonctionne en dernier entré, premier sorti (last-in first-out, ou LIFO, en anglais): l’appel le plus récent est terminé en premier.
3. Lorsque le cas de base est atteint, la fonction commence à renvoyer des valeurs, en retirant chaque stack frame dans l’ordre inverse.
Comme chaque processus se voit attribuer une portion limitée de mémoire par le système d’exploitation, si trop d’appels récursifs sont effectués, la pile peut déborder (stack overflow).
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.
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
Ajoutez une section principale (main) à votre script Python comme suit :
if __name__ == "__main__":
# measure execution times
# plot performance curves
Ajoutez les instructions pour mesurer le temps d'exécution de fibonacci_rec() et fibonacci_iter(), et
tracer les courbes de performance.
if __name__ == "__main__" est une construction spéciale de Python qui vérifie si un script est exécuté directement ou importé comme module.
Si le script est exécuté directement, le code à l’intérieur de ce bloc est exécuté.
Si le script est importé dans un autre module, le code à l’intérieur du bloc n’est pas exécuté.
Cela permet d’écrire du code qui peut être testé ou exécuté lorsqu’il est lancé comme programme, sans s’exécuter automatiquement lorsqu’il est importé.
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 utiliserons Numpy pour manipuler les matrices.
Numpy est une bibliothèque Python open source qui fournit des fonctions pour manipuler des structures de données multidimensionnelles.
La principale structure de données est le np.array, qui représente un vecteur multidimensionnel.
Les vecteurs multidimensionnels peuvent également être représentés en utilisant des listes Python standard.
Cependant, deux différences importantes existent entre les listes Python et les tableaux NumPy :
1. La taille d’un tableau NumPy est fixée lors de sa création et ne peut pas changer. En revanche, les listes Python peuvent croître dynamiquement. Modifier la taille d’un tableau NumPy créera un nouveau tableau et supprimera l’original.
2. Tous les éléments d’un tableau NumPy doivent avoir le même type de données.
En conséquence, les éléments d’un tableau NumPy sont tous stockés dans des emplacements contigus en mémoire, ce qui n’est pas le cas des listes Python. C’est pourquoi itérer sur des tableaux NumPy est beaucoup plus efficace que d’itérer sur des listes Python.
Les tableaux NumPy facilitent les opérations mathématiques avancées et d’autres types d’opérations sur de grandes quantités de données. En général, ces opérations sont exécutées plus efficacement et avec moins de code que ce qui est possible en utilisant les séquences intégrées de Python.
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.