Mesurer la complexité d'un code

Un moyen efficace de mesurer la complexité d'un code est de mesurer le temps qu'il met à être exécuté. Pour que la mesure soit conforme à la complexité il faut que :

  1. les instructions basiques durent un temps similaire,
  2. l'on ait un moyen efficace de mesurer le temps
  3. le système ne doit exécuter que l'algorithme et n'avoir aucun autre processus concurrent (en temps partagé) (voir prérequis système)
  4. les paramètres d'entrée doivent :

Code python

On présuppose que vous avez fait les prérequis du cours d'algorithmie, en particulier que vous savez coder en python et/ou que vous avez suivi le cours d'introduction à python. Selon notre convention, les exemples de code qui commencent par >>> ont été exécutés directement dans un interpréteur.

On utilisera deux modules très utiles :

On vous fera installer tout ça dans un projet juste après. Essayez ici de comprendre la logique de ce code.

Comment mesurer la complexité

Reprenons les 4 conditions que l'on vient d'expliciter.

Nous allons utiliser les mesures de l'algorithme recherche que l'on a déjà vues :

def recherche(T, x):
    for e in T:
        if e == x:
            return True
    return False

1. durée d'une instruction basique

Le code source d'un programme ne correspond pas aux instructions qui sont effectivement effectuées sur l'ordinateur. Selon le type de langage, le code source est :

Ces deux approches nécessitent une étape de conversion :

Enfin, la première approche permet de créer un code portable, seul l'interpréteur doit être prévu pour le système (windows, Linux ou mac) et le type de processeur utilisé (x86 ou arm essentiellement).

Instruction python

Pour voir le bytecode python, on peut utiliser le module dis :

import dis

def recherche(T, x):
    for e in T:
        if e == x:
            return True
    return False

print(dis.dis(recherche))

Qui va afficher le bytecode associé à la fonction recherche :

  3           RESUME                   0

  4           LOAD_FAST                0 (T)
              GET_ITER                 0
      L1:     FOR_ITER                13 (to L3)
              STORE_FAST               2 (e)

  5           LOAD_FAST_BORROW_LOAD_FAST_BORROW 33 (e, x)
              COMPARE_OP              88 (bool(==))
              POP_JUMP_IF_TRUE         3 (to L2)
              NOT_TAKEN
              JUMP_BACKWARD           11 (to L1)

  6   L2:     POP_TOP
              POP_TOP
              LOAD_COMMON_CONSTANT     9 (True)
              RETURN_VALUE

  4   L3:     END_FOR
              POP_ITER

  7           LOAD_COMMON_CONSTANT    10 (False)
              RETURN_VALUE

Les instructions élémentaires de python ne sont donc pas celles du pseudo-code. De plus, le byte-code correspond à des algorithmes, par exemple l'addition :

>>> import dis
>>> dis.dis("a+b")
  0           RESUME                   0

  1           LOAD_NAME                0 (a)
              LOAD_NAME                1 (b)
              BINARY_OP                0 (+)
              RETURN_VALUE

L'instruction de bytecode BINARY_OP utilisée est un algorithme qui va prendre un temps proportionnel au nombre de chiffres de ses paramètres. Pour le vérifier on peut utiliser le module timeit qui va mesurer le temps mis pour exécuter du code python number fois :

>>> import timeit

>>> timeit.timeit("a + b", setup="a, b = 1, 1", number=10**5)
0.0007226660382002592
>>> timeit.timeit("a + b", setup="a, b = 10**100000, 10**100000", number=10**5)
1.1451560839777812

On ne peut donc pas mesurer le temps mis pour chaque instruction du byte-code et sommer le tout car leurs durées dépendent de leurs paramètres. Ce qui n'est pas le cas des instructions du processeur.

Instructions processeur

Une instruction du processeur va durer un certain nombre de cycles processeur (1 cycle correspond à la vitesse du processeur) fixe pour chaque instruction. Le problème est que chaque type de processeur va avoir son propre jeu d'instructions. Les processeurs x86 (en gros les PC) sont ainsi des processeurs CISC qui possèdent des instructions complexes et les processeurs ARM (portables, tablettes et mac) sont a contrario des processeurs RISC avec peu d'instructions.

Enfin, si les instructions ARM sont faites pour toutes durer 1 cycle, les instructions x86 vont varier grandement, de 1 cycle pour un test booléen, quelques dizaines de cycles pour une division de deux nombres codés sur 64 bits à plusieurs millions de cycles pour l'instruction WBINVD.

