14

The following scenario happened to me several times.

I programmed a algorithm that solves a certain problem. It works fine and finds the correct solutions. Now, I want to have an option to tell the algorithm "write a full explanation of how you got to the solution". My goal is to be able to use the algorithm in online demonstrations, tutorial classes, etc. I still want to have an option to run the algorithm in real time, without the explanations. What is a good design pattern to use?

EXAMPLE: Suppose I implement this method for finding the greatest common divisor. The current implemented method returns the correct answer, but with no explanations. I want to have an option for the method to explain its actions, like:

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.

The output should be returned such that it can be easily displayed both in console and in web-based applications.

What is a good pattern to provide explanations when needed, while not hurting the real-time performance of the algorithm when explanations are not needed?

50

The "pattern" you are looking for is called "logging", just make the logging statements as verbose as you need them. By using a decent logging framework you should be able to switch it on and off at run time, provide different verbosity levels, or tailor the output for different purposes (like web vs. console).

If this has a noteable performance impact (even if logging is switched off) will probably depend on the language, the framework and the number of logging statements you need in the specific case. In compiled languages, if this really becomes a problem, you could provide a compiler switch to build "logging variant" and a "non-logging variant" of your code. However, I heavily recommend against optimizing "just in case", without measuring first.

  • 2
    While they're not something you turn on and off like logging, it feels like comments and self documenting code should at least get an honorable mention in a question about an "algorithm that explains itself". – candied_orange May 11 '16 at 6:15
  • 9
    @CandiedOrange the question specifically asks for an "explanation" with real run-time values included in it. Comments won't help much in that case. – metacubed May 11 '16 at 7:54
  • @metacubed oh come on. I didn't say it was an alternative to logging. Look at the question title and think about the traffic coming through here. – candied_orange May 11 '16 at 8:00
  • 4
    @CandiedOrange: I think the question title is misleading, you are correct it could be interpreted that way, but it is not what the OP is asking for. But I let me correct that, I will edit the title. – Doc Brown May 11 '16 at 10:52
  • 1
    Note that something like treelog is specifically designed to produce output that explains complex computations by producing a complete record of function calls. – Boris the Spider May 11 '16 at 12:23
7

A good pattern is Observer. https://en.wikipedia.org/wiki/Observer_pattern

In your algorithm, at each point where you want to output something, you notify some observer(s). They then decide what to do, be it to output your text on the console, or to send it to the HTML engine/Apache etc.

Depending on your programming language there may be different ways to make it fast. For example, in Java (treat it as pseudocode, for brevity; making it "correct", with getters, setters, is left to the reader):

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

This is slightly verbose, but the check for ==null should be as fast as it can get.

(Note that in the general case, observer would probably be a Vector observers instead to allow for more than one observer; this is of course possible as well and will not lead to more overhead; you can still put in the optimization that you set observers=null instead of having an empty Vector.)

Of course, you'd implement different kinds of observers depending on what you want to achieve. You can also put in timing statistics etc. there, or do other fancy stuff.

5

As a slight improvement to straight logging, create some sort of object that models one execution of the algorithm. Add a "step" to this container object each time your code does something interesting. At the end of the algorithm, log the accumulated steps from the container.

This has a few advantages:

  1. You can log the full execution as one log entry, often useful when there's the possibility of other threads logging stuff in between your algo steps
  2. In my Java version of this class (called simply "Debug"), I don't add strings as log entries, but lambdas that produce strings. These lambdas are only evaluated IF actual logging will take place, i.e. if the Debug object finds that its log level is currently activated. This way, there is no performance overhead of constructing log strings unnecessarily.

EDIT: As commented by others, lambdas have overhead, so you would have to benchmark to ensure this overhead is less than the unnecessary evaluation of code required to construct the log string (log entries are often not simple literals, but involve getting contextual info from participating objects).

  • 2
    There is, of course, the overhead of creating lambdas... – Sergio Tulentsev May 11 '16 at 15:01
  • 1
    Sergio makes light of, but does not fully explain the folly of your logic. The performance overhead of constructing log strings is an order of magnitude lower than the performance overhead of constructing lambdas. You have made a very poor tradeoff here – Kyeotic May 11 '16 at 16:23
  • 2
    @Tyrsius: Do you have a reliable benchmark proving that? (The benchmark you link to is deeply flawed, c.f. stackoverflow.com/questions/504103/…) – meriton May 11 '16 at 21:11
  • 1
    @Tyrsius it all depends on the specific situation. I can also give you a, arguably, more relevant counterexample. You can see that the String version is an order of magnitude slower than the Runnable. This case is more realistic, because in the context of this question you will always want to construct your strings dynamically. This always necessitates creation of Stringbuilder objects, while with the Lambda they will be only created when needed (i.e. when logging is on). – jhyot May 12 '16 at 7:15
  • 1
    Lambdas have overhead, agreed. However, the benchmark posted is completely irrelevant in this context. Logging of algorithms often involve evaluation of other code that would not have been evaluated had the logging been skipped (retrieving contextual information from participating objects, etc.). It is this evaluation that lambdas avoid. But you're right, my answer above does assume that the lambda overhead is less than this overhead, something I have not consistently tested. – Cornel Masson May 12 '16 at 8:35
0

I usually look for the branching, meaning i look for if-statements. Because these indicate that i evaluate a value, that will control the flow of the algorithm. In each such occurance (each condition) i can then log the chosen path, and why it was chosen.

So basically i would log the entry values (initial state), every branch chosen (conditionals) and the values when entering the chosen branch (temp state).

  • 1
    this doesn't even attempt to address the question asked, about not hurting the real-time performance of the algorithm when explanations are not needed – gnat May 11 '16 at 13:02
  • I took the question as more general than that and i answered it on a design level. But if that is a concern, add to the conditional a flag to set if you want to print to log or not. Set this flag as a parameter when launching. – Richard Tyregrim May 11 '16 at 14:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.