Modèle d'algorithme qui génère une explication de la façon dont il parvient à une solution en cas de besoin

Le scénario suivant m'est arrivé plusieurs fois.

J'ai programmé un algorithme qui résout un certain problème. Cela fonctionne bien et trouve les bonnes solutions. Maintenant, je veux avoir une option pour dire à l'algorithme "écrire une explication complète de la façon dont vous êtes arrivé à la solution". Mon objectif est de pouvoir utiliser l'algorithme dans des démonstrations en ligne, des cours de didacticiel, etc. Je veux toujours avoir une option pour exécuter l'algorithme en temps réel, sans les explications. Quel est un bon modèle de conception à utiliser?

EXEMPLE: Supposons que j'implémente cette méthode pour trouver le plus grand diviseur commun . La méthode implémentée actuelle renvoie la bonne réponse, mais sans explication. Je veux avoir une option pour la méthode pour expliquer ses actions, comme:

Initially, a=6 and b=4. The number of 2-factors, d, is initialized to 0.
a and b are both even, so we divide them by 2 and increment d by 1.
Now, a=3 and b=2.
a is odd but b is even, so we divide b by 2.
Now, a=3 and b=1.
a and b are both odd, so we replace a by (a-b)/2 = 1.
Now, a=1 and b=1.
a=b, so the GCD is a*2^d = 2.

La sortie doit être renvoyée de manière à pouvoir être facilement affichée à la fois dans la console et dans les applications Web.

Quel est un bon modèle pour fournir des explications en cas de besoin, sans nuire aux performances en temps réel de l'algorithme lorsque des explications ne sont pas nécessaires?

Le "modèle" que vous recherchez est appelé "journalisation". Rendez les instructions de journalisation aussi verbeuses que vous en avez besoin. En utilisant un cadre de journalisation décent, vous devriez pouvoir l'activer et le désactiver au moment de l'exécution, fournir différents niveaux de verbosité ou personnaliser la sortie à des fins différentes (comme le Web ou la console).

Si cela a un impact notable sur les performances (même si la journalisation est désactivée), cela dépendra probablement de la langue, du cadre et du nombre d'instructions de journalisation dont vous avez besoin dans le cas spécifique. Dans les langages compilés, si cela devient vraiment un problème, vous pouvez fournir un commutateur de compilation pour construire une "variante de journalisation" et une "variante de non-journalisation" de votre code. Cependant, je déconseille fortement d'optimiser "au cas où", sans mesurer d'abord.

Un bon modèle est Observer. https://en.wikipedia.org/wiki/Observer_pattern

Dans votre algorithme, à chaque point où vous voulez sortir quelque chose, vous informez un ou plusieurs observateurs. Ils décident ensuite quoi faire, que ce soit pour sortir votre texte sur la console, ou pour l'envoyer au moteur HTML / Apache, etc.

Selon votre langage de programmation, il peut y avoir différentes façons de le rendre rapide. Par exemple, en Java (le traiter comme un pseudocode, par souci de concision; le rendre "correct", avec des getters, setters, est laissé au lecteur):

interface AlgoLogObserver {
   public void observe(String message);
}

class AlgorithmXyz {   
   AlgoLogObserver observer = null;
   void runCalculation() {   
       if (observer!=null) { oberserver.observe("Hello"); }
       ...
   }   
}

...
algo = new AlgorithmXyz();
algo.observer = new ConsoleLoggingObserver();  // yes, yes make a 
                                               // setter instead, or use Ruby :-)
algo.runCalculation();

C'est un peu verbeux, mais la vérification ==nulldoit être aussi rapide que possible.

(Notez que dans le cas général, ce observerserait probablement un Vector observersau lieu de permettre plus d'un observateur; cela est bien sûr également possible et ne conduira pas à plus de surcharge; vous pouvez toujours mettre l'optimisation que vous définissez observers=nullau lieu d'avoir un vide Vector.)

Bien sûr, vous implémenteriez différents types d'observateurs en fonction de ce que vous souhaitez réaliser. Vous pouvez également y mettre des statistiques de chronométrage, etc., ou faire d'autres choses fantaisistes.

Pour améliorer légèrement la journalisation directe, créez une sorte d'objet qui modélise une exécution de l'algorithme. Ajoutez une "étape" à cet objet conteneur chaque fois que votre code fait quelque chose d'intéressant. À la fin de l'algorithme, enregistrez les étapes accumulées à partir du conteneur.

Cela présente quelques avantages:

1. Vous pouvez enregistrer l'exécution complète en une seule entrée de journal, souvent utile lorsqu'il existe la possibilité que d'autres threads consignent des éléments entre vos étapes algo
2. Dans ma version Java de cette classe (appelée simplement "Debug"), je n'ajoute pas de chaînes comme entrées de journal, mais des lambdas qui produisent des chaînes. Ces lambdas ne sont évalués que si la journalisation réelle a lieu, c'est-à-dire si l'objet Debug constate que son niveau de journalisation est actuellement activé. De cette façon, il n'y a pas de surcharge de performances pour construire des chaînes de journaux inutilement.

EDIT: Comme l'ont commenté d'autres, les lambdas ont un surdébit, vous devriez donc faire un benchmark pour vous assurer que ce surdébit est inférieur à l'évaluation inutile du code requis pour construire la chaîne de journal (les entrées de journal ne sont souvent pas de simples littéraux, mais impliquent d'obtenir des informations contextuelles à partir de objets participants).

Je recherche généralement la ramification, ce qui signifie que je recherche des instructions if. Parce que ceux-ci indiquent que j'évalue une valeur, cela contrôlera le flux de l'algorithme. Dans chacune de ces occurrences (chaque condition), je peux ensuite consigner le chemin choisi et pourquoi il a été choisi.

Donc, fondamentalement, je consignerais les valeurs d'entrée (état initial), chaque branche choisie (conditionnelles) et les valeurs lors de l'entrée dans la branche choisie (état temporaire).