Patrón para algoritmo que genera una explicación de cómo llega a una solución cuando es necesario

14

El siguiente escenario me sucedió varias veces.

Programé un algoritmo que resuelve un cierto problema. Funciona bien y encuentra las soluciones correctas. Ahora, quiero tener una opción para decirle al algoritmo "escribe una explicación completa de cómo llegaste a la solución". Mi objetivo es poder usar el algoritmo en demostraciones en línea, clases de tutoría, etc. Todavía quiero tener una opción para ejecutar el algoritmo en tiempo real, sin las explicaciones. ¿Cuál es un buen patrón de diseño para usar?

EJEMPLO: Supongamos que implemento este método para encontrar el máximo divisor común . El método implementado actual devuelve la respuesta correcta, pero sin explicaciones. Quiero tener una opción para que el método explique sus acciones, como:

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 salida debe devolverse de modo que pueda mostrarse fácilmente tanto en la consola como en aplicaciones basadas en la web.

¿Cuál es un buen patrón para proporcionar explicaciones cuando sea necesario, sin dañar el rendimiento en tiempo real del algoritmo cuando no se necesitan explicaciones?

Erel Segal-Halevi
fuente

Respuestas:

50

El "patrón" que está buscando se llama "registro", solo haga que las declaraciones de registro sean tan detalladas como las necesite. Al usar un marco de registro decente, debería poder encenderlo y apagarlo en tiempo de ejecución, proporcionar diferentes niveles de verbosidad o adaptar la salida para diferentes propósitos (como web frente a consola).

Si esto tiene un impacto notable en el rendimiento (incluso si el registro está desactivado) probablemente dependerá del idioma, el marco y la cantidad de declaraciones de registro que necesite en el caso específico. En los lenguajes compilados, si esto realmente se convierte en un problema, puede proporcionar un modificador de compilación para construir una "variante de registro" y una "variante de no registro" de su código. Sin embargo, recomiendo no optimizar "por si acaso", sin medir primero.

Doc Brown
fuente
2
Si bien no son algo que se enciende y apaga como iniciar sesión, parece que los comentarios y el código de autodocumentación deberían al menos recibir una mención de honor en una pregunta sobre un "algoritmo que se explica por sí mismo".
candied_orange
99
@CandiedOrange la pregunta específicamente pide una "explicación" con valores de tiempo de ejecución reales incluidos en ella. Los comentarios no ayudarán mucho en ese caso.
metacubado
@metacubed oh vamos. No dije que era una alternativa al registro. Mire el título de la pregunta y piense en el tráfico que viene por aquí.
candied_orange
44
@CandiedOrange: Creo que el título de la pregunta es engañoso, tienes razón, podría interpretarse de esa manera, pero no es lo que el OP está pidiendo. Pero me dejo corregir eso, editaré el título.
Doc Brown
1
Tenga en cuenta que algo como treelog está específicamente diseñado para producir resultados que explican cálculos complejos al producir un registro completo de llamadas a funciones.
Boris the Spider
7

Un buen patrón es el observador. https://en.wikipedia.org/wiki/Observer_pattern

En su algoritmo, en cada punto donde desea generar algo, notifica a algunos observadores. Luego deciden qué hacer, ya sea para generar su texto en la consola, o enviarlo al motor HTML / Apache, etc.

Dependiendo de su lenguaje de programación, puede haber diferentes formas de acelerarlo. Por ejemplo, en Java (trátelo como pseudocódigo, por brevedad; dejarlo al lector "correcto", con getters, setters):

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

Esto es un poco detallado, pero la verificación ==nulldebe ser lo más rápida posible.

(Tenga en cuenta que en el caso general, observerprobablemente sería un Vector observerslugar para permitir más de un observador; esto, por supuesto, también es posible y no generará más sobrecarga; aún puede poner la optimización que establezca en observers=nulllugar de tener un vacío Vector)

