Mesurer l'efficacité d'un algorithme
Deux algorithmes peuvent donner le même résultat, mais l'un en une seconde et l'autre en une heure. Comment les comparer ? En comptant le travail qu'ils font.
Compter les comparaisons
Reprenons deux façons de chercher une valeur dans un tableau trié. Chaque fonction renvoie non pas la position, mais le nombre de comparaisons qu'elle a faites :
fonction comparaisonsLineaire(liste, cherche)
compteur est un nombre vaut 0
pour i de 0 à longueur(liste) - 1
compteur ajoute 1
si liste[i] = cherche alors
retourne compteur
fin si
fin pour
retourne compteur
fin fonction
fonction comparaisonsDichotomie(liste, cherche)
compteur est un nombre vaut 0
mini est un nombre vaut 0
maxi est un nombre vaut longueur(liste) - 1
milieu est un nombre
tant que mini <= maxi
milieu vaut arrondi_inferieur((mini + maxi) / 2)
compteur ajoute 1
si liste[milieu] = cherche alors
retourne compteur
sinon si liste[milieu] < cherche alors
mini vaut milieu + 1
sinon
maxi vaut milieu - 1
fin si
fin tant que
retourne compteur
fin fonction
nombres est un tableau vaut intervalle(1, 1000)
affiche 'Recherche simple : ' + comparaisonsLineaire(nombres, 1000) // 1000
affiche 'Dichotomie : ' + comparaisonsDichotomie(nombres, 1000) // 10
intervalle(1, 1000) fabrique le tableau [1, 2, 3, ... 1000]. Pour y trouver 1000, la recherche simple regarde les 1000 cases. La dichotomie n'en regarde que 10 !
Et quand les données grossissent ?
Le plus important n'est pas le chiffre lui-même, mais comment il évolue quand le tableau grandit. Place ces lignes sous les deux fonctions :
tailles est un tableau vaut [1000, 10000, 100000]
donnees est un tableau
quantite est un nombre
pour k de 0 à 2
quantite vaut tailles[k]
donnees vaut intervalle(1, quantite)
affiche quantite + ' valeurs :'
affiche ' simple : ' + comparaisonsLineaire(donnees, quantite)
affiche ' dichotomie : ' + comparaisonsDichotomie(donnees, quantite)
fin pour
Les résultats :
- 1 000 valeurs : 1 000 comparaisons contre 10 ;
- 10 000 valeurs : 10 000 contre 14 ;
- 100 000 valeurs : 100 000 contre 17.
Quand le tableau est 100 fois plus grand, la recherche simple travaille 100 fois plus. La dichotomie, elle, ne fait que 7 comparaisons de plus.
Question : Un tableau trié passe de 1 000 à 2 000 valeurs. Combien de comparaisons de plus pour la dichotomie, dans le pire cas ? — Une seule. Doubler le nombre de valeurs n'ajoute qu'une étape : la première comparaison élimine d'un coup la moitié du tableau.
Les boucles imbriquées coûtent cher
Autre exemple : chercher si un tableau contient un doublon en comparant chaque valeur à toutes les suivantes.
fonction comparaisonsDoublon(quantite)
compteur est un nombre vaut 0
pour i de 0 à quantite - 2
pour j de i + 1 à quantite - 1
compteur ajoute 1
fin pour
fin pour
retourne compteur
fin fonction
affiche '100 valeurs : ' + comparaisonsDoublon(100) // 4950
affiche '200 valeurs : ' + comparaisonsDoublon(200) // 19900
affiche '400 valeurs : ' + comparaisonsDoublon(400) // 79800
Regarde bien : quand le nombre de valeurs double, le travail est multiplié par quatre environ. C'est la marque des deux boucles imbriquées : le travail grandit comme le carré de la taille. Pour 10 fois plus de données, 100 fois plus de travail.
Chronométrer
Compter les opérations est fiable. On peut aussi mesurer le temps réel avec chrono() :
fonction comparaisonsDoublon(quantite)
compteur est un nombre vaut 0
pour i de 0 à quantite - 2
pour j de i + 1 à quantite - 1
compteur ajoute 1
fin pour
fin pour
retourne compteur
fin fonction
depart est un nombre
resultat est un nombre
tailles est un tableau vaut [100, 200, 400]
pour k de 0 à 2
depart vaut chrono()
resultat vaut comparaisonsDoublon(tailles[k])
affiche tailles[k] + ' valeurs : ' + arrondi(chrono() - depart) + ' ms'
fin pour
Les durées dépendent de ton ordinateur, et changent un peu d'une exécution à l'autre. Mais la tendance est là : chaque ligne prend environ quatre fois plus de temps que la précédente.
Un chronométrage n'est fiable que si le travail est assez long. Pour une opération très rapide, répète-la mille fois et mesure le tout.
Trois familles à connaître
- Le travail grandit très lentement (dichotomie) : doubler les données ajoute une étape. Un million de valeurs : 20 étapes.
- Le travail grandit comme les données (parcourir un tableau, chercher un maximum, faire une somme) : deux fois plus de données, deux fois plus de travail. Un million de valeurs : un million d'étapes.
- Le travail grandit comme le carré (deux boucles imbriquées, tri à bulles, tri par insertion) : deux fois plus de données, quatre fois plus de travail. Un million de valeurs : mille milliards d'étapes... bien trop long.
Avec dix ou cent valeurs, tout va vite et la différence ne se voit pas. C'est quand les données grossissent que le choix de l'algorithme devient décisif.
En résumé
- On compare des algorithmes en comptant leurs opérations, pas seulement en les chronométrant.
- Ce qui compte, c'est l'évolution du travail quand les données grandissent.
- Une boucle : travail proportionnel. Deux boucles imbriquées : travail au carré.
- La dichotomie est spectaculaire, mais elle exige un tableau trié.
