Algorithmique impérative/Inversion de deux variables

Problèmatique

Nous disposons de deux entiers a et b. Nous voulons intervertir ces deux nombres. À la fin du programme : la valeur de a sera égale à celle de b lors du lancement du programme et inversement : b sera égal au a initial.

Exemple : au début du programme nous posons a=2 et b=3. À la fin du programme nous aurons a=3 et b=2.

Solutions

Voici deux solutions acceptables :

Algorithme inversion_stockage
Variables
  a : entier
  b : entier
  temp : entier (* variable dans laquelle on stockera le contenu
                   d'une variable pour ne pas l'écraser au moment
                   de la première assignation *)
Début
  temp := a (* on sauvegarde a qui sera effacée à la ligne suivante
               pour pouvoir la placer dans b plus tard *)
  a := b
  b := temp
Fin

Algorithme inversion_calcul
Variables
  a : entier
  b : entier
Début
  a := a+b
  b := a-b
  a := a-b
Fin

Remarque

Ces deux solutions présentent en fait une notion clé de l'informatique : étudions nos deux solutions de plus près :

Simplifions le fonctionnement d'une machine au maximum : supposons

• Qu'il faut utiliser une unité de mémoire pour stoker une variable en mémoire
• Qu'il faut une unité de temps au processeur pour effectuer un calcul et qu'une opération entière et l'assignation consistent toutes en 1 calcul.

Temps de calcul requis par chaque algorithme :

• Pour inversion_stockage : 3 unités de temps (3 assignations)
• Pour inversion_calcul : 6 unités de temps (3 assignations + 1 somme + 2 différences)

Mémoire requise par chaque algorithme :

• Pour inversion_stockage : 3 unités de mémoire (a, b et temps)
• Pour inversion_calcul : 2 unités de mémoire (a et b)

On a donc que

• inversion_stockage prend plus de mémoire mais moins de temps de calcul que inversion_calcul
• inversion_calcul prend plus de temps de calcul mais moins de mémoire que inversion_stockage

Et c'est là un concept généralisable :

D'une façon générale, vous pouvez faire des algorithmes plus rapides en utilisant plus de mémoire et des algorithmes utilisant moins de ressources mémoire mais qui seront plus lents.

Attention cependant, cela ne veut surtout pas dire qu'aucun algorithme n'est améliorable sans perte de ressources en calcul ou en mémoire. Bien au contraire, vous devez toujours essayer d'être le plus efficace possible.

Ce constat ne permet pas de dire si un des algorithmes est plus efficace que l'autre : notre analyse a été trop simplifiée pour cela. En effet, nous n'avons pas considéré que :

• la mise en mémoire peut aussi prendre un temps non négligeable ;
• peut-être que les calculs de sommes et de différences sont très coûteux en temps ;
• peut-être que le processeur est assez avancé technologiquement pour effectuer un premier calcul et en commencer un deuxième avant d'avoir obtenu le premier résultat ;
• l'algorithme pourrait utiliser des réels, et, en général, les calculs sur les réels sont plus longs que sur les entiers.

Vous contesterez, avec raison, que sur cet exemple, aujourd'hui nos ordinateurs sont parfaitement capables d'exécuter ces deux programmes en un temps record et qu'on ne distinguera pas la différence suivant qu'on utilise l'un ou l'autre. C'est vrai, mais vous négligez que peut-être :

• ce programme sera exécuté sur une machine minuscule, une micro-puce de quelques millimètres dans laquelle on n'a pu mettre que très peu de mémoire et un minuscule processeur ;
• ce programme doit pouvoir être exécuté simultanément des milliers de fois sur la même machine ;
• ce programme ne sera pas exécuté plusieurs fois en même temps mais des milliers de fois, les unes après les autres, et que le programme ayant besoin d'inverser des milliers de valeurs à la suite doit pouvoir donner un résultat dans la seconde...

En réalité, n'importe quel compilateur décent, depuis les années 80, va optimiser bien au delà de ce que le programmeur moyen aura le courage de faire. Par exemple sur l'échange : utiliser deux registres au lieu d'une variable supplémentaire (R1 := A; R2 := B; A := R2; B:= R1) si les données tiennent dans un mot machine, ou utiliser les instructions spécialisées du processeur d'échange de deux zones en mémoire. En écrivant la forme la plus simple d'échange, le compilateur reconnaitra (parce qu'on lui a inculqué un certain nombre de recettes) de quoi il s'agit, et fabriquera le meilleur code possible. Le temps consacré à de la micro-optimisation est en général une perte sèche, il est de loin préférable de la consacrer à une bonne conception, et à l'utilisation d'algorithmes efficaces.