Mesurer le temps d’exécution d’un fragment de code

Un moyen intuitif de comparer l’efficacité de deux portions de code est de mesurer leur temps d’exécution en fonction de la taille des données. Le module timeit de Python permet de faire cela de façon semi-automatisée. Nous allons voir comment dans cet article, en considérant trois fonctions différentes qui renvoient le n-ième \(F_n\) de la suite de Fibonacci.

Pour les besoins du code présent dans la suite, on commencera par les importations suivantes :

import matplotlib.pyplot as plt
import timeit

Fonctions à tester

Ces fonctions sont issues d’un exercice du chapitre “Récursivité” du cours de NSI de terminale. Cependant, l’objectif de cet article est juste de montrer un moyen de comparer et de visualiser les vitesses d’exécution.

Nous considérons les trois fonctions suivantes. La première retourne le nombre \(F_n\) par une méthode itérative.

def fibo_iter(n: int) -> int:
    """Suite de Fibonacci, version itérative"""
    if n == 0:
        return 0
    else:
        f0, f1 = 0, 1
        for k in range(1, n):
            f0, f1 = f1, f0 + f1
        return f1

La deuxième fonction est une fonction récursive qui traduit directement la définition de la suite de Fibonacci.

def fibo_rec(n: int) -> int:
    """Suite de Fibonacci version récursive"""
    # Cas de base
    if n == 0 or n == 1:
        return n
    # Récursion
    else:
        return fibo_rec(n-2)+fibo_rec(n-1)

La troisième est également récursive et utilise les idées de la programmation dynamique.

def fibo_dyn(n: int, suite: dict = {0: 0, 1: 1}) -> int:
    """Suite de Fibonacci version dynamique"""
    # Cas de base
    if n == 0 or n == 1:
        return n
    # Récursion
    else:
        # Si Fn est déjà calculé, on le retourne
        if n in suite.keys():
            return suite[n]
        else:
            # Sinon, on le calcule et on le garde en mémoire
            f = fibo_dyn(n-2, suite) + fibo_dyn(n-1, suite)
            suite[n] = f
            return f

Utilisation de timeit

Par exemple, pour obtenir le temps d’exécution de 100 appels à la fonction fibo_iter() avec le paramètre 15, on entre le script suivant :

timeit.timeit('fibo_iter(15)', number=1000, globals=globals())

0.0008780480002315016

et on obtient en sortie le temps d’exécution en secondes.

Beaucoup d’autres choses sont possibles avec le module timeit, mais cette simple commande nous suffira.

Visualisation graphique

Dans le script suivant, nous définissions un tableau des abscisses correspondant aux différentes valeurs de \(n\) pour lesquelles nous calculons \(F_n\) : \(n\) varie de 0 à 15 avec un pas de 1 (ligne 1)

Ensuite, pour chacune des fonctions, nous calculons le temps d’exécution de chaque terme de la suite (100 fois) et nous stockons les résultats dans un tableau d’ordonnées. (lignes 5 à 11)

Nous traçons ensuite les courbes correspondantes. (lignes 12 à 15)

abscisses = [k for k in range(0, 20, 1)]
ordonnees_rec = []
ordonnees_iter = []
ordonnees_dyn = []
for x in abscisses:
    ordonnees_iter.append(timeit.timeit(
        'fibo_iter(x)', number=100, globals=globals()))
    ordonnees_rec.append(timeit.timeit(
        'fibo_rec(x)', number=100, globals=globals()))
    ordonnees_dyn.append(timeit.timeit(
        'fibo_dyn(x)', number=100, globals=globals()))
plt.plot(abscisses, ordonnees_iter, 'b')
plt.plot(abscisses, ordonnees_rec, 'r')
plt.plot(abscisses, ordonnees_dyn, 'g')
plt.show()

Nous observons pour la fonction récursive une courbe caractéristique d’une croissance exponentielle du temps d’exécution. Les courbes bleue et verte correspondant aux deux autres méthodes sont confondues. Pour les distinguer, nous allons faire une nouvelle figure sans les données de la fonction fibo_rec cette fois ci (image réalisée avec \(n\) variant de 0 à 100) :

abscisses = [k for k in range(0, 100, 1)]
ordonnees_iter = []
ordonnees_dyn = []
for x in abscisses:
    ordonnees_iter.append(timeit.timeit(
        'fibo_iter(x)', number=100, globals=globals()))
    ordonnees_dyn.append(timeit.timeit(
        'fibo_dyn(x)', number=100, globals=globals()))
plt.plot(abscisses, ordonnees_iter, 'b')
plt.plot(abscisses, ordonnees_dyn, 'g')
plt.show()

Ce graphique suggère une croissance linéaire pour la méthode itérative et des performances encore meilleures pour la méthode dynamique.

Bien sûr, cette démarche ne remplace pas une étude théorique rigoureuse et un calcul de complexité, mais elle permet, grâce à la visualisation, de comparer rapidement deux algorithmes et de conjecturer leur complexité.