TD I2 : Tests de performance (correction)

On a parlé dans le TD précédent de tests de correction, c'est à dire que l'on s'est posé la question de savoir si nos fonctions faisaient bien ce pourquoi elles avaient été écrites. Voyons un peu si elle le font rapidement (!) en faisant un petit détour par les tests de performance...

Après avoir testé la correction d'une fonction on peut aussi tester la rapidité de l'exécution de cette fonction. Pour cela le module time propose par exemple la fonction time qui va nous permettre de chronométrer le temps d'exécution d'un fonction.

import time
help(time.time)

Help on built-in function time in module time:

time(...)
    time() -> floating point number

    Return the current time in seconds since the Epoch.
    Fractions of a second may be present if the system clock provides them.

Le principe est de relever l'heure avant l'exécution de la fonction, puis après et de faire la différence. À noter que le temps d'exécution de nos fonctions est souvent très court (trop court pour être mesuré), on préfèrera mesurer le temps d'exécution d'un grand nombre de répétitions de notre fonction.

import time
t0 = time.time()
for _ in range(1000) :
    ma_fonction_a_tester()
t1 = time.time()
print(t1-t0)

1. Un exemple

Par exemple, si l'on souhaite chronométer la vitesse d'exécution du calcul de math.log(10), on peut faire (on notera que l'exécution est tellement rapide que l'on ne chronomètre pas une exécution mais ici 10000):

import time
import math
N = 10000 # nombre de répétitions

def perf_log(n):
    t0 = time.time()
    for i in range(N):
        math.log(n)
    t1 = time.time()
    return t1-t0

print(perf_log(99))

0.0005738735198974609

Q1. Essayer de voir si le calcul de math.log(n) ralentit si n devient bien plus grand que 10...

Réponse : NON, toujours à peu près pareil !

Exercice 1

Q2. On donne ci-dessous une fonction qui calcule la racine carrée d'un nombre positif à $10^{-10}$ près. On souhaite savoir si cette fonction est plus ou moins rapide que la fonction native math.sqrt() pour calculer la racine carrée de a=10. Pour cela vous devez écrire une fonction compare_racines(n : float) -> float qui reçoit un flottant $a$, qui mesure le temps $t_1$ mis pour effectuer 10000 caluls de racine(n) , le temps $t_2$ mis pour effectuer 10000 caluls de math.sqrt(n), et qui renvoie le quotient des temps $\frac{t_1}{t_2}$.

import math

def racine(a :  float) -> float :
    """ renvoie la racine carrée de 'a' à 10^(-10) près"""
    assert a >= 0
    u, v = 1, a
    i = 0
    while abs(v-u)>10**(-10) :
        i += 1
        u_temp = 2/(1/u+1/v)
        v = (u+v)/2
        u = u_temp
    # print(i) # nombre d'itérations
    return (u+v)/2
    

def compare_racines(a : float) -> float :
    # à compléter : docstring et code
    N= 10000
    c0=time.time()
    for _ in range(N):
        racine(a)
    c1=time.time()
    t1=c1-c0
    for _ in range(N):
        math.sqrt(a)
    c2=time.time()
    t2=c2-c1
    return t1/t2

compare_racines(10)

22.994212962962962

Q3. On souhaite comparer visuellement les temps de 10000 calculs de racine(n) et de math.sqrt(n) pour des valeurs de $n$ de plus en plus grandes (des nombres contenant jusqu'à 10 chiffres). On répondra aux questions suivantes dans la cellule de code ci-dessous.

• Q3a. Créer la liste nombre_chiffres contenant les nombres 1 à 10. (ce sont les nombres de chiffres de chacun des $n$ que l'on va calculer). Attention de ne pas dépasser 10 ! (plantage ...)

• Q3b. Créer la liste nombres contenant les nombres $10^{i}$ pour i dans la liste nombres_chiffres.

• Q3c. Créer la liste quotients contenant les rapports des temps calculés en Q2 (temps de 10000 calculs de racnie(n) par temps de 10000 calculs de math.sqrt(n)) pour les nombres n de la liste nombres.

• Q3d. Créer la courbe des valeurs de quotients en fonction de nombre_chiffres. Que constatez-vous sur les ratios?

import matplotlib.pyplot as plt

nombre_chiffres = list(range(1,11))
nombres = [10**i for i in nombre_chiffres]
quotients = [compare_racines(n) for n in nombres]

plt.figure(1)
plt.clf()

plt.plot(nombre_chiffres, quotients,'o')

plt.xlabel("nombre de chiffres")
plt.ylabel("quotient du temps de calcul")
plt.show()

Exercice 2

Q4. On souhaite faire un travail similaire à l'exercice 1 pour comparer puissance(5,n) avec mystere(5,n) pour des valeurs de $n$ comprises entre 1 et 1000 :

• Q4a. Créer les focntions perf_puiss(n) et perf_myst(n) qui chronomètrent 10000 calculs de puissance(5,n) et de mystere(5,n).

• Q4b. Créer la liste nb_bits contenant les nombres 1 à 10. (ce sont les tailles en nombre de bits des valeurs de $n$ que l'on va calculer)

• Q4c. Créer la liste exposants contenant les nombres $2^{i}$ pour i dans la liste nb_bits.

• Q4d. Créer la liste quotients contenant les rapports perf_puiss(n)/perf_myst(n) pour les nombres n de la liste exposants.

• Q4e. Créer la courbe des valeurs de quotients en fonction de nb_bits. Que pouvez-vous dire quant-aux vitesses de ces deux fonctions?

import matplotlib.pyplot as plt
import time

def puissance(nombre,exposant):
    resultat = 1
    for e in range(exposant):
        resultat *= nombre
        
    return nombre

def mystere(x,n):
    if n == 0 : 
        return 1
    if n%2 == 0 :
        m = mystere(x,n//2)
        return m*m
    else :
        m = mystere(x,n-1)
        return x*m

def perf_puiss(n):
    t0 = time.time()
    for _ in range(10000):
        puissance(5,n)
    t1= time.time()
    return t1-t0

def perf_mystere(n):
    t0 = time.time()
    for _ in range(10000):
        mystere(5,n)
    t1= time.time()
    return t1-t0

nb_bits= list(range(1,11))
exposants = [2**i for i in nb_bits]
quotients = [perf_puiss(e)/perf_mystere(e) for e in exposants]

plt.figure(2)
plt.clf()

plt.plot(nb_bits,quotients)

plt.show()

On constate que plus l'exposant est grand, plus la fonction puissance est lente par rapport à la fonction mystere.