Conception algorithmique

Un problème qui résiste est presque toujours un problème qu’on n’a pas assez découpé. La méthode est simple : tant qu’une étape vous semble difficile, c’est qu’elle contient plusieurs étapes plus simples. Continuez à couper jusqu’à ce que chaque morceau tienne en une phrase.

Afficher le bulletin d’un élève est vague. Découpons :

1. Calculer la moyenne d’une liste de notes.
2. Trouver la mention qui correspond à une moyenne.
3. Afficher le nom, la moyenne et la mention.

Chaque morceau devient une fonction qui porte son nom. Et le programme principal, lui, se lit comme un résumé du raisonnement :

// Trois sous-problèmes, trois fonctions

fonction moyenneDe(liste)
    si longueur(liste) = 0 alors
        retourne 0
    fin si
    total est un nombre vaut 0
    pour i de 0 à longueur(liste) - 1
        total ajoute liste[i]
    fin pour
    retourne total / longueur(liste)
fin fonction

fonction mentionDe(moy)
    si moy >= 16 alors
        retourne 'Très bien'
    fin si
    si moy >= 14 alors
        retourne 'Bien'
    fin si
    si moy >= 12 alors
        retourne 'Assez bien'
    fin si
    si moy >= 10 alors
        retourne 'Admis'
    fin si
    retourne 'Refusé'
fin fonction

procédure bulletin(eleve, liste)
    moy est un nombre vaut moyenneDe(liste)
    affiche eleve + ' : ' + decimal(moy, 2) + ' -> ' + mentionDe(moy)
fin procédure

// Le programme principal se lit comme un résumé
appelle bulletin('Léa', [12, 15.5, 9])
appelle bulletin('Tom', [17, 16, 18])
appelle bulletin('Inès', [8, 11, 9.5])

Où couper ?

Trois signaux ne trompent pas :

• Vous écrivez deux fois la même chose : c’est une fonction qui demande à naître.
• Vous ne savez pas nommer un morceau : c’est qu’il en fait plusieurs à la fois.
• Un bloc dépasse vingt lignes : il cache au moins deux idées.

À l’inverse, une fonction qui ne sert qu’une fois et tient en une ligne n’apporte souvent rien. Le but n’est pas de découper le plus possible, mais de donner un nom à chaque idée.

Deux programmes peuvent donner le même résultat, l’un en une seconde et l’autre en une heure. Ce qui les sépare n’est presque jamais la vitesse de la machine : c’est le nombre d’opérations que l’algorithme demande. Et ce nombre se compte, sur le papier, avant d’écrire quoi que ce soit.

La bonne question n’est pas combien de temps ça prend ? mais qu’est-ce qui se passe si les données sont dix fois plus nombreuses ? Trois réponses possibles, et elles suffisent à couvrir presque tous les cas :

À part, et précieux : les algorithmes qui coupent en deux à chaque étape. Doubler les données ne coûte qu’une étape de plus. C’est la recherche par dichotomie, qui exige un tableau trié.

// Combien de comparaisons pour trouver une valeur ?

fonction coutLineaire(liste, cherche)
    compteur est un nombre vaut 0
    pour i de 0 à longueur(liste) - 1
        compteur ajoute 1
        si liste[i] = cherche alors
            retourne compteur
        fin si
    fin pour
    retourne compteur
fin fonction

fonction coutDichotomie(liste, cherche)
    compteur est un nombre vaut 0
    bas est un nombre vaut 0
    haut est un nombre vaut longueur(liste) - 1
    milieu est un nombre
    tant que bas <= haut
        milieu vaut arrondi_inferieur((bas + haut) / 2)
        compteur ajoute 1
        si liste[milieu] = cherche alors
            retourne compteur
        sinon si liste[milieu] < cherche alors
            bas vaut milieu + 1
        sinon
            haut vaut milieu - 1
        fin si
    fin tant que
    retourne compteur
fin fonction

nombres est un tableau vaut intervalle(1, 1000)
affiche 'Une à une : ' + coutLineaire(nombres, 1000)      // 1000
affiche 'En coupant en deux : ' + coutDichotomie(nombres, 1000)    // 10

Mille comparaisons contre dix. Et l’écart se creuse : sur un million de valeurs, la recherche simple en demanderait un million, la dichotomie vingt. Pas vingt mille : vingt.

Le bon réflexe

Avec dix valeurs, tout va vite et le choix de l’algorithme n’a aucune importance. C’est quand les données grossissent que la différence apparaît, et en général, on ne s’en rend compte qu’en production. Prenez donc l’habitude de compter les boucles imbriquées : chaque niveau d’imbrication multiplie le coût par la taille des données.