La technique des sentinelles

Dernière mise à jour le par BunoCS .

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

A voir également
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
Rejoignez-nous