Skip to content

Texte

Approche pragmatique : mesurons le temps d'exécution

Une première approche pragmatique, pour avoir des informations sur le temps d'exécution, est tout simplement de le mesurer sur différents jeux de données.

Le module timeit permet de réaliser plusieurs exécutions d'un code donné et de retenir le meilleur temps CPU parmi l'ensemble des exécutions.

Les exécutions peuvent se faire au "terminal" ou dans un script ou une console Python

Par exemple dans un terminal l'instruction

python3 -m timeit -n 5 "print('coucou')"

mesure le temps d'exécution pris pour exécuter 5 fois le code donné en paramèrre.

$ python3 -m timeit -n 5 "print('coucou')"
coucou
...
coucou
coucou
5 loops, best of 5: 1.69 usec per loop
:0: UserWarning: The test results are likely unreliable. The worst time (9.01 usec) was more than four times slower than the best time (1.69 usec).
ThierryM:~ tmassart$ 

ou (ici à la console en utilisant le module timeit, un objet de classe Timer et la méthode timeit :

>>> import timeit
>>> t = timeit.Timer("print('coucou')")
>>> t.timeit(5)

coucou
coucou
coucou
coucou
coucou
4.3688996811397374e-05

Prenons un autre exemple : supposons qur nous désirions analyser les deux fonctions anagramme_dico(a, b) et anagramme_list(a, b) données ici, qui renvoient toutes deux True si les séquences a et b sont des permutations l'une de l'autre.

def anagramme_dico(a,b):
    res = False
    if len(a)==len(b):
        dic_a = {}
        dic_b = {}
        for i in a:
            dic_a[i] = dic_a.setdefault(i, 0) + 1
        for i in b:
            dic_b[i] = dic_b.setdefault(i, 0) + 1
        res = dic_a == dic_b
    return res


def anagramme_list(a,b):
    res = False
    if len(a) == len(b):
        liste_b = list(b)
        res = True
        for i in a:
            if i in liste_b:
                liste_b.remove(i)
            else:
                res = False
    return res

Prenons initalement la chaîne de 10 caractères dont on multiplie la longueur par deux à chaque itération, et donnons le temps d'exécution de chaque code.

import timeit

d1 = """
def anagramme_list(a,b):
    res = False
    if len(a) == len(b):
        liste_b = list(b)
        res = True
        for i in a:
            if i in liste_b:
                liste_b.remove(i)
            else:
                res = False
    return res
"""
d2 = """def anagramme_dico(a,b):
    res = False
    if len(a)==len(b):
        dic_a = {}
        dic_b = {}
        for i in a:
            dic_a[i] = dic_a.setdefault(i, 0) + 1
        for i in b:
            dic_b[i] = dic_b.setdefault(i, 0) + 1
        res = dic_a == dic_b
    return res
"""
taille = 1
for i in range(20):
    t1 = timeit.Timer(d1 + f"""anagramme_list('RAVITAILLE'*{taille},'RAVITAILLE'[::-1]*{taille})""")
    t2 = timeit.Timer(d2 + f"""anagramme_dico('RAVITAILLE'*{taille},'RAVITAILLE'[::-1]*{taille})""")
    print(f"{taille*10:8d} {t1.timeit(1):11f} {t2.timeit(1):11f}")
    taille *= 2

Celui-ci est presque immédiat pour les chaînes de taille inférieure à 100000 caractères. Au delà, la fonction anagramme_list prend un temps de plus en plus significatif.


Taille anagramme_list (en s) anagramme_dico (en s)
10 0.000008 0.000006
20 0.000009 0.000009
40 0.000012 0.000012
80 0.000022 0.000021
160 0.000037 0.000037
320 0.000063 0.000074
640 0.000121 0.000145
1280 0.000261 0.000266
2560 0.000590 0.000571
5120 0.001676 0.001070
10240 0.005371 0.002035
20480 0.016907 0.003809
40960 0.098608 0.007899
81920 0.303143 0.012504
163840 1.231720 0.027419
327680 4.438462 0.050453
655360 20.400489 0.108817
1310720 102.657282 0.211423
2621440 586.517143 0.412746
5242880 2995.177226 0.991613

Par exemple dans la dernière ligne du tableau ici, pour une chaîne d'un peu plus de cinq millions de caractères, il faut approximativement 3000 secondes pour la version liste, soit près d'une heure, et moins d'une seconde pour la version dictionnaire.

On peut estimer grossièrement que le temps d'exécution grandit

  • linéairement par rapport à la taille des séquences avec la fonction anagramme_dico, et
  • de façon quadratique par rapport à la taille des séquences avec la fonction anagramme_list

il est intuitivement normal que ces fonctions prennent un temps proportionnel à la taille de a (on suppose que les deux chaînes de caractères sont de même taille).

Par contre, cette démarche est chronophage et on atteint vite ses limites car il n'est pas possible de faire des tests pour tous les exemples intéressants possibles et sur l'ensemble des ordinateurs possibles.