CodeS-SourceS
Rechercher un code, un tuto, une réponse

La technique des sentinelles

Octobre 2017

Cette technique de programmation permet d'économiser des instructions dans plusieurs algorithmes classiques de manipulation de données.


Introduction


Une instruction en langage évolué (C ou autre) est une suite de plusieurs instructions en langage machine (assembleur). Gagner des instructions dans un algorithme, c'est gagner plusieurs instructions machines, c'est-à-dire de nombreux cycles d'exécution d'un algorithme.

Algorithme de base


Voici un algorithme de recherche d'une clé x dans un tableau a[] de quatre éléments non triés :


 
for ( i = 0,trouve = 0 ; i < 4 && !trouve; i++)
    if ( a[i] == x ) trouve = 1;

Cette version n'est pas très efficace :
  • On réalise 2 initialisations (2 instructions) ;
  • On réalise 2 tests (2 instructions) avant chaque passage dans la boucle ( i < 4 et trouve != 0)

Algorithme amélioré


Une version un peu plus travaillée de cet algorithme est :


for ( i = 0;i < 4; i++)
    if ( a[i] == x ) i = 5;
trouve = (i == 5);

On gagne :
  • 1 initialisation (1 instruction) en début d'algorithme;
  • 1 test (1 instruction) avant chaque passage de boucle.Soit n instructions sur un tableau de n éléments (dans le meilleur des cas).

Algorithme optimisé


En retravaillant un peu l'algorithme, on peut réduire encore le nombre d'instructions :

 
i = 0 ;
while ( i< 4 && (a[i] != x) ) i++ ;
trouve = (i < 4 );

Ici on gagne juste une instruction : une affectation (i = 5). C est toujours ça...

Algorithme avec sentinelle


Enfin, on peut exécuter l'algorithme sans tester l'indice de boucle. Il suffit de prévoir une case de travail, où l'on place la clé x pour être sûr de la trouver. Cette case s'appelle une sentinelle.

a = | 4 | 3 | 2 | 5 | x |

On peut aussi voir les sentinelles comme des éléments butoirs dans l'exécution d'un algorithme.

 
a[4] = x ; // sentinelle
i = 0 ;
while (a[i] != x ) i++ ;
trouve = (i < 4) ;

En éliminant le test de l'indice de boucle, on gagne encore n instructions sur un tableau de n éléments (dans le meilleur des cas).

C'est-à-dire que par rapport à l'algorithme de base, on a gagné jusqu'à 2n + 2 instructions.

Avec un tableau de 4 éléments, l'économie en instructions est insignifiante, mais avec des tableaux de plusieurs milliers ou million de cellules, l'économie est de plusieurs milliers ou plusieurs millions d'instructions gagnées.

Dans le cas où la recherche se fait en sens inverse, on place la sentinelle au début du tableau.

Dans le cas où l'on ne sait pas dans quel sens se fera la recherche on crée un tableau avec deux sentinelles, une en début de tableau et une en fin de tableau.

Les sentinelles sont utilisables avec les tableaux, les listes, les arbres et d'autres structures de données.

Un autre exemple d'algorithme utilisant une sentinelle : http://codes-sources.commentcamarche.net/source/37794-tri-par-insertion-avec-sentinelle
Publié par cs_AlexN.
Ce document intitulé «  La technique des sentinelles  » issu de CodeS-SourceS (codes-sources.commentcamarche.net) est mis à disposition sous les termes de la licence Creative Commons. Vous pouvez copier, modifier des copies de cette page, dans les conditions fixées par la licence, tant que cette note apparaît clairement.
Colinux, une installation système exotique
Débuter en C++ sous Windows avec les principaux IDE