Technique – Optimisation par savoir discret

Ce que je nommerai ici Optimisation par savoir discret est une technique simple par laquelle un sous-programme peut générer très rapidement une donnée parmi un ensemble fini – donc susceptibles d'être identifiées par des entiers – de données.

Cas type – virage à gauche

Imaginons un programme dans lequel le concept de déplacement est exploité et pour lequel les directions correspondent aux quatre points cardinaux que sont Est, Nord, Ouest et Sud – utiliser plus de directions ne changerait en rien la stratégie, alors nous limiterons l'exemple à cette courte liste de directions possibles.

Notre objectif sera d'écrire la fonction gauche() prenant en paramètre une direction d et retournant la direction correspondant à un virage à gauche de 90° (π/2 radians) par rapport à d.

Une version que je qualifierais de naïve suit:

const std:string DIR_EST   = "EST";
const std:string DIR_NORD  = "NORD";
const std:string DIR_OUEST = "OUEST";
const std:string DIR_SUD   = "SUD";
// Fonction gauche(), version naïve
// La direction est représentée par une chaîne de caractères,
// ce qui est lent et difficile à internationaliser.
// On présume ici que avant est une direction a priori valide,
// pour éviter de gérer les erreurs
std::string gauche (const std::string &avant)
{
   std::string apres;
   if (avant == DIR_EST)
      apres = DIR_NORD;
   else if (avant == DIR_NORD)
      apres = DIR_OUEST;
   else if (avant == DIR_OUEST)
      apres = DIR_SUD;
   else // avant == DIR_SUD
      apres = DIR_EST;
   return apres;
}

Cette version est naïve pour deux raisons. La première est qu'elle fait usage d'un type de données très peu approprié au problème – une chaîne de caractères – ce qui implique que la comparaison de directions nécessite une boucle complexe de comparaisons caractère par caractère et ce qui rend l'internationalisation de la fonction difficile.

Une version moins naïve en ce sens serait:

using Direction = short;
const Direction DIR_EST   = 0,
                DIR_NORD  = 1,
                DIR_OUEST = 2,
                DIR_SUD   = 3;
// Fonction gauche(), version naïve mais un peu moins
// La direction est représentée par un entier.
// On présume ici que avant est une direction a priori
// valide, pour éviter de gérer les erreurs
Direction gauche(Direction avant)
{
   Direction apres;
   if (avant == DIR_EST)
      apres = DIR_NORD;
   else if (avant == DIR_NORD)
      apres = DIR_OUEST;
   else if (avant == DIR_OUEST)
      apres = DIR_SUD;
   else // avant == DIR_SUD
      apres = DIR_EST;
   return apres;
}

...ou encore :

enum Direction : short
{
   Est, Nord, Ouest, Sud
};
// Fonction gauche(), version naïve mais un peu moins
// La direction est représentée par un entier.
// On présume ici que avant est une direction a priori
// valide, pour éviter de gérer les erreurs
Direction gauche(Direction avant)
{
   Direction apres;
   if (avant == Est)
      apres = Nord;
   else if (avant == Nord)
      apres = Ouest;
   else if (avant == Ouest)
      apres = Sud;
   else // avant == Sud
      apres = Est;
   return apres;
}

La seconde est plus complexe, tenant de la naïveté structurelle de cette fonction. Cet article a pour rôle de la décrire et de montrer comment amener l'implémentation de fonctions semblables à gauche() plus près de standards professionnels de performance et d'élégance.

Première optimisation – d'une séquence d'alternatives à une sélective

La séquence d'alternatives étant maintenant faite sur des entiers, on pourrait la remplacer par une sélective – les sélectives en C, C++ ou Java, pour ne donner que ces exemples, ne sont possibles que sur des entiers.

Nous obtenons alors :

enum Direction : short
{
   Est, Nord, Ouest, Sud
};
// Fonction gauche(), version naïve mais un peu moins
// La direction est représentée par un entier.
// On présume ici que avant est une direction a priori
//  valide, pour éviter de gérer les erreurs
Direction gauche(Direction avant)
{
   Direction apres;
   switch (avant)
   {
   case Est:
      apres = Nord;
      break;
   case Nord:
      apres = Ouest;
      break;
   case Ouest:
      apres = Sud;
      break;
   case Sud:
      apres = Est;
      break;
   default: // gérer les directions erronnées
      ;
   }
   return apres;
}

À moins de faire affaire avec un très mauvais compilateur, cette version devrait être plus rapide et plus claire que la précédente.

Seconde optimisation – d'une sélective à une indirection à un seul niveau

