De l'optimisation des programmes

Assez régulièrement j'entends parler et parle moi même de l'optimisation des programmes, bien entendu à chaque fois ce genre de discussion débouche sur un bon nombre de petites «astuces» ou «hack» destinés à grappiller quelques mili ou micro secondes. Bien au delà de toutes ces techniques divers et variées qui ne sont bien souvent même pas perceptibles, je vous propose ici une démonstration par l'exemple la règle d'or de l'optimisation d'un programme. Les différents codes d'exemple sont écrits en C ANSI, mais le propos reste vrai pour tous les langages de programmation.

Le problème

Afin de mettre en valeur notre règle d'or, prenons l'exemple suivant (qui est largement connu sous divers formes) : Dans une prison, on compte autant de gardiens que de cellules. Le soir, toutes les portes étant fermées, les gardiens jouent à un jeu étrange. Le premier passe et change l'état de toutes les portes. Changer l'état d'une porte signifiant l'ouvrir si elle était fermée et la fermer si elle était ouverte, il ouvre donc toutes les portes. Le second gardien passe et change l'état d'une porte sur deux, puis le troisième d'une porte sur trois et ainsi de suite pour chaque gardien. Notre but est de créer un programme qui, connaissant le nombre de cellules nous dit si une cellule précise sera ouverte ou fermée à la fin du passage de tous les gardiens.

La résolution

La base de notre programme

Afin de se concentrer sur la méthode de détermination de l'état de la cellule, nous utiliseront le main suivant :

int
main(int argc, char *argv[])
{
  int nb_cells, num_cell;

  if (argc != 3)
    return 1;
  nb_cells = atol(argv[1]);
  num_cell = atol(argv[2]);
  if (nb_cells < num_cell)
    return 2;
  printf("%s\n", is_open(nb_cells, num_cell) ? "opened" : "closed");
  return 0;
}

Partant de là, il ne nous reste plus qu'a inclure les bibliothèques adéquat (stdlib.h et stdio.h) et à coder la fonction is_open dont le prototype est le suivant :

static int
is_open(const int nb_cells, const int num_cell);

Premier algorithme : la méthode naïve

Lorsque l'on rencontre ce genre de problème, l'on vois tout de suite comment s'en sortir : l'on vas stocker l'état de la cellule (initialisé à 0) dans une variable, puis faire une boucle pour chaque gardien. A chaque tour de boucle, on change l'état de la cellule si le gardien le change ou non. Afin de savoir si un gardien de numéro donné change l'état de la cellule, il suffit de regarder si le numéro de la cellule est un multiple du numéro du gardien, chose à laquelle un modulo se prête aisément.

static int
is_open(const int nb_cells, const int num_cell)
{
  int i, status;

  status = 0;
  for (i = 1; i <= nb_cells; i++)
    {
      if (num_cell % i == 0)
      status = !status;
    }
  return status;
}

Maintenant que nous avons mis au point notre fonction, testons et regardons le temps d'exécution. Pour un faible nombre de cellules c'est tout bon, par contre quand l'on commence à en avoir beaucoup notre programme se traîne.

tycho@uraniborg-> cc prisonniers.c -ansi -pedantic -Wall -Wextra
tycho@uraniborg-> time ./a.out 200 42
closed

real    0m0.016s
user    0m0.000s
sys 0m0.000s
tycho@uraniborg-> time ./a.out 200000000 42
closed

real    0m4.186s
user    0m4.088s
sys 0m0.012s

Un algorithme plus intelligent

Lorsque l'on se penche un peu plus longtemps sur le problème, on se rend compte d'une propriété intéressante : l'état d'une cellule peut se déterminer simplement par une formule mathématique ! En effet, une cellule sera ouverte si son numéro est le carré d'un nombre entier. On peut donc en déduire l'implémentation suivante de notre fonction is_open :

static int
is_open(const int nb_cells, const int num_cell)
{
  int a;

  (void)nb_cells;
  a = sqrt(num_cell);
  return a * a == num_cell;
}

Afin de déterminer si le numéro de la cellule est le carré d'un nombre entier, on prend la partie entière de sa racine carrée (a étant un int, le retour de sqrt() est arrondi) et on l'élève au carré afin de vérifier si on retombe bien sur le même nombre.Cette méthode ayant l'avantage de ne pas dépendre du nombre de cellules pour déterminer l'état d'une seule cellule, son temps d'exécution reste donc relativement constant. On remarquera que l'appel à sqrt() demande l'inclusion de math.h et la compilation avec la libmath (-lm).

tycho@uraniborg-> cc prisonniers.c -lm -ansi -pedantic -Wall -Wextra
tycho@uraniborg-> time ./a.out 200 42
closed

real    0m0.001s
user    0m0.000s
sys 0m0.000s
tycho@uraniborg-> time ./a.out 200000000 42
closed

real    0m0.001s
user    0m0.000s
sys 0m0.000s

Conclusion

Vous avez certainement déduit de vous même la règle d'or de l'optimisation : de l'utilisation du bon algorithme dépendra la vitesse de votre programme. Il ne sert à rien de se mettre à économiser des millisecondes lorsque l'algorithme que l'on utilise est mauvais, il y a de fortes chances pour qu'un tel programme ne rattrape jamais un autre programme moins «optimisé» mais mieux conçu.

Le code complet

Pour ceux d'entre vous qui n'apprécient pas avoir des petits bouts de code partout et ne savent pas quoi en faire, voici le code au grand complet :

#include <stdlib.h>
#include <stdio.h>
#include <math.h>

static int
is_open(const int nb_cells, const int num_cell)
{
  int a;

  (void)nb_cells;
  a = sqrt(num_cell);
  return a * a == num_cell;
}

int
main(int argc, char *argv[])
{
  int nb_cells, num_cell;

  if (argc != 3)
    return 1;
  nb_cells = atol(argv[1]);
  num_cell = atol(argv[2]);
  if (nb_cells < num_cell)
    return 2;
  printf("%s\n", is_open(nb_cells, num_cell) ? "opened" : "closed");
  return 0;
}