Optimisation d'un algorithme

Objectif

  • Découvrir l'optimisation algorithmique.

Mise en situation

La complexité algorithmique est une notion importante pour qui veut développer des applications capables de passer à l'échelle. Lors des étapes de développements, il est courant de tester les algorithmes sur de petits jeu de données. Mais si l'algorithme s'avère trop complexe, l'utilisation sur un plus grand volume de données peut s'avérer beaucoup plus lente ou gourmande en ressources. Il convient donc de réaliser une analyse de la complexité d'un algorithme avant de l'utiliser, et éventuellement de l'adapter et l'optimiser pour permettre un fonctionnement conforme à ce qui est attendu.

RappelComplexité algorithmique

La complexité algorithmique est une estimation du nombre d'opérations élémentaires pour résoudre un problème en fonction de la taille des données d'entrée, notée n. On note O() l'ordre de grandeur de la complexité d'un algorithme. Par exemple, O(n) signifie que le nombre d'opérations est de l'ordre de n (si on a 1000 données en entrée, on s'attend à environ 1000 opérations).

Complexité en temps

La complexité en temps est celle qui vient en premier dans l'esprit des développeurs. Elle donne un ordre d'idée du temps d’exécution d'un algorithme. L'estimer permet de chercher des optimisations qui permettront de réduire le temps de calcul. Il est parfois très simple de diviser par 2 le temps de calcul, ce qui se ressent du point de vue de l'utilisateur.

Complexité en espace

La complexité en espace est moins connue mais toute aussi importante. Elle donne un ordre de grandeur du nombre de « case mémoire » qui seront nécessaires au calcul. Réduire au maximum cette complexité évitera que le programme ne dysfonctionne car il n'y a pas plus assez de mémoire disponible.

Exemple

Soit deux algorithmes qui calculent la somme des entiers de 1 à n.

  • n est donné en entrée de l'algorithme.

  • Il existe une formule mathématique permettant d'obtenir la somme des n premiers entiers (n * (n - 1) / 2).

Le premier algorithme dit naïf est en O(n), le second utilisant la formule mathématique est en O(1). Ainsi, il faudra préférer le second algorithme car pour une complexité en espace identique, il possède une complexité en temps bien plus faible.

1
Algo Somme1aN:
2
3
Entrée:
4
    n, un entier positif
5
6
somme prend la valeur 0
7
Pour i de 1 à n alors:
8
    somme prend la valeur somme + i
9
FinPour
10
11
Retourner somme
1
Algo Somme1aN:
2
3
Entrée:
4
    n, un entier positif
5
6
somme prend la valeur n*(n+1)/2
7
8
Retourner somme
Méthode
  • La suppression de boucles est une bonne solution pour réduire la complexité d'un algorithme.
  • Il est également possible de réduire la complexité en supprimant des instructions simples. Par exemple, on parle de factorisation lorsqu'on condense plusieurs conditions en une seule instruction. Le nombre de calculs de comparaisons est réduit.
Ainsi, pour optimiser un algorithme, il faut commencer par supprimer les boucles superflues puis, dans un second temps, factoriser le code qui peut l'être.
Exemple
Dans l'exemple ci-dessous, le second algorithme réduit la complexité en temps car il fusionne les deux conditions en une seule. De plus, la complexité en espace est également réduite car il n'utilise plus de variable pour stocker le résultat.
1
Algo PeutConduire1:
2
3
Entrées:
4
    age, un entier
5
    permis, un booléen
6
7
résultat prend la valeur Vrai
8
9
Si age < 18 alors:
10
    resultat prend la valeur Faux
11
FinSi
12
13
Si age > 18 et non permis alors
14
    resultat prend la valeur Faux
15
FinSi
16
17
Retourner resultat
1
Algo PeutConduire2:
2
3
Entrées:
4
    age, un entier
5
    permis, un booléen
6
7
Si (age < 18) ou (age > 18 et non permis) alors:
8
    Retourner Faux
9
Sinon
10
    Retourner Vrai
11
FinSi
ComplémentChoisir entre espace et temps
Il arrive de devoir choisir entre un algorithme qui minimise le temps et un autre l'espace. Le choix devra être orienté par le domaine d'application. En informatique embarquée, l'espace est très limité donc le temps pourrait être sacrifié au profit d'un espace mémoire moindre. En Big Data, l'espace mémoire à disposition est gigantesque et l'accélération des calculs sera souhaitée.
À retenir
  • Il est possible d'estimer le temps d’exécution d'un algorithme ainsi que l'espace mémoire dont il a besoin grâce à la complexité algorithmique.
  • Un développeur doit chercher un algorithme minimisant le temps et l'espace.
  • Selon son domaine d'application, il pourra privilégier le temps ou l'espace.