La technique des sentinelles
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
7 nov. 2021 à 07:19