Une sélective demande l'évaluation d'une condition et la comparaison de sa valeur avec plusieurs cas possibles. En général, les sélectives sont plus rapides que les séquences d'alternatives qu'elles remplacent du fait que leur condition n'est évaluée qu'une seule fois (dans une séquence d'alternatives, dans le pire cas, la condition de chaque if aura été évaluée).

Cela dit, si on prend les valeurs possibles de directions pour des index dans un tableau, on peut améliorer la situation. Présumant que la direction avant est valide, le corps de la fonction gauche() devient aisément une simple indirection faite à partir d'un tableau où la direction à gauche de chaque direction avant possible est précalculée:

enum Direction : short
{
   Est = 0, Nord, Ouest, Sud
};
// Fonction gauche(), version rapide
// La direction est représentée par un entier.
// On présume ici que avant est une direction a priori
// valide, pour éviter de gérer les erreurs
Direction gauche(Direction avant)
{
   static const Direction apres[] =
   {
      Nord,  // à gauche de Est
      Ouest, // à gauche de Nord
      Sud,   // à gauche de Ouest
      Est    // à gauche de Sud
   };
   return apres[avant];
}

Cette version est très rapide: un compilateur décent brûlera la constante qu'est le tableau apres à la compilation, de manière à ce que le seul bout de code à exécuter réellement en fin de compte soit l'indirection dans le tableau (la dernière ligne de la fonction).

Remarquez que pour que cette technique soit applicable, il faut:

Une version plus robuste, au sens de résistante à un indice avant qui serait illégal, serait :

enum Direction : short
{
   Est = 0, Nord, Ouest, Sud
};
class DirectionInvalide {};
// Fonction gauche(), version rapide mais robuste
Direction gauche(Direction avant)
{
   static const Direction apres[] =
   {
      Nord,  // à gauche de Est
      Ouest, // à gauche de Nord
      Sud,   // à gauche de Ouest
      Est    // à gauche de Sud
   };
   if (avant < Est || avant > Sud)
      throw DirectionInvalide{};
   return apres[avant];
}

Cette version est légèrement plus lente que la précédente à cause du test (le if) supplémentaire.

Si le service gauche() était offert par un objet (que je nommerai serveur), alors il deviendrait relativement simple d'exposer les versions sécurisée et non sécurisée de manière à ce que les accès venant de l'extérieur du serveur, donc potentiellement à risque, passent par la version sécurisée du service alors que les accès internes au serveur, pour lesquels on serait en droit de présumer que les paramètres sont préalablement validés, passeraient par la version rapide mais non sécurisée.

class ServeurOrientation
{
   // version rapide mais non sécurisée
   Direction gaucheBrut (const Direction &avant) const
   {
      static const Direction apres[] =
      {
         Nord,  // à gauche de Est
         Ouest, // à gauche de Nord
         Sud,   // à gauche de Ouest
         Est    // à gauche de Sud
      };
      return apres[avant];
   }
   // ...
public:
   enum Direction : short
   {
      Est = 0, Nord, Ouest, Sud
   };
   class DirectionInvalide {};
   // Fonction gauche(), version sécurisée
   Direction gauche(Direction avant) const
   {
      static const Direction apres[] =
      {
         Nord,  // à gauche de Est
         Ouest, // à gauche de Nord
         Sud,   // à gauche de Ouest
         Est    // à gauche de Sud
      };
      if (avant < Est || avant > Sud)
         throw DirectionInvalide{};
      return apres[avant];
   }
   // ...
};

...ou, mieux encore :

class ServeurOrientation
{
   // version rapide mais non sécurisée
   Direction gaucheBrut (const Direction &avant) const
   {
      static const Direction apres[] =
      {
         Nord,  // à gauche de Est
         Ouest, // à gauche de Nord
         Sud,   // à gauche de Ouest
         Est    // à gauche de Sud
      };
      return apres[avant];
   }
   // ...
public:
   enum Direction : short
   {
      Est = 0, Nord, Ouest, Sud
   };
   class DirectionInvalide {};
   // Fonction gauche(), version sécurisée
   Direction gauche(Direction avant) const
   {
      if (avant < Est || avant > Sud)
         throw DirectionInvalide{};
      return gaucheBrut (avant);
   }
   // ...
};

...ou encore mieux :

class ServeurOrientation
{
   // version rapide mais non sécurisée
   Direction gaucheBrut (const Direction &avant) const
   {
      static const Direction apres[] =
      {
         Nord,  // à gauche de Est
         Ouest, // à gauche de Nord
         Sud,   // à gauche de Ouest
         Est    // à gauche de Sud
      };
      return apres[avant];
   }
   // ...
public:
   enum Direction : short
   {
      Est = 0, Nord, Ouest, Sud
   };
   class DirectionInvalide {};
   static bool est_valide(Direction d) const
   {
      return d >= Est && d <= Sud;
   }
   // Fonction gauche(), version sécurisée
   Direction gauche(Direction avant) const
   {
      if (!EstDirectionValide (avant))
         throw DirectionInvalide{};
      return gaucheBrut (avant);
   }
   // ...
};

Exploiter le constructeur

Et si le nombre d'initialisations à réaliser était important? On se doute qu'initialiser un tableau constant peut alors devenir pénible et prêter à des erreurs humaines. Par exemple, si on veut appliquer cette technique pour écrire la fonction est_operateur_arithmetique(c) (qui retournerait VRAI si et seulement si le caractère passé en paramètre fait partie de l'ensemble { +, -, *, /, % }), l'initialisation d'un tableau constant ressemblerait à:

// La fonction prend en paramètre un caractère non signé
// pour s'assurer que la valeur entière dudit caractère
// ne soit pas négative (ce qui mènerait alors à un index
// illégal dans le tableau)
bool est_operateur_arithmetique(unsigned char c)
{
   static const bool resultat[256] =
   {
      false false false false false false false false
      false false false false false false false false
      false false false false false false false false
      false false false false false false false false
      false false false false false true  false false
      false false true  true  false true  false true
      false false false false false false false false
      false false false false false false false false
      false false false false false false false false
      false false false false false false false false
      false false false false false false false false
      false false false false false false false false
      false false false false false false false false
      false false false false false false false false
      false false false false false false false false
      false false false false false false false false
      false false false false false false false false
      false false false false false false false false
      false false false false false false false false
      false false false false false false false false
      false false false false false false false false
      false false false false false false false false
      false false false false false false false false
      false false false false false false false false
      false false false false false false false false
      false false false false false false false false
      false false false false false false false false
      false false false false false false false false
      false false false false false false false false
      false false false false false false false false
      false false false false false false false false
      false false false false false false false false
   };
   return resultat[c];
}

On voit assez rapidement à quel point ce code est difficile à valider et à entretenir (sans compter qu'il ne fonctionne que pour certains encodages de caractères, ce qui le rend difficilement internationalisable).

On pourrait vouloir générer ce tableau plus intelligemment, mais il y a un prix à payer pour cela :

// La fonction prend en paramètre un caractère non signé
// pour s'assurer que la valeur entière dudit caractère
// ne soit pas négative (ce qui mènerait alors à un index
// illégal dans le tableau)
bool est_operateur_arithmetique(unsigned char c)
{
   bool resultat[256] = { 0 }; // par défaut: 0 (false) partout
   // on corrige les quelques cases pour lesquelles la réponse
   // n'est pas false
   resultat['+'] = true;
   resultat['-'] = true;
   resultat['*'] = true;
   resultat['/'] = true;
   resultat['%'] = true;
   // on répond à la question
   return resultat[c];
}

Le prix est une perte significative de rapidité, puisque le tableau ne peut plus être constant et doit donc être réinitialisé à chaque appel – ici, notre optimisation coûte plus cher qu'une sélective bien écrite.

Si on applique une stratégie OO, par contre, on a le meilleur des deux mondes. Le constructeur de l'objet (du serveur exposant un service d'identification des opérateurs arithmétiques) peut initialiser le tableau à la création de l'objet, puis il ne reste plus aux appels à la méthode est_operateur_arithmetique() qu'à utiliser le savoir ainsi préparé de manière optimale:

class ServeurOperateursArithmetiques
{
   bool resultat_[256];
public:
   ServeurOperateursArithmetiques()
   {
      // initialisation du tableau
      fill(begin(resultat_), end(resultat_), false);
      resultat_['+'] = true;
      resultat_['-'] = true;
      resultat_['*'] = true;
      resultat_['/'] = true;
      resultat_['%'] = true;
   }
   bool est_operateur_arithmetique(unsigned char c) const
      { return resultat_[c]; }
};

...ou, pris sous un angle plus près du foncteur que du serveur :

class est_operateur_arithmetique
{
   bool resultat_[256];
public:
   est_operateur_arithmetique ()
   {
      // initialisation du tableau
      fill(begin(resultat_), end(resultat_), false);
      resultat_['+'] = true;
      resultat_['-'] = true;
      resultat_['*'] = true;
      resultat_['/'] = true;
      resultat_['%'] = true;
   }
   bool operator()(unsigned char c) const
      { return resultat_[c]; }
};

Les plus éveillé(e)s parmi vous remarqueront qu'on peut faire encore mieux. En effet, ici, chaque instance de notre serveur comprend sa propre version du tableau resultat_, or tous les serveurs auront précisément les mêmes valeurs dans leur propre version de ce tableau. On pourrait régler cet irritant avec un singleton (en exercice) ou, ce qui est élégant, en cachant un serveur unique et interne à la classe à l'intérieur de celle-ci:

class est_operateur_arithmetique
{
   class ServeurInterne
   {
      bool resultat_[256];
   public:
      ServeurInterne()
      {
         fill(begin(resultat_), end(resultat_), false);
         resultat_['+'] = true;
         resultat_['-'] = true;
         resultat_['*'] = true;
         resultat_['/'] = true;
         resultat_['%'] = true;
      }
      bool est_operateur_arithmetique(unsigned char c) const
         { return resultat_[c]; }
   };
   static ServeurInterne serveur_;
public:
   bool operator()(unsigned char c) const
   {
      return serveur_::est_operateur_arithmetique(c);
   }
};
// définition du serveur interne (cacher dans un .cpp)
est_operateur_arithmetique::ServeurInterne serveur_;

Lectures complémentaires

Quelques liens pour enrichir le propos.

Valid XHTML 1.0 Transitional

CSS Valide !