Muster für einen Algorithmus, der eine Erklärung ausgibt, wie er bei Bedarf zu einer Lösung gelangt

Das folgende Szenario ist mir mehrmals passiert.

Ich habe einen Algorithmus programmiert, der ein bestimmtes Problem löst. Es funktioniert gut und findet die richtigen Lösungen. Jetzt möchte ich die Option haben, dem Algorithmus zu sagen, "schreibe eine vollständige Erklärung, wie du zur Lösung gekommen bist". Mein Ziel ist es, den Algorithmus in Online-Demonstrationen, Tutorials usw. verwenden zu können. Ich möchte weiterhin die Option haben, den Algorithmus in Echtzeit ohne die Erklärungen auszuführen. Was ist ein gutes Designmuster?

BEISPIEL: Angenommen, ich implementiere diese Methode, um den größten gemeinsamen Teiler zu finden . Die aktuell implementierte Methode gibt die richtige Antwort zurück, jedoch ohne Erklärungen. Ich möchte eine Option für die Methode haben, um ihre Aktionen zu erklären, wie zum Beispiel:

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.

Die Ausgabe sollte so zurückgegeben werden, dass sie sowohl in der Konsole als auch in webbasierten Anwendungen problemlos angezeigt werden kann.

Was ist ein gutes Muster, um bei Bedarf Erklärungen bereitzustellen, ohne die Echtzeitleistung des Algorithmus zu beeinträchtigen, wenn Erklärungen nicht benötigt werden?

Das "Muster", nach dem Sie suchen, heißt "Protokollierung". Machen Sie die Protokollierungsanweisungen so ausführlich, wie Sie sie benötigen. Wenn Sie ein vernünftiges Protokollierungsframework verwenden, sollten Sie in der Lage sein, es zur Laufzeit ein- und auszuschalten, verschiedene Ausführlichkeitsstufen bereitzustellen oder die Ausgabe für verschiedene Zwecke anzupassen (z. B. Web oder Konsole).

Ob sich dies merklich auf die Leistung auswirkt (auch wenn die Protokollierung deaktiviert ist), hängt wahrscheinlich von der Sprache, dem Framework und der Anzahl der Protokollierungsanweisungen ab, die Sie im jeweiligen Fall benötigen. Wenn dies in kompilierten Sprachen wirklich zu einem Problem wird, können Sie einen Compiler-Schalter zum Erstellen einer "Protokollierungsvariante" und einer "Nichtprotokollierungsvariante" Ihres Codes bereitstellen. Ich rate jedoch dringend davon ab, "nur für den Fall" zu optimieren, ohne vorher zu messen.

Ein gutes Muster ist Observer. https://en.wikipedia.org/wiki/Observer_pattern

In Ihrem Algorithmus benachrichtigen Sie an jedem Punkt, an dem Sie etwas ausgeben möchten, einen oder mehrere Beobachter. Sie entscheiden dann, was zu tun ist, ob Sie Ihren Text auf der Konsole ausgeben oder ihn an die HTML-Engine / Apache usw. senden möchten.

Abhängig von Ihrer Programmiersprache kann es verschiedene Möglichkeiten geben, diese zu beschleunigen. Zum Beispiel in Java (behandeln Sie es der Kürze halber als Pseudocode; es "korrekt" zu machen, mit Gettern, Setzern, bleibt dem Leser überlassen):

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();

Dies ist etwas ausführlich, aber der Check für ==nullsollte so schnell wie möglich sein.

(Beachten Sie, dass im allgemeinen Fall observerwahrscheinlich Vector observersstattdessen mehr als ein Beobachter zugelassen wird. Dies ist natürlich auch möglich und führt nicht zu mehr Aufwand. Sie können weiterhin die von Ihnen festgelegte Optimierung verwenden, observers=nullanstatt eine zu haben leer Vector.)

Natürlich würden Sie verschiedene Arten von Beobachtern implementieren, je nachdem, was Sie erreichen möchten. Sie können dort auch Timing-Statistiken usw. eingeben oder andere ausgefallene Dinge tun.

Erstellen Sie als leichte Verbesserung der geraden Protokollierung eine Art Objekt, das eine Ausführung des Algorithmus modelliert. Fügen Sie diesem Containerobjekt jedes Mal einen "Schritt" hinzu, wenn Ihr Code etwas Interessantes tut. Protokollieren Sie am Ende des Algorithmus die akkumulierten Schritte aus dem Container.

Dies hat einige Vorteile:

1. Sie können die vollständige Ausführung als eine protokollieren Protokolleintrag protokollieren. Dies ist häufig hilfreich, wenn andere Threads zwischen Ihren Algo-Schritten Daten protokollieren
2. In meiner Java-Version dieser Klasse (einfach "Debug" genannt) füge ich keine Zeichenfolgen als Protokolleinträge hinzu, sondern Lambdas , die Zeichenfolgen erzeugen. Diese Lambdas werden nur ausgewertet, wenn die eigentliche Protokollierung stattfindet, dh wenn das Debug-Objekt feststellt, dass seine Protokollierungsstufe derzeit aktiviert ist. Auf diese Weise entsteht kein unnötiger Leistungsaufwand beim Erstellen von Protokollzeichenfolgen.

BEARBEITEN: Wie von anderen kommentiert, haben Lambdas Overhead, so dass Sie einen Benchmark durchführen müssen, um sicherzustellen, dass dieser Overhead geringer ist als die unnötige Auswertung des Codes, der zum Erstellen der Protokollzeichenfolge erforderlich ist (Protokolleinträge sind oft keine einfachen Literale, sondern erfordern das Abrufen von Kontextinformationen von beteiligte Objekte).

Normalerweise suche ich nach der Verzweigung, was bedeutet, dass ich nach if-Anweisungen suche. Weil diese anzeigen, dass ich einen Wert auswerte, der den Fluss des Algorithmus steuert. In jedem solchen Fall (jeder Bedingung) kann ich dann den gewählten Pfad und den Grund für die Wahl protokollieren.

Im Grunde genommen würde ich also die Eingabewerte (Anfangszustand), jeden ausgewählten Zweig (Bedingungen) und die Werte beim Eingeben des ausgewählten Zweigs (temporärer Zustand) protokollieren.