Por supuesto, implementaría diferentes tipos de observadores dependiendo de lo que quiera lograr. También puede poner estadísticas de tiempo, etc. allí, o hacer otras cosas elegantes.

AnoE
fuente
5

Como una ligera mejora al registro directo, cree algún tipo de objeto que modele una ejecución del algoritmo. Agregue un "paso" a este objeto contenedor cada vez que su código haga algo interesante. Al final del algoritmo, registre los pasos acumulados desde el contenedor.

Esto tiene algunas ventajas:

  1. Puede registrar la ejecución completa como una entrada de registro, a menudo útil cuando existe la posibilidad de que otros hilos registren cosas entre sus pasos de algo
  2. En mi versión Java de esta clase (llamada simplemente "Debug"), no agrego cadenas como entradas de registro, sino lambdas que producen cadenas. Estas lambdas solo se evalúan SI se llevará a cabo un registro real, es decir, si el objeto Debug encuentra que su nivel de registro está activado actualmente. De esta manera, no hay sobrecarga de rendimiento al construir cadenas de registro innecesariamente.

EDITAR: Como comentaron otros, las lambdas tienen sobrecarga, por lo que tendría que comparar para asegurarse de que esta sobrecarga sea menor que la evaluación innecesaria del código requerido para construir la cadena de registro (las entradas de registro a menudo no son simples literales, sino que implican obtener información contextual de objetos participantes).

Cornel Masson
fuente
2
Existe, por supuesto, la sobrecarga de crear lambdas ...
Sergio Tulentsev
1
Sergio se burla, pero no explica completamente la locura de su lógica. La sobrecarga de rendimiento de la construcción de cadenas de registro es un orden de magnitud menor que la sobrecarga de rendimiento de la construcción de lambdas. Has hecho una muy mala compensación aquí
Kyeotic
2
@Tyrsius: ¿Tienes un punto de referencia confiable que lo demuestre? (El punto de referencia al que se vincula es profundamente defectuoso, cf stackoverflow.com/questions/504103/… )
meriton
1
@Tyrsius todo depende de la situación específica. También puedo darle un contraejemplo , posiblemente, más relevante . Puede ver que la versión de String es un orden de magnitud más lenta que Runnable. Este caso es más realista, porque en el contexto de esta pregunta siempre querrá construir sus cadenas dinámicamente. Esto siempre requiere la creación de objetos Stringbuilder, mientras que con el Lambda solo se crearán cuando sea necesario (es decir, cuando el inicio de sesión esté activado).
jhyot
1
Las lambdas tienen gastos generales, de acuerdo. Sin embargo, el punto de referencia publicado es completamente irrelevante en este contexto. El registro de algoritmos a menudo implica la evaluación de otro código que no se habría evaluado si se hubiera omitido el registro (recuperar información contextual de los objetos participantes, etc.). Es esta evaluación la que evitan las lambdas. Pero tienes razón, mi respuesta anterior asume que la sobrecarga lambda es menor que esta sobrecarga, algo que no he probado constantemente.
Cornel Masson
0

Normalmente busco la ramificación, lo que significa que busco declaraciones if. Debido a que estos indican que evalúo un valor, eso controlará el flujo del algoritmo. En cada uno de estos casos (cada condición), puedo registrar el camino elegido y por qué fue elegido.

Entonces, básicamente, registraría los valores de entrada (estado inicial), cada rama elegida (condicionales) y los valores al ingresar a la rama elegida (estado temporal).

Richard Tyregrim
fuente
1
esto ni siquiera intenta responder a la pregunta formulada, sobre no dañar el rendimiento en tiempo real del algoritmo cuando no se necesitan explicaciones
mosquito
Tomé la pregunta como más general que eso y la respondí a nivel de diseño. Pero si eso es una preocupación, agregue al condicional una bandera para establecer si desea imprimir para iniciar sesión o no. Establezca este indicador como parámetro al iniciar.
Richard Tyregrim