Wzorzec dla algorytmu, który wyświetla wyjaśnienie, w jaki sposób trafia do rozwiązania w razie potrzeby

Poniższy scenariusz przytrafił mi się kilka razy.

Zaprogramowałem algorytm, który rozwiązuje pewien problem. Działa dobrze i znajduje właściwe rozwiązania. Teraz chcę mieć możliwość powiedzenia algorytmowi „napisz pełne wyjaśnienie, w jaki sposób dotarłeś do rozwiązania”. Moim celem jest umiejętność korzystania z algorytmu podczas demonstracji online, zajęć instruktażowych itp. Nadal chcę mieć możliwość uruchamiania algorytmu w czasie rzeczywistym, bez wyjaśnień. Jakiego wzorca projektowego należy użyć?

PRZYKŁAD: Załóżmy, że wdrażam tę metodę w celu znalezienia największego wspólnego dzielnika . Aktualnie wdrożona metoda zwraca poprawną odpowiedź, ale bez wyjaśnień. Chcę mieć opcję wyjaśniającą jej metodę, na przykład:

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.

Dane wyjściowe powinny zostać zwrócone, aby można je było łatwo wyświetlić zarówno w konsoli, jak i aplikacjach internetowych.

Jaki jest dobry wzorzec dostarczania wyjaśnień, gdy jest to potrzebne, bez uszczerbku dla wydajności algorytmu w czasie rzeczywistym, gdy wyjaśnienia nie są potrzebne?

„Wzorzec”, którego szukasz, nazywa się „rejestrowaniem”, wystarczy, aby instrukcje rejestrowania były tak szczegółowe, jak potrzebujesz. Korzystając z przyzwoitej struktury rejestrowania, powinieneś być w stanie ją włączać i wyłączać w czasie wykonywania, zapewniać różne poziomy szczegółowości lub dostosowywać dane wyjściowe do różnych celów (np. Web vs. konsola).

Jeśli ma to znaczący wpływ na wydajność (nawet jeśli rejestrowanie jest wyłączone), prawdopodobnie będzie to zależeć od języka, struktury i liczby instrukcji rejestrowania, których potrzebujesz w konkretnym przypadku. W skompilowanych językach, jeśli naprawdę staje się to problemem, możesz podać przełącznik kompilatora, aby zbudować „wariant rejestrowania” i „wariant niezalogowany” kodu. Jednak zdecydowanie odradzam optymalizację „na wszelki wypadek”, bez wcześniejszego pomiaru.

Dobrym wzorem jest Obserwator. https://en.wikipedia.org/wiki/Observer_pattern

W swoim algorytmie, w każdym punkcie, w którym chcesz coś wyprowadzić, powiadamiasz niektórych obserwatorów. Następnie decydują, co zrobić, czy to wysyłać tekst na konsoli, czy wysłać go do silnika HTML / Apache itp.

W zależności od języka programowania mogą istnieć różne sposoby na szybkie. Na przykład w Javie (traktuj to jako pseudokod, dla zwięzłości; uczynienie go „poprawnym”, z getterami, setterami, pozostawia się czytelnikowi):

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

Jest to nieco szczegółowe, ale czekanie ==nullpowinno być tak szybkie, jak to możliwe.

(Zauważ, że w ogólnym przypadku observerprawdopodobnie byłoby Vector observerszamiast tego pozwolić na więcej niż jednego obserwatora; jest to oczywiście również możliwe i nie doprowadzi do większego obciążenia; nadal możesz wprowadzić optymalizację, którą ustawiłeś observers=nullzamiast mieć pusty Vector.)

Oczywiście wdrażasz różne rodzaje obserwatorów w zależności od tego, co chcesz osiągnąć. Możesz także umieścić tam statystyki czasowe itp. Lub zrobić inne wymyślne rzeczy.

Jako niewielką poprawę prostego rejestrowania, stwórz obiekt, który modeluje jedno wykonanie algorytmu. Dodaj „krok” do tego obiektu kontenera za każdym razem, gdy kod zrobi coś interesującego. Na końcu algorytmu zaloguj zakumulowane kroki z kontenera.

Ma to kilka zalet:

1. Możesz zarejestrować pełne wykonanie jako jeden wpis dziennika, często przydatny, gdy istnieje możliwość, że inne wątki rejestrują rzeczy między krokami algo
2. W mojej wersji Java tej klasy (zwanej po prostu „Debugowaniem”) nie dodam ciągów jako wpisów w dzienniku, ale lambdy, które produkują ciągi. Te lambd są oceniane tylko JEŻELI nastąpi rzeczywiste rejestrowanie, tj. Jeśli obiekt debugowania stwierdzi, że jego poziom dziennika jest obecnie aktywowany. W ten sposób nie powstaje narzut związany z niepotrzebnym budowaniem ciągów dziennika.

EDYCJA: Jak skomentowali inni, lambdas mają narzut, więc trzeba by przeprowadzić test porównawczy, aby upewnić się, że ten narzut jest mniejszy niż niepotrzebna ocena kodu wymagana do skonstruowania ciągu dziennika (wpisy w dzienniku często nie są zwykłymi literałami, ale wymagają uzyskania informacji kontekstowych z obiekty uczestniczące).

Zwykle szukam rozgałęzień, co oznacza, że ​​szukam instrukcji if. Ponieważ wskazują one, że oceniam wartość, która będzie kontrolować przepływ algorytmu. Przy każdym takim zdarzeniu (każdy warunek) mogę następnie zapisać wybraną ścieżkę i dlaczego została wybrana.

Więc w zasadzie rejestrowałbym wartości wejściowe (stan początkowy), każdą wybraną gałąź (warunki) i wartości podczas wchodzenia do wybranej gałęzi (stan tymczasowy).