En pratique

En pratique ceci importe peu puisque :

  1. on veut de toute façon avoir le code le plus rapide possible,
  2. ces variations ne vont influer que sur les constantes additives et multiplicatives du code, pas sur l'allure générale de la courbe

Enfin, d'un point de vue algorithmique, l'ordre de grandeur en $\mathcal{O}$ sera conservé quel que soit l'ordinateur sur lequel le code sera exécuté.

À retenir

Même si les instructions processeurs sont très différentes du pseudo-code et que leur durée d'exécution n'est pas homogène, mesurer le temps permet d'avoir l'allure générale de la courbe de complexité.

Trouver un bon algorithme peut faire gagner un ordre de grandeur, optimiser le code ne va faire gagner qu'un facteur au mieux multiplicatif. On ne cherchera à optimiser le code processeur qu'après avoir choisi le bon algorithme et, surtout, on ne le fera jamais directement : on laissera le compilateur faire.

2. mesure du temps

On dispose de deux outils pour mesurer le temps :

Le premier va rendre une date (ce que l'on cherche est un temps et faire des différences de date est compliqué), dépendante du fuseau horaire et finalement moins précise (à la microseconde près) qu'un chronomètre (à la nanoseconde près).

On a déjà vu un exemple de mesure d'un code python avec le module timeit. Il n'est cependant pas pratique car il faut mettre le code sous la forme d'une chaîne à exécuter ou d'une fonction sans paramètre. Il est plus simple d'utiliser le chronomètre du module time.

from time import perf_counter_ns

def recherche(T, x):
    for e in T:
        if e == x:
            return True
    return False

T = list(range(100))
début = perf_counter_ns()
recherche(T, 42)
fin = perf_counter_ns()
t = fin - début

print("l'exécution de la fonction a duré :", t, "ns")

Ce qui donne chez moi :

l'exécution de la fonction a duré : 50458 ns

L'exécution de la fonction perf_counter_ns() rend un entier qui augmente de 1 toutes les nanosecondes. Si on exécute cette méthode juste avant et juste après l'exécution de la fonction recherche sa différence nous donne le temps d'exécution en nanosecondes.

3. Isoler l'algorithme du système

Isoler des autres programmes

Si vous relancez le code précédent plusieurs fois, vous constaterez que le temps mis n'est pas une constante :

from time import perf_counter_ns

def recherche(T, x):
    for e in T:
        if e == x:
            return True
    return False

T = list(range(100))

for _ in range(5):
    début = perf_counter_ns()
    recherche(T, 42)
    fin = perf_counter_ns()
    t = fin - début

    print("l'exécution de la fonction a duré :", t, "ns")

Par exemple :

l'exécution de la fonction a duré : 24500 ns
l'exécution de la fonction a duré : 3333 ns
l'exécution de la fonction a duré : 1875 ns
l'exécution de la fonction a duré : 2166 ns
l'exécution de la fonction a duré : 2125 ns

La première instruction a duré presque 10 fois plus de temps que les 4 suivantes. Ceci est dû au fait que notre programme python ne tourne pas tout seul sur l'ordinateur, de nombreux autres programmes fonctionnent en concurrence, c'est-à-dire que chacun va tourner une fraction du temps puis passer la main à un autre programme. Cela va si vite qu'on ne se rend pas compte qu'il n'y a qu'un seul programme qui tourne sur 1 processeur.

Notre chronomètre ne mesure donc pas le temps qu'a mis uniquement notre programme pour tourner mais également l'ensemble des programmes du système qui tournaient en même temps. Comme tous ces temps sont ajoutés, on peut relancer le programme plusieurs fois et prendre le minimum.

À retenir

Pour minimiser les variations dues aux exécutions d'autres programmes concurrents, on mesure l'exécution plusieurs fois (typiquement 10 fois, mais on peut diminuer ce temps si l'exécution de notre mesure est longue) et on prend le minimum.

Le code devient :

from time import perf_counter_ns

def recherche(T, x):
    for e in T:
        if e == x:
            return True
    return False

T = list(range(100))

t = None
for _ in range(10):
  début = perf_counter_ns()
  recherche(T, 42)
  fin = perf_counter_ns()
  delta = fin - début
  if (t is None) or (delta < t):
    t = delta

print("l'exécution de la fonction a duré :", t, "ns")

Et il donne chez moi :

l'exécution de la fonction a duré : 500 ns

Notez qu'on a initialisé le temps à None pour toujours prendre la première mesure qui donnera une valeur entière à t

Isoler de python

Maintenant que notre programme est isolé du reste du système, une dernière amélioration serait de l'isoler de python lui-même. En effet, python fait épisodiquement un état des lieux des différentes variables pour supprimer celles qui ne sont plus utilisées. Ce mécanisme s'appelle le ramasse-miettes et est un mécanisme fondamental qui permet de minimiser la mémoire utilisée. En règle générale il ne faut pas l'enlever mais dans notre cas cela peut être utile de voir uniquement la complexité de la fonction. Pour cela on utilise le module gc qui nous permet de contrôler ce mécanisme.

Le code devient maintenant :

from time import perf_counter_ns
import gc

def recherche(T, x):
    for e in T:
        if e == x:
            return True
    return False

T = list(range(100))

gc_actif = gc.isenabled()
if gc_actif:
    gc.disable()

t = None
for _ in range(10):
  début = perf_counter_ns()
  recherche(T, 42)
  fin = perf_counter_ns()
  delta = fin - début
  if (t is None) or (delta < t):
    t = delta

if gc_actif:
    gc.enable()

print("l'exécution de la fonction a duré :", t, "ns")

Notez que l'on ne réactive le ramasse-miettes que s'il était actif avant notre manipulation (on stocke l'état courant dans la variable gc_actif).

Qui donne chez moi :

l'exécution de la fonction a duré : 459 ns

On gagne un petit peu. Vous verrez que plus la taille du tableau augmente, plus on gagnera (et plus il est important de conserver ce mécanisme en temps normal puisqu'il permet de libérer de la mémoire non utilisée...)

Une fonction de mesure

Comme on va utiliser intensivement cette mesure de calcul, on va en faire une fonction qui sera facile à utiliser :

from time import perf_counter_ns
import gc

def calcul(f, f_params, rep=10):
    
    gc_actif = gc.isenabled()
    if gc_actif:
        gc.disable()

    t = None
    for _ in range(rep):
        début = perf_counter_ns()
        f(*f_params)
        fin = perf_counter_ns()

        delta = fin - début
        if (t is None) or (delta < t):
          t = delta

    if gc_actif:
        gc.enable()
    
    return t

On utilise la possibilité qu'offre python d'utiliser une liste comme suite de paramètres d'une fonction avec la notation *args.

On pourra l'utiliser ainsi :


T = list(range(100))
t = calcul(recherche, (T, 42))
print("l'exécution de la fonction a duré :", t, "ns")

Ce qui donne chez moi :

l'exécution de la fonction a duré : 416 ns
À retenir

Gardez-vous un fichier contenant les fonctions nécessaires à la mesure du temps. Cela vous permettra de l'inclure dans tous les projets ultérieurs où nous aurons besoin de mesurer la complexité.

Complexité maximum et minimum

Le but est de pouvoir mesurer la complexité maximale, minimale et moyenne d'un algorithme codé. La complexité dépendant d'un paramètre il faudra le faire varier pour déterminer la courbe de complexité (pour notre exemple de l'algorithme recherche, le paramètre était la longueur du tableau).

Pour que tout soit homogène, on crée alors deux fonctions dédiées prenant uniquement ce paramètre plutôt que les différents paramètres initiaux de l'algorithme :

def calcule_max(n):
    T = list(range(n))
    return calcul(recherche, (T, -1))


def calcule_min(n):
    T = list(range(n))
    return calcul(recherche, (T, 0))

La complexité max est en effet atteinte pour la recherche d'un élément qui n'est pas dans le tableau (ici -1) et la complexité minimale est atteinte pour la recherche du premier élément du tableau.

À retenir

Pour le calcul des complexités min et max on se crée des fonctions ayant uniquement comme paramètre celui utilisé pour le calcul de la complexité et on adapte les entrées de l'algorithme initial au calcul recherché.

On cherche à représenter graphiquement la durée par rapport au paramètre. Pour que notre courbe soit représentative :

Pour trouver rapidement le nombre N_max correspondant à T_MAX, on utilise l'algorithme suivant, qui double $n$ à chaque itération et s'arrête au premier $n$ dont la mesure prend plus que le temps maximum alloué :

def calcul_n_max(f_calcul_temps_complexité, n_min, T_MAX):
    n_max = n_min
    while f_calcul_temps_complexité(n_max) < T_MAX:
        n_max *= 2

    return n_max

Je trouve un N_max = 16777216 avec un temps max de 0.1s et le code suivant :

N_min = 1

T_max = 10 ** 8  # 0.1s
N_max = calcul_n_max(calcule_max, N_min, T_max)
print("Pour un dixième de seconde N_max =", N_max)

On ne peut pas se permettre de mesurer le temps pris pour tous les tableaux de taille 1 à N_max = 16777216, cela prendrait trop de temps et serait inutile. On utilise la fonction linspace du module numpy qui rend un découpage d'un intervalle donné. Si on veut un découpage en K points d'un intervalle allant de N_min à N_max, en gardant le fait que ce sont des entiers :

import numpy as np

K = 10
Ns = [int(x) for x in np.linspace(N_min, N_max, K)]
À retenir

Fixez-vous une taille min et max de paramètre et donnez-vous un nombre d'expérimentations $K$ pour déterminer les $K$ différentes mesures de temps à faire.

Déterminez les tailles min et max de paramètre une fois, ne refaites pas le calcul à chaque lancement.

On peut enfin calculer les temps min et max :

for n in Ns:
    print("taille", n)
    print("     max :", calcule_max(n))
    print("     min :", calcule_min(n))

Ce qui donne chez moi :

taille 1
     max : 83
     min : 42
taille 14913081
     max : 131349625
     min : 42
taille 29826162
     max : 262013875
     min : 83
taille 44739243
     max : 394027000
     min : 83
taille 59652324
     max : 526060458
     min : 83
taille 74565404
     max : 655763916
     min : 42
taille 89478485
     max : 795593000
     min : 41
taille 104391566
     max : 930963834
     min : 83
taille 119304647
     max : 1064934541
     min : 83
taille 134217728
     max : 1199735750
     min : 83

Les derniers calculs peuvent prendre du temps puisque l'on fait 10 fois un calcul qui va prendre de l'ordre de .1s. Si vous voulez accélérer le process :

  • soit diminuez le nombre maximum d'éléments dans le tableau,
  • soit diminuez le nombre de répétitions (passer de 10 à 5 par exemple),
  • soit les deux.

Complexité en moyenne

Pour calculer la complexité en moyenne, il faut chercher un entier quelconque du tableau ou pas. On peut par exemple utiliser le code suivant, utilisant la fonction randrange du module random :

import random

def calcule_moyenne(n, rep=10):
    T = list(range(n))
    return calcul(recherche, (T, random.randrange(-1, n)))

Mais ceci n'est pas suffisant car il peut y avoir de grandes variations selon l'élément à rechercher. Ci-après le temps pris pour un tableau de 100000 éléments, on va de 2208ns à près de 500000ns :

409500.0
488959.0
146625.0
93791.0
225209.0
422500.0
22125.0
317041.0
227875.0
2208.0

La solution est de moyenner le résultat (par défaut 10 essais) :

def calcule_moyenne(n, rep=10):
    T = list(range(n))
    t = calcul(recherche, (T, random.randrange(-1, n)))
    for _ in range(rep-1):
        t += calcul(recherche, (T, random.randrange(-1, n)))
    return t / rep

On peut alors ajouter la moyenne à notre calcul :

for n in Ns:
    print("taille", n)
    print("     max :", calcule_max(n))
    print("     moy :", calcule_moyenne(n))
    print("     min :", calcule_min(n))

Chez moi j'obtiens :

taille 1
     max : 83
     moyenne : 58.1
     min : 41
taille 14913081
     max : 129418084
     moyenne : 62261433.3
     min : 42
taille 29826162
     max : 259101583
     moyenne : 114150833.3
     min : 42
taille 44739243
     max : 388659917
     moyenne : 163993899.7
     min : 42
taille 59652324
     max : 516515208
     moyenne : 210178308.4
     min : 42
taille 74565404
     max : 645720458
     moyenne : 307273212.3
     min : 41
taille 89478485
     max : 785189500
     moyenne : 503277858.3
     min : 42
taille 104391566
     max : 915702833
     moyenne : 420030974.9
     min : 42
taille 119304647
     max : 1045916584
     moyenne : 506352900.1
     min : 42
taille 134217728
     max : 1185341667
     moyenne : 497359804.2
     min : 41

Les derniers calculs peuvent prendre du temps puisque l'on fait 10x un calcul qui va prendre de l'ordre de 10 x .1s. Si vous voulez accélérer le process :

  • soit diminuez le nombre maximum d'éléments dans le tableau,
  • soit diminuez le nombre de répétitions (passer de 10 à 5 par exemple),
  • soit diminuez le nombre d'essais pour la moyenne (passer de 10 à 5 par exemple),
  • soit deux des trois,
  • soit les trois.

Représentation graphique

Enfin, on peut représenter graphiquement les résultats. Pour cela, il faut commencer par stocker les résultats de nos mesures et pas juste les afficher :

c_min = []
c_moy = []
c_max = []
for n in Ns:
    print("taille", n)
    c_max.append(calcule_max(n))
    print("     max :", c_max[-1])
    c_moy.append(calcule_moyenne(n))
    print("     moy :", c_moy[-1])
    c_min.append(calcule_min(n))
    print("     min :", c_min[-1])

Et on utilise la fonction de dessin suivante qui affiche les 3 courbes de complexité :

import matplotlib.pyplot as plt

def affiche_complexité(N, c_min, c_moy, c_max):
    _, ax = plt.subplots(figsize=(20, 5))

    ax.set_title("complexités temporelles")
    ax.set_xlabel("taille du tableau")
    ax.set_ylabel("temps de calcul en ns")

    p1, = ax.plot(N, c_min, 'o-', label="min")
    p2, = ax.plot(N, c_moy, 'o-', label="moyenne")
    p3, = ax.plot(N, c_max, 'o-', label="max")


    ax.legend(handles=(p1, p2, p3))

    plt.show()

Fichiers finaux

On a séparé notre code en 3 fichiers :

algorithmes.py

import random

from mesure_temps import calcul

def recherche(T, x):
    for e in T:
        if e == x:
            return True
    return False


def calcule_max(n):
    T = list(range(n))
    return calcul(recherche, (T, -1), rep=5)


def calcule_min(n):
    T = list(range(n))
    return calcul(recherche, (T, 0))


def calcule_moyenne(n, rep=10):
    T = list(range(n))
    t = calcul(recherche, (T, random.randrange(-1, n)), rep=5)
    for _ in range(rep-1):
        t += calcul(recherche, (T, random.randrange(-1, n)), rep=5)
    return t / rep

mesure_temps.py

from time import perf_counter_ns
import gc

import matplotlib.pyplot as plt


def calcul(f, f_params, rep=10):
    
    gc_actif = gc.isenabled()
    if gc_actif:
        gc.disable()

    t = None
    for _ in range(rep):
        début = perf_counter_ns()
        f(*f_params)
        fin = perf_counter_ns()

        delta = fin - début
        if (t is None) or (delta < t):
          t = delta

    if gc_actif:
        gc.enable()
    
    return t

def calcul_n_max(f_calcul_temps_complexité, n_min, T_MAX):
    n_max = n_min
    while f_calcul_temps_complexité(n_max) < T_MAX:
        n_max *= 2

    return n_max

def affiche_complexité(N, c_min, c_moy, c_max):
    _, ax = plt.subplots(figsize=(20, 5))

    ax.set_title("complexités temporelles")
    ax.set_xlabel("taille du tableau")
    ax.set_ylabel("temps de calcul en ns")

    p1, = ax.plot(N, c_min, 'o-', label="min")
    p2, = ax.plot(N, c_moy, 'o-', label="moyenne")
    p3, = ax.plot(N, c_max, 'o-', label="max")


    ax.legend(handles=(p1, p2, p3))

    plt.show()

main.py

Avec une réduction du nombre de répétitions et un temps max de 1 centième de seconde :

import numpy as np

from mesure_temps import calcul_n_max, affiche_complexité
from algorithmes import calcule_max, calcule_min, calcule_moyenne

N_min = 1

T_max = 10**7  # 0.01s
N_max = calcul_n_max(calcule_max, N_min, T_max)
print("Pour", T_max / 10**9, "seconde, N_max =", N_max)

K = 6
Ns = [int(n) for n in np.linspace(N_min, N_max, K)]
print(Ns)

c_min = []
c_moy = []
c_max = []
for n in Ns:
    print("taille", n)
    c_max.append(calcule_max(n))
    print("     max :", c_max[-1])
    c_moy.append(calcule_moyenne(n))
    print("     moy :", c_moy[-1])
    c_min.append(calcule_min(n))
    print("     min :", c_min[-1])

affiche_complexité(Ns, c_min, c_moy, c_max)