retour




Algorithmique pratique et optimisation de code :
les éliminatoires du Prologin édition 2005


Notice

Le présent document est publié sous la licence « Verbatim Copying » telle que définie par la Free Software Fondation dans le cadre du projet GNU.


Toute copie ou diffusion de ce document dans son intégralité est permise (et même encouragée), quel qu'en soit le support à la seule condition que cette notice, incluant les copyrights, soit préservée.


Copyright (C) 2005 Yann LANGLAIS, ilay.


PROLOGIN est une association loi 1901 visant à permettre à de jeunes passionés d'informatique de se rencontrer pour se mesurer entre eux et de faciliter les échanges d'idées. Elle organise tous les ans le Concours National d'Informatique. Elle est parainnée par le Ministre délégué à la Recherche et aux Nouvelles Technologies, et sponsorisée par l'Epita, Hexaglobe et les magazines PCTeam et Login:.


La plus récente version en date de ce document est sise à l'url http://ilay.org/yann/articles/prologin2005/.


Toute remarque, suggestion ou correction est bienvenue et peut être adressée à Yann LANGLAIS, ilay.org.

Introduction

L'épreuve d'algorithmique des éliminatoires du Prologin est toujours un régal. Pour tous les curieux qui, comme moi sont [beaucoup ?] trop vieux pour participer, c'est l'occasion de redémarrer la machine à penser et de vérifier que les engrenages [diodes ? transistors ?] ne se sont pas trop encrassés et tournent toujours rond.
Au delà du défi, et comme le dit si bien l'accroche du concours, c'est l'occasion de découvrir ou de redécouvrir des terres oubliées.

A l'instar des précédentes éditions, je m'y suis jeté comme un gamin. Mais, cette fois, j'ai décidé de poser sur le papier mes réflexions et de vous inviter à les partager.

logo prologin

Où nous comptons les bits

Enoncé

1. Écrire une fonction qui prend un entier positif en argument (inférieur à 1000) et retourne le nombre d'occurrences du chiffre 1 dans la représentation binaire naturelle de cet entier.


Exemple :
On passe « 42 » à la fonction, elle doit retourner 3, puisqu'en binaire, 42 s'écrit 101010.

Conception

Reçevons-nous vraiment un entier en paramètre? De prime abord, la question peut paraître saugrenue. Cependant, si l'on a un entier, habituellement représenté en décimal, il nous faut obligatoirement le convertir en binaire afin de répondre à la question.
Or, le paramètre que nous reçevons est un entier codé en binaire, l'ordinateur ne comprenant que le codage binaire (hormis le BCD, ou Binary Coded Decimal, utilisé par les bibliothèques de calcul dites à « précision arbitraire »).
Nous recevons donc du binaire et il nous suffit de parcourir une liste de bits. Si le bit courant est 1, il nous faut incrémenter un compteur entier (codé lui aussi en binaire).
En première approximation, l'ordre de l'algorithme ne devrait pas dépasser o(n) où n est le nombre de digits sur lequel est codé l'entier. Le nombre d'itérations ne devrait ainsi pas dépasser 10 (la 10-ième puissance de 2 vaut 1024, qui est supérieur à notre limite de 1000).


Implémentation

Nous avons un très grand nombre de possibilités afin d'implémenter cette recette. Nous pouvons utiliser l'opérateur & binaire, ou encore le reste d'une division entière par 2. Nous pouvons utiliser une variable « filtre » qui sera multipliée par 2 à chaque itération, ou encore diviser par 2 notre entier passé en paramètre (pour peu que celui-ci ne soit pas passé en tant que const).
Afin de faire l'économie d'une variable, je choisis d'utiliser notre paramètre (value).

 
1. J'initialise mon compteur à 0.
2. Tant que value n'est pas nul
   2.1 Je teste si son bit de poids faible est à 1 (ET binaire). 
       2.1.1  Si c'est le cas, alors j'incrémente le compteur.  
   2.2 Je décale les bits de value d'un cran vers la droite
3. je retourne mon compteur.

Voyons ce qui ce passe avec l'exemple fourni par l'énoncé :

    count = 0;                          initialisation de count à 0
    value = 42  --> 101010              value vaut 101010
    value & 1   --> 0                   le premier bit est-il à 1 ? non.
    value >>= 1 --> 010101              on décale vers la droite d'1 bit
    value & 1   --> 1                   le premier bit est il à 1 ? oui, 
        ==> count <-- 1                 alors on incrémente count 

    ...

Voici l'implémentation en C :


/* 
 * Retourne le nombre de bits à 1 dans la représentation binaire 
 * de d'un entier compris entre 0 et 1000, ou -1 si l'entier n'est 
 * pas dans l'intervalle :
 */ 

int prg1(int value) {
    int count = 0;

    /* On vérifie que le paramètre est dans les limites : */
    if (value < 0 || value >= 1000) return -1;

    /* puis on compte les digits à 1 : */
    
    while (value) {
        if (value & 1) count++;
        value >>= 1;
    }
    return count;
}

Discussion

D'une façon générale, il est difficile de simplifier d'avantage ces lignes, tant en terme de trace mémoire que de performances.

Les différentes optimisations possibles de cette fonction sont largement dépendantes de la plateforme, du processeur et du compilateur.

On pourra commencer par déclarer les variables value et count en tant que register. Pour le reste, il faudra effectuer des tests en remplaçant & par % 2 ou encore >>= 1 par /2. Il faudra aussi jouer avec les options de compilation, voire, comparer les différents désassemblages des exécutables générés.

Mais dans tous les cas de figure, les gains de performances resteront assez limités.

Où nous comptons les écarts

Enoncé

2. On vous donne un tableau de N entiers positifs distincts et un entier K, où N et K sont compris entre 1 et 1000. Ecrire une fonction prenant en argument ce tableau et ces entiers et retournant le nombre de couples de nombres qu'il est possible de former en conservant une distance inférieure ou égale à K dans chacun des couples.

Exemple :
On dispose de la liste « 10 1 21 7 16 9 12 18 4 19 » (N = 10), et on donne K = 2.
Alors on peut former les couples suivants : (7,9), (9,10), (10,12), (16,18), (18,19) et (19, 21).
La fonction retourne donc 6.

Conception

Ce second problème requiert le calcul des écarts entre toutes les paires d'entiers. L'ordre de l'algorithme est donc Cn2 = n (n - 1) / 2, soit le cardinal des possibilités du tirage de 2 nombres parmi n, où n est le nombre d'éléments du tableau.


Donc, pour effectuer nos n (n - 1) / 2 tests, on utilisera deux boucles imbriquées. La première, indicée par i, parcourt les n - 1 premiers termes (de 0 à n - 2 et la seconde, indicée par j, parcourt les éléments de i + 1 à n - 1.

Pour tous les couples (i, j) ainsi constitués, on calcule abs(N[i] - N[j]). Si cette valeur est inférieure ou égale à k, alors on incrémente notre compteur.

Implémentation


/*
 * Fonction d'aide retournant la valeur absolue d'un entier :
 */

int abs(int a) {
    if (a < 0)  return -a;
    return a;
}     

/*
 * Retourne le nombre de paires dont l'écart est inférieur ou égal à k 
 * ou -1 si n ou k ne sont pas des valeurs correctes, 
 * ou -2 si N n'est pas défini :
 */ 

int prg2(int n, int *N, int k) {
    int i, j, c = 0;

    /* Vérifie que k et n sont correctes */
    if (k < 1 || k > 1000 || n < 1 || n > 1000) return -1;

    /* Vérifie que le tableau d'entier n'est pas un pointeur nul : */
    if (!N) return -2;

    for (i = 0; i < n - 1; i++)
        for (j = i + 1; j < n; j++)
            if (abs(N[i] - N[j])) c++;

    return c;
}

Discussion

Cette fois-ci encore, il est difficile de simplifier (à moins d'une idée lumineuse de conception). On peut encore jouer avec les directives de compilation, définir les variables locales comme register (au cas où ça ne soit pas fait automatiquement) et définir la fonction abs comme inline.

On pourra aussi utiliser une expression ternaire comme :

#define abs_diff(A, B) ((A) > (B) ? ((A) - (B)) : ((B) - (A)))

Où nous testons la symétrie

Enoncé

3. Ecrire une fonction qui prend en argument une matrice remplie de 0 et de 1 contenant une forme géométrique, et deux entiers L et C qui sont respectivement le nombre de lignes et de colonnes compris entre 1 et 1000 inclus. La fonction devra renvoyer 1 s'il existe un axe de symétrie vertical sur la figure formée par l'ensemble des chiffres 1, 0 sinon.

Exemples :

             0 0 1 1 0 0 
La forme     0 1 1 1 1 0   est symétrique selon l'axe vertical. 
L=3, C=6     0 0 1 1 0 0   Le résultat est donc 1. 

             0 1 0 0 
La forme     1 1 1 0       est aussi symétrique selon l'axe vertical. 
L=3, C=4     1 1 1 0       On retourne 1.

Conception

Des différents algorithmes proposés, celui-ci est le plus difficile à mettre en oeuvre. Commencons par simplifier l'énoncé en considérant le cas d'une matrice possédant un axe de symétrie vertical en son centre.

Déterminer si une matrice comporte un axe de symétrie revient à vérifier si chaque ligne est symétrique, i.e. est un palindrome.

Cette opération est effectuée en parcourant une ligne simultanément par ses deux extrémités jusqu'à son centre en testant l'égalité des élements i et n - i - 1, pour tout i allant de 0 à n - 1 .

Prouver qu'une matrice est symétrique nécessite de tester tous ses composants deux à deux. A contrario, la première rupture de symétrie qui se présentera suffira à prouver que la matrice n'est pas symétrique.

Le « pire » des cas survient donc lorsque la matrice est symétrique car nous devons alors tester toutes les colonnes de toutes les lignes.

Notre algorithme est, en première approximation et dans le pire des cas, de l'ordre de n / 2.


        0 0 1 1 0 0 1 1 0 0
        ^                 ^ a[0] == a[n - 1] ? 

        0 0 1 1 0 0 1 1 0 0
          ^             ^   a[1] == a[n - 2] ?

        0 0 1 1 0 0 1 1 0 0
            ^         ^     a[2] == a[n - 3] ?

        ... jusqu'au centre de la ligne

Nous n'avons cependant pas répondu à la question. En effet, nous avons supposé que l'axe se trouvait au milieu de chaque ligne, ce qui est invalidé par le second exemple. Bien que ce procédé ne soit en général pas une bonne idée, car il vaut mieux prévoir (prévenir) que patcher (guérir), nous pouvons conserver notre première approche et y apporter des corrections.

Il faut ajouter deux corrections de premier ordre à notre démarche :


Le premier point est géré par deux boucles consécutives de recherche du premier et dernier 1 de chaque ligne.

Le second se fait en sauvant la position à droite et à gauche de l'axe de symétrie puis en les comparant aux valeurs pour la ligne suivante.


    0 0 0 0 1 1 0 1 1 0 0  -->    1 1 0 1 1 
    ^           |       ^         ^   |   ^
                                     axe
             

    0 0 0 1 0 1 0 1 0 1 0  -->  1 0 1 0 1 0 1
    ^           |       ^       ^     |     ^
                                     axe

Cette seconde correction nécessite une correction de second ordre (effet secondaire d'une correction de premier ordre). En effet, si une ligne « vide » (i.e. dont toutes les colonnes sont à 0) se présente, il faut s'assurer qu'elle n'influe pas sur la dernière position de l'axe. Comme une ligne vide est neutre vis à vis de la symétrie, le plus simple est d'ignorer purement et simplement et de passer à la ligne suivante.

Nous devons encore nous poser une ultime question : « Est-ce qu'une matrice dont tous les éléments sont nuls possède un axe de symétrie ? »
Ce point n'étant pas déterminé par l'énoncé, j'ai choisi de répondre par l'affirmative.

illustration d'une matrice

Implémentation

/*
 * Retourne 1 si la matrice possède un axe de symétrie, 0, si non,
 * En cas d'erreur, retourne : 
 *  -1 si L ou C hors limite,
 *  -2 si la matrice n'est pas allouée,
 *  -n si la (n - 2)-ième ligne n'est pas allouée. 
 */

int prg3(int L, int C, int **mat) {
    int l, i, j;
    int lasti = -1, lastj = -1;

    /* Test des paramètres L et C : */
    if (L < 1 || L > 1000 || C < 1 || C > 1000) return -1;
    
    /* Test de la matrice d'entrée : */
    if (!mat) return -1;
    
    /* Boucle sur toute les lignes : */
    for (l = 0; l < L; l++) {
        
        /* Test de la ligne en cours : */
        if (!mat[l]) return -(2 + l);

        /* Trouver le 1er 1 à gauche : */
        for (i = 0; i < C && !mat[l][i]; i++);

        /* Si pas de 1, on explore la ligne suivante : */
        if (i == C) continue;
        
        /* Trouver le 1er 1 à droite : */
        for (j = C - 1; j >= i && !mat[l][j]; j--); 

        /* Vérifier la symétrie entre les premiers 1 à droite et à gauche : */ 
        while (i < j) { 

            /* Si rupture de symétrie => retourner 0 : */
            if (mat[l][i] != mat[l][j]) return 0; 

            i++, j--;
        }

        /* Vérifie l'unicité de l'axe de symétrie : */
        if (lasti > -1 && (lasti != i || lastj != j)) 

            /* Axe différent => retour 0 : */
            return 0; 

        /* Sauver la position de l'axe de symétrie : */
        lasti = i, lastj = j;
    }

    /* La matrice est symétrique : */
    return 1;
}

Discussion

Nos corrections ont ajouté des itérations supplémentaires par rapport au problème de base. Le pire des cas est maintenant celui où la matrice est nulle. On parcourt alors toute la matrice à la recherche d'un 1.

Dans le cas d'une matrice symétrique où les premières et dernières colonnes sont à 1, nous retrouvons le pire cas du problème de base avec tout juste n / 2 itérations.

Notons que lasti et lastj ne contiennent pas respectivement la dernière colonne avant et la première colonne après l'axe de symétrie, mais exactement le contraire, ce qui ne fait pour nous aucune différence.

Comme il est écrit plus haut, il est préférable, dans le cas général, d'éviter de répondre à un problème en terme de « patches » d'une solution à un problème plus simple. Ce cas est un bon contre exemple confirmant que le dogme doit s'effacer devant le pragmatisme. Il est, par contre, nécessaire d'être exhaustif dans la prise en compte des effets secondaires que chaque retouche apporte.

Où nous jouons avec la lumière

Nous allons nous arrêter un peu plus longtemps sur ce sujet car il illustre bien les implications de la façon d'apprehender un problème donné sur le code (et ses performances).

Enoncé

4. Pour une rampe de P projecteurs, un éclairagiste a installé quatre interrupteurs ayant un effet différent :

  • L'interrupteur 1 inverse l'état de tous les projecteurs de la rampe.
  • L'interrupteur 2 inverse l'état des projecteurs portant un numéro pair.
  • L'interrupteur 3 inverse l'état des projecteurs portant un numéro impair.
  • L'interrupteur 4 inverse l'état des projecteurs dont le numéro est de la forme 3K + 1, où K est un entier.

Au départ, tous les projecteurs sont éteints. L'éclairagiste facétieux décide de presser un nombre B de boutons au hasard.


Vous devez écrire une fonction qui prend trois arguments :

  • Un entier P (avec 0 < P < 1001) représentant le nombre de projecteurs.
  • Un entier B (avec 0 < B < 100001) représentant le nombre de boutons pressés par l'éclairagiste.
  • Un tableau de taille B contenant des entiers compris entre 1 et 4 qui représentent, dans l'ordre, les interrupteurs que l'éclairagiste a pressés (on identifie le premier projecteur comme le projecteur 1).

Votre fonction doit afficher une chaîne composée de 0 et de 1, de longueur P qui représente l'état final de la rampe de projecteurs après l'intervention de l'éclairagiste : le chiffre 1 représente un projecteur allumé, et le chiffre 0 un projecteur éteint.

Exemple :

Soit P = 4, B = 3, et les états des interrupteurs conformes au tableau : [1, 2, 4] 
On obtient l'ordre suivant :   0000 
                               1111 
                               1010 
On retourne donc le résultat : 0011

Conception

illustration d'une rampe de projecteurs avec 4 boutons

Ce problème peut être abordé sous des angles différents. En premier lieu, nous verrons une approche « physique ». Nous discuterons aussi des différentes possibilités de l'implémenter. Puis nous verrons ce que peuvent nous apporter quelques notions mathématiques de base. Enfin, nous comparerons les différentes approches ainsi que leur efficacicé respective.

Approche « physique »

Nous allons commencer par une approche « physique » en reprenant l'énoncé tel quel. On a p projecteurs et b boutons. Intuitivement, notre algorithme sera de l'ordre de p * b. En effet, l'état de chaque projecteur dépend de la séquence des boutons.

Dans cette hypothèse, on utilise 2 boucles imbriquées. L'une pour les projecteurs, et l'autre pour les boutons. L'ordre d'imbrication influe sur le code. En effet, si la boucle externe se charge de parcourir les projecteurs, on aura toujours au total p * b itérations, mais on pourra afficher l'état des projecteurs en cours de calcul. Si l'on inverse l'ordre des boucles, on pourra ne parcourir que les projecteurs de la suite correspondant au bouton en cours :

Les 4 boutons étant équiprobables, on aura (où p est ne nombre de projecteurs) :

Probabiliténb d'itérations
bouton 11/4p
bouton 21/4p/2
bouton 31/4p/2
bouton 41/4p/3

Le temps moyen (ou nombre d'itérations moyen) par bouton sera donc de l'ordre de :
p . (1/4 + 1/2 . 1/4 + 1/2 . 1/4 + 1/3 * 1/4) ~ 0.58 p
soit en moyenne environ 40% d'itérations en moins par rapport au cas précédent.

Nous aurons au pire p * b itérations. Par contre, cet agencement nous oblige à conserver l'état de tous les projecteurs en permanence et donc à réserver un espace mémoire à cet effet, et, comme nous ne sommes pas certains que la dernière boucle passe par tous les projecteurs, il est nécessaire d'effectuer une boucle supplémentaire dédiée à l'affichage de l'état des projecteurs. Notre pire cas devient donc p * (b + 1). ll sera en moyenne plus rapide que le précédent d'environ 40%, mais consommera un peu plus de mémoire. Nous verrons ces deux approches dans la phase d'implémentation.

Approche « mathématique »

Voyons ce que donne une approche plus « mathématique ». Chaque bouton peut, tout comme notre série de projecteur, être assimilé à une suite. L'activation d'un bouton déclenche une opération xor entre la suite représentant l'état de nos projecteurs et la suite représentative du bouton activé.

Nous avons les suites, qui contrairement à ce qui est stipulé dans l'énoncé, commencent ici à 0 :

On remarque que s0 est l'inverse de s1 et s2, l'inverse de s3.

En jouant avec xor, on voit apparaître certaines propriétés :


Ces propriétés rappellent celle d'une base dont l'opérateur « multiplication » est ici xor.

Cependant, cette base n'est pas complète. Il nous manque tout d'abord l'inverse de s4. Celui-ci s'obtient par l'opération s4 xor s1. On note cet inverse s5 (101101...).

    010010...   s4
xor 111111...   s1
---------------
    101101...   s5

Le fait d'avoir une base est intéressant car nous pourrons peut-être en déduire un certain nombre de propriétés contraignant notre opérateur.

Lorsque l'on effectue l'opération s2 xor s4, on obtient une nouvelle suite (111000...). Nommons la s6. s6 doit aussi avoir un inverse (s6 xor s1), s7 (000111...). Et, là, surprise, notre base est complète! Quels que soient les opérandes, notre opérateur xor donne un résultat appartenant à notre base :

    101010... s2       101010... s2       010010... s4
xor 010010... s4   xor 111000... s6   xor 111000... s6
-------------      -------------       -------------
    111000... s6       010010... s4       101010... s2

Il en va de même avec les suites « négatives »

Notre base est un groupe fini. Et comme l'opérateur xor est commutatif (i xor j = j xor i), ce groupe est abélien.

Ces considérations « mathématiques » ont des implications non-négligeables sur notre problème.
D'une part, comme le groupe est fini et ne contient que 8 éléments, toute combinaison de boutons donnera une de ces 8 suites.
D'autre part, l'existence d'une table de « multiplication » permet de « compiler » la liste des boutons une fois pour toutes pour obtenir directement l'état final de notre rampe de projecteurs.

Voici cette table :

bouton
s0 s1 s2 s3 s4 s5 s6 s7
état s0 s0 s1 s2 s3 s4 s5 s6 s7
s1 s1 s0 s3 s2 s5 s4 s7 s6
s2 s2 s3 s0 s1 s6 s7 s4 s5
s3 s3 s2 s1 s0 s7 s6 s5 s4
s4 s4 s5 s6 s7 s0 s1 s2 s3
s5 s5 s4 s7 s6 s1 s0 s3 s2
s6 s6 s7 s4 s5 s2 s3 s0 s1
s7 s7 s6 s5 s4 s3 s2 s1 s0

L'algorithme qui en découle comporte donc deux parties :

Nous avons toujours deux boucles, mais elles ne sont plus imbriquées. L'ordre se réduit alors à p + b.

Implémentation

Approche physique

Nous allons implémenter les deux types d'imbrications à des fins comparatives. Il n'y a dans les deux cas, aucune difficulté notable.

Boucle externe sur les projecteurs

Pour chaque projecteur, nous initialisons à 0, puis, pour chaque bouton, nous vérifions si le bouton en cours modifie l'état du projecteur. Si c'est le cas, nous inversons l'état du projecteur.

void prg4_1(int p, int b, int *B) {
    int i, j, val;

    /* Boucle externe sur les projecteurs : */
    for (i = 1; i <= p; i++) {

        /* Initialisation du projecteur : */
        val = 0;

        /* Boucle interne sur les boutons : */
        for (j = 0; j < b; j++) 

            /* Est-ce que le bouton modifie l'état du projecteur? : */
            if ( B[j] == 1              ||
                (B[j] == 2 && !(i % 2)) ||
                (B[j] == 3 &&  (i % 2)) ||
                (B[j] == 4 && !((i - 1) % 3)))
            
                /* Change l'état du projecteur : */
                val ^= 1;

        /* Affiche l'état du projecteur : */
        putchar(val + '0');
    }
    putchar('\n');
}

Boucle externe sur les boutons


void prg4_2(int p, int b, int *B) {
    int i, j;

    /* Définition des suite d'après leur premier élément : */
    int start[5] = {0, 1, 2, 1, 1};

    /* et d'après l'incrément pour l'élément suivant : */
    int incr[5]  = {0, 1, 2, 2, 3};

    /* mémoire pour les projecteurs : */
    int prj[1002];

    /* initialise les projecteurs  0 : */
    memset((void *) (prj + 1), 0, p * sizeof(int));

    /* boucle externe sur les boutons : */
    for (j = 0; j < b; j++) {

        /* boucle externe sur les projecteurs : */
        for (i = start[B[j]]; i <= p; i += incr[B[j]]) {

            /* inversion du projecteur : */
            if (prj[i]) prj[i] = 0;
            else        prj[i] = 1;
        }
    }

    /* Affichage des projecteurs : */
    for (i = 1; i <= p; i++) putchar(prj[i] + '0');
    putchar('\n');
}

Approche mathématique

Les deux points fondamentaux de l'implémentation sont le codage de la table de multiplication et de la génération de la suite finale.

La table complète comporte 64 entrées. Cependant, comme nous ne possédons que quatre boutons, nous n'avons besoin que de la moitié des colonnes (s1, s2, s3 et s4), soit 32 entrées (colonnes en jaune sur la table de multiplication). On utilisera un « accumulateur », la variable acc, chargé de contenir le membre gauche de notre opération en cours. Il sert d'index de ligne. L'index de colonne est lui représenté par le numéro du bouton en cours, diminué de 1. Le résultat, table[acc][B[i] - 1] est lui même affecté à acc. Une fois tous les boutons parcourus, acc ne contient rien de moins que le numéro de la suite finale.

L'affichage de la suite finale peut être fait de plusieurs manières. On peut, à partir de la définition mathématique de chaque suite, vérifier si le numéro du projecteur en cours répond aux critères de la suite. L'implémentation nécessite alors d'effectuer des tests. Sur ce point, j'ai opté pour une représentation plus « informatique » : je code le motif minimal commun de chaque suite dans un tableau. Aussi le i-ème élément sera donné par un calcul sur pointeurs. Le motif le plus long est celui des suites s6 et s7 et fait 6 bits. Aussi, le notre i-ème élément est donné par suite[acc][i % 6].

void prg4_3(int p, int b, int *B) {

    /* Table de multiplication : */
    int table[8][4] = {
        {1, 2, 3, 4},
        {0, 3, 2, 5},
        {3, 0, 1, 6},
        {2, 1, 0, 7},
        {5, 6, 7, 0},
        {4, 7, 6, 1}, 
        {7, 4, 5, 2},
        {6, 5, 4, 3} 
    };

    /* Codage du motif des 8 suites : */
    int suite[8][6] = {
        {0, 0, 0, 0, 0, 0},
        {1, 1, 1, 1, 1, 1},
        {1, 0, 1, 0, 1, 0},
        {0, 1, 0, 1, 0, 1}, 
        {0, 1, 0, 0, 1, 0},
        {1, 0, 1, 1, 0, 1},
        {1, 1, 1, 0, 0, 0},
        {0, 0, 0, 1, 1, 1}
    };

    /* Accumulateur à 0 : */
    int acc = 0, i; 

    /* Calcul de la suite */
    for (i = 0; i <  b; i++) acc = table[acc][B[i] - 1]; 

    /* Affichage de la suite de projecteurs : */
    for (i = 1; i <= p; i++) putchar(suite[acc][i % 6] + '0');
    putchar('\n');
}   

Discussion

Un petit test comparatif s'impose. Les trois fonctions ont été incluses dans un même fichier. On génère aléatoirement une séquence de 1000 boutons qui vont opérer sur 1000 projecteurs. Comme les temps sont très petits et pour minimiser l'impact de la charge machine, les fonctions sont appelées 1000 fois d'affilée avec les mêmes paramètres. On chronomètre le temps total de ces 1000 itérations, boucle incluse (pour plus d'informations, consulter les fichiers prg4.c et coverage.c).

Le résultat est pour le moins édifiant :

algorithme Solaris cc Solaris gcc Linux gcc
prg4_1 22.004618 15.226231 19.592074
prg4_2 5.292302 5.481149 4.090236
prg4_3 0.046198 0.083301 0.164511

Conditions de test:
Ce test a été effectué sur plateforme Sun :
SunOS 5.8 Generic_117350-13 sun4u sparc SUNW,Sun-Fire-880 avec cc WS6U2 et gcc 2.95.2.
Sur plateforme Linux :
Fedora 3 2.6.9-1.667 i686 athlon i386 GNU/Linux avec gcc 3.4.2

Les rapports des temps entres les différents algorithmes sur une même plateforme sont assez édifiants.

La différences d'agencement des boucles imbriquées est d'un facteur 4 en moyenne (prg4_2 dépend, comme nous l'avons vu, de la qualité des données).

Ce facteur est déjà loin d'être négligeable. Mais la différence la plus importante provient des différentes approches d'un même problème. Le facteur est dans ce cas de l'ordre de plusieurs dizaines de prg4_2 à prg4_3 et de la centaine de prg4_1 à prg4_3.

Conclusion

Cette épreuve des éliminatoires du Prologin 2005 nous a permis d'entrevoir différentes méthodes de réflexion concernant l'élaboration d'algorithmes.

Nous avons aussi pu observer les effets de quelques unes des approches possibles. Si certains sont minimes, d'autres ont des implications profondes sur les performances.

Comme il n'y a jamais qu'une seule et unique façon de faire les choses, il est bien évident que les « solutions » vues ici ne sont pas forcément les meilleures. Je vous invite donc à me faire part de toutes vos remarques à l'adresse suivante ylanglais@gmail.com. Si celles-ci sont nombreuses et intéressantes, je me ferais une joie de les inclure à ce présent document.

Code source

Voici le code des différents programmes et outils utilisés dans l'article.

Références

Prologin: Le site officiel
Mathématiques: définition d'un groupe
Algorithmique pratique et optimisation de code : La génération de labyrinthes


Cet article est paru dans Login: n°128, mai 2005 Couverture du magazine Login: n°128, mai 2005

Valid HTML 4.01! Valid CSS!