Nos trucs préférés : la recherche binaire

Vous ne pensez peut-être pas qu’il serait possible d’avoir un algorithme d’optimisation favori, mais moi oui. Et si vous êtes versé dans l’art mathématique de l’escalade, vous pourriez être surpris que mon choix n’implique même pas de prendre de dérivées. Cela ne veut pas dire que je n’aime pas la méthode de Newton, parce que je l’aime, mais ce n’est tout simplement pas aussi largement applicable que la bonne vieille recherche binaire. Et c’est certainement un outil que vous devriez également avoir dans votre boîte à outils.

Ceux d’entre vous qui ont dormi pendant le cours de calcul ont probablement déjà les paupières tombantes, alors je vais vous donner un exemple de recherche binaire dans le monde réel. Supposons que vous recadriez une image pour la publier sur Hackaday. Pour trouver la meilleure largeur pour l’image particulière, vous commencez avec un recadrage trop fin et un trop large. Commencez par une estimation initiale à mi-chemin entre les bords. Si cette première estimation est trop large, vous divisez à nouveau la différence entre l’estimation actuelle et la largeur la plus fine. Mis à jour avec cette nouvelle supposition, vous divisez à nouveau les différences.

Mais rendons cela encore plus concret : une image de 1200 pixels de large. Il ne peut pas être plus large que 1200 ou plus fin que 0. Donc, notre première estimation est 600. C’est trop mince, donc nous devinons 800 – à mi-chemin entre 600 et la limite supérieure de 1200. Cela finit par être trop large, donc nous devinons ensuite 700 , à mi-chemin entre 600 et 800. Quelques itérations supplémentaires nous amènent à 650, 675 et 688. Dans ce cas, nous sommes descendus au niveau des pixels assez rapidement, et nous avons terminé. En général, vous pouvez vous arrêter lorsque vous êtes satisfait ou que vous avez atteint n’importe quel objectif de précision.

Ce qui est fantastique avec la recherche binaire, c’est le peu qu’elle exige de vous. Contrairement aux méthodes d’optimisation plus sophistiquées, vous n’avez pas besoin de dérivés. Heck, vous n’avez même pas vraiment besoin d’évaluer la fonction plus précisément que « trop ​​peu, trop », et c’est vraiment utile pour le genre d’exemple de recadrage de photographie Goldilocks-y ci-dessus, mais c’est aussi extrêmement utile dans le monde numérique ainsi que. Les comparateurs prennent exactement ce genre de décisions dans le monde de la tension analogique, et vous avez probablement remarqué le mot « binaire » dans la recherche binaire. Mais la recherche binaire n’est pas seulement utile à l’intérieur du silicium.

Pourquoi ne puis-je pas le battre ?

Cet exemple de recadrage de photographies ci-dessus n’était pas une blague. Je suis cette procédure exacte plusieurs fois par jour. Ou du moins j’essaie. Lorsque j’effectue une recherche binaire comme celle-ci dans ma tête, il est incroyablement difficile de me discipliner pour réduire strictement l’espace de recherche à moitié chaque fois. Mais je devrais probablement.

Mon fils et moi étions en train de calibrer un robot tortue il y a quelques semaines. Fondamentalement, nous devions déterminer le pourcentage magique de PWM qui faisait tourner deux moteurs à courant continu différents à la même vitesse. Cela aurait été une application parfaite de la recherche binaire : elle tournait soit légèrement vers la gauche, soit vers la droite, et nous avions de bonnes valeurs PWM de délimitation pour chaque cas. Mais nous n’arrêtions pas de dire, « ça va seulement un peu vers la gauche » et de faire monter le PWM par petits incréments à chaque fois. Après avoir répété cela cinq fois, il était clair pour moi que nous aurions dû utiliser une recherche binaire.

Pour voir pourquoi vous ne devriez probablement pas tricher lors de vos recherches binaires, imaginez que vous ne connaître rien de plus que l’objectif est entre les valeurs supérieure et inférieure, mais vous avez ceci pressentiment qu’il est plus près du fond. Ainsi, au lieu de choisir le point médian, vous choisissez 10 %. Si vous avez raison, votre prochaine supposition sera à l’intérieur de la plage de 10 % de la plage actuelle, ce qui est génial, mais si la cible est même juste un peu plus grande que 10 %, vous envisagez une énorme recherche place au tour suivant. Neuf fois plus grand, pour être exact. Et plus vous êtes incertain quant à savoir où se trouve la vérité, plus vous avez de chances de faire une mauvaise supposition car il y a plus d’espace du côté contre lequel vous pariez.

Le choix du point médian n’est pas arbitraire, et l’intuition ci-dessus peut recevoir une rigueur mathématique (mortis) pour prouver que le point médian est optimal lorsque vous n’avez pas d’informations supplémentaires, mais en même temps, il est incroyablement difficile pour nous, les humains, de résister au jeu. Prenez mon fils avec les PWM – il savait il était vraiment proche. Mais ce qu’il ne savait pas, c’était A quelle distance. Les humains se fixent sur la valeur actuelle. On « ancre », dans les termes des négociations.

Une partie de la raison pour laquelle j’aime la recherche binaire est que cette discipline aide à vaincre ce biais décisionnel humain. Mais l’autre raison pour laquelle j’aime la recherche binaire est la facilité avec laquelle elle est implémentée dans le silicium.

Pas seulement un Lifehack

Ceux d’entre vous qui sont plus portés sur les logiciels ont probablement déjà un profond amour pour les arbres de recherche binaires, mais je suis un gars du matériel. Les convertisseurs analogique-numérique (CAN) de mes microcontrôleurs préférés utilisent tous la recherche binaire sous le capot. Ils partent du principe que la tension qu’ils numérisent se situe entre GND et VCC.

En interne, la tension d’entrée est stockée sur un condensateur échantillonneur-bloqueur qui est connecté à un comparateur. L’autre entrée du comparateur prend la sortie, ironiquement, d’un convertisseur numérique-analogique (DAC). Ce DAC commence avec la tension médiane, VCC/2et le comparateur indique si l’entrée est supérieure ou inférieure.

Avec un DAC 10 bits, vous pouvez le faire dix fois, ce qui vous donne un résultat ADC de dix bits. La partie la plus cool est que la valeur binaire sur l’ADC tombe juste hors du processus. Le premier choix est le bit le plus significatif, et ainsi de suite. Si vous souhaitez voir le circuit en action, consultez [Mitsuru Yamada]de démonstrateur basé sur IC. Pour en savoir plus sur les ADC en général, regardez la vidéo de Bil Herd.

Vingt questions c’est trop

C’est pourquoi la recherche binaire est l’une de mes choses préférées. C’est un outil-slash-algorithme que j’utilise plusieurs fois par jour, et c’est ce qui sous-tend les ADC. Chaque étape vous donne essentiellement un peu plus de résolution, donc dans de nombreuses situations réelles, vous ne ferez probablement pas plus de 12 étapes environ. Choisissez un nombre entre 0 et 1 000 et je le devinerai en dix essais.

Comme le montre mon exemple de photo-recadrage, vous n’avez même pas besoin d’avoir une fonction objective calculable, juste la possibilité de dire « plus grand » ou « plus petit ». Et là où vous avez une fonction objective, la charge de calcul est exceptionnellement légère.

Bien sûr, il y a un moment et un endroit pour des routines d’optimisation plus compliquées – il existe des branches entières de la science basées sur le raffinement de ce piège à souris particulier – mais vous n’exécutez pas de recuit simulé dans votre tête, ni ne l’implémentez dans du silicium brut. La beauté de la recherche binaire est que c’est aussi l’algorithme le plus simple qui puisse fonctionner, et il fonctionne merveilleusement bien pour des problèmes simples. Résoudre des problèmes simples me fait simplement sourire.