Diviser pour régner

Le chapitre précédent a montré une récursivité qui réduit le problème d'un cran à chaque appel : une case de moins, un chiffre de moins, une unité d'exposant de moins. La réduction était réelle mais avare, et le nombre d'appels restait proportionnel à la taille des données. Il existe une autre façon de réduire, qui consiste à couper le problème en deux à chaque étape. Le nombre d'étapes s'effondre alors, et c'est cet effondrement qui fait la valeur de la méthode.

Deux recherches, deux comptes de pas

Soit un relevé de quarante-huit mesures rangées par ordre croissant, et la valeur 209 à retrouver. Elle se trouve en quarante-septième position, mais l'algorithme ne le sait pas. Voici d'abord la recherche la plus directe, qui examine les cases une par une et rend la position trouvée, ou 0 si la valeur est absente, puisqu'aucune case ne porte ce numéro.

Le compteur annonce 98 pas. C'est cohérent, et le détail se relève sur la figure : quarante-sept tours de boucle à deux pas chacun, l'en-tête du Pour et le test Si, le Retourner qui les conclut, la ligne qui range le relevé, et la ligne d'appel franchie deux fois, à l'aller et au retour. L'algorithme est correct et ne demande rien de particulier aux données.

Voici maintenant la même recherche, sur le même tableau et pour la même valeur, menée autrement. À chaque tour, l'algorithme examine la case du milieu de la zone encore possible. Si cette case porte la valeur cherchée, c'est fini. Sinon, la comparaison indique de quel côté continuer, et l'autre moitié est éliminée sans avoir été regardée.

Le compteur annonce 29 pas, pour la même réponse. Le rapport est de trois pour un, et il ne vient pas d'une écriture plus habile : il vient de ce que la boucle n'a tourné que cinq fois. La figure suivante rend ces cinq tours visibles en affichant chaque case examinée.

Les cases examinées sont les positions 24, 36, 42, 45 et 47. Cinq cases sur quarante-huit, et les quarante-trois autres n'ont jamais été lues. La différence entre les deux algorithmes est exactement là : non pas dans la vitesse d'un examen, mais dans le nombre d'examens nécessaires.

Ce que dit l'écart entre 98 et 29. Le compteur ne récompense pas une astuce d'écriture. Un examen coûte même plus cher à la dichotomie : quatre à six pas, pour tester la boucle, calculer le milieu, comparer et déplacer une borne, contre deux pas à la recherche linéaire. Mais la dichotomie fait cinq examens là où l'autre en fait quarante-sept, et c'est le nombre d'examens qui décide : neuf fois moins d'examens, un peu plus du double de travail pour chacun, et au bout du compte trois fois moins de pas. Cet écart n'est pas constant : il grandit avec la taille des données, parce que les deux comptes ne grandissent pas de la même façon. Doubler le tableau ajoute, au pire, quarante-huit examens à la recherche linéaire, et un seul à la dichotomie.

Pourquoi couper en deux change l'ordre de grandeur

La recherche linéaire élimine un candidat par examen. La dichotomie en élimine la moitié. La question intéressante est : combien de fois faut-il diviser par deux pour tomber à un seul candidat ?

La colonne de droite se calcule sans rien dérouler. Un examen divise la zone restante au moins par deux, puisque la case examinée en sort aussi ; deux examens la divisent par quatre, trois par huit, et dix par 1 024, puisque 2 puissance 10 vaut 1 024. Dix examens suffisent donc pour mille candidats ; six suffisaient pour quarante-huit, puisque 2 puissance 6 vaut 64, et il en faut vingt pour un million, trente pour un milliard. Comme mille est presque exactement 2 puissance 10, multiplier la taille du relevé par mille, à partir de la deuxième ligne, n'ajoute que dix examens. Passer d'un million à un milliard d'enregistrements coûte ainsi dix examens de plus à la dichotomie, et neuf cent quatre-vingt-dix-neuf millions à la recherche linéaire. C'est ce genre d'écart qui décide si un traitement est faisable ou non, bien avant toute question de machine ou de langage.

La version récursive dit la même chose plus brièvement, et elle relie ce chapitre au précédent : le cas de base est la zone vide, le cas récursif est une moitié de la zone courante.

Le compteur affiche 31 pas, deux de plus que la version itérative, et la pile monte à six cadres : le programme principal et un par case examinée. La hauteur de pile est ici tout à fait supportable, et pour une raison qui vaut d'être notée : elle suit le nombre de cases examinées, donc le nombre de divisions par deux. Sur ces quarante-huit mesures, aucune recherche n'empile plus de sept appels, et un milliard d'éléments n'en demanderait qu'une trentaine. Une récursivité qui coupe en deux ne fait donc pas déborder la pile, là où une récursivité qui retire une unité la fait déborder dès le millier d'éléments en Python.

Le prix : un tableau déjà trié

Tout ce qui précède repose sur une hypothèse qui n'a jamais été discutée : le tableau est trié. Sans elle, la comparaison t[milieu] < cible ne dit rien sur le côté où continuer, et l'algorithme élimine une moitié au hasard.

Le tableau contient bien la valeur 99, en cinquième position. L'algorithme répond Position : 0, c'est-à-dire « absente », en 32 pas. Et il ne signale rien : il a fait son travail, tiré ses conclusions de comparaisons qui ne voulaient rien dire, et rendu une réponse fausse avec l'assurance d'une réponse juste. Sur le même tableau, il trouverait pourtant 91 du premier coup, parce que cette valeur occupe par hasard la case du milieu : une recherche qui réussit ne prouve donc rien.

Cette remarque déplace le problème plutôt qu'elle ne le résout. Si obtenir un tableau trié coûte plus cher que la recherche linéaire qu'on voulait éviter, l'affaire n'est pas rentable. Elle le devient dès que le même tableau est interrogé plusieurs fois : le tri se paie une fois, les recherches se paient par cinq examens. C'est exactement le raisonnement qui justifie un index dans une base de données. Et c'est la raison pour laquelle le chapitre suivant est consacré aux tris.

Le schéma général

La dichotomie est un cas particulier d'une manière de faire qui porte un nom.

La recherche dichotomique est un cas dégénéré du schéma : elle divise en deux, mais n'en traite qu'une seule moitié, et n'a donc rien à combiner. Elle divise même sans rien découper : elle travaille sur des indices bas et haut, ce qui est le procédé le plus économique, puisqu'il ne recopie aucune donnée. D'autres algorithmes du même genre ont besoin de vraies portions, manipulables comme des tableaux autonomes : le tri fusion, au chapitre suivant, coupe le tableau en deux moitiés qu'il traite séparément avant de les réunir. Il leur faut d'abord un outil qui découpe.

Tranche : extraire une portion de tableau

Trois détails méritent une lecture attentive, car aucun n'est évident avec des indices qui commencent à 1.

La taille vaut b - a + 1, et non b - a. Les deux bornes sont comprises : la tranche de 3 à 7 contient les cases 3, 4, 5, 6 et 7, donc cinq cases. Le + 1 est la trace du fait que la borne de départ compte elle aussi. Oublier ce + 1 réserve une case de moins qu'il n'en faut : la dernière copie vise alors une case qui n'existe pas, et l'algorithme s'arrête sur un indice qui sort du tableau, comme le ferait un langage réel. La tranche d'une seule case demanderait même un tableau de zéro case, refusé dès la réservation.

Le décalage d'indice s'écrit k - a + 1. La case lue est t[k], la case écrite est r[k - a + 1]. Quand k vaut a, l'expression donne 1 : le premier élément de la tranche va bien dans la première case du résultat. Quand k vaut b, elle donne b - a + 1, la dernière case. Écrire r[k - a] donnerait 0 au premier tour, et l'indice 0 provoque un arrêt immédiat, avec le message qui rappelle que le premier élément porte l'indice 1.

Une tranche est une copie, pas une vue. Tranche(t, 1, 3) fabrique un tableau neuf, rempli case par case. Modifier ce résultat ne modifie pas t, et c'est ce qui rend la fonction sûre à employer. En contrepartie, la copie a un coût proportionnel à la taille de la tranche, ce qui la déconseille dans une boucle interne.

Les trois temps, et un contre-exemple

L'exemple suivant utilise les trois temps, avec Tranche pour le premier.

Le cas de base est un tableau d'une seule case, dont le maximum est son unique élément. Le cas récursif coupe en deux, demande le maximum de chaque moitié, et combine en gardant le plus grand des deux. Le déroulement prend 179 pas et empile cinq cadres, pour huit mesures que le parcours par boucle du chapitre sur les tableaux traite en une vingtaine de pas.

Cette figure est donc un contre-exemple utile : ici, diviser pour régner coûte plus cher que la boucle, parce que chaque examen est précédé d'une copie, et que le nombre total d'examens ne diminue pas. Chercher un maximum oblige à regarder toutes les cases, quelle que soit la méthode. La dichotomie ne gagnait pas parce qu'elle coupait en deux, mais parce qu'elle jetait une moitié. C'est la distinction à retenir.

Diviser ne suffit pas. Diviser pour régner ne rapporte que dans deux situations : quand une des portions peut être abandonnée sans être examinée, comme dans la dichotomie, ou quand la combinaison des résultats partiels est nettement moins coûteuse que le traitement direct, comme dans le tri fusion. Découper sans l'un ni l'autre ajoute des copies et des appels à un travail qui n'a pas diminué.

Mettre en pratique

Le coût d'une recherche se prévoit sans rien dérouler : il suffit de compter ce que chaque examen élimine, et ce que chaque appel transmet.