Patrón para el algoritmo que da 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 problema determinado. Funciona bien y encuentra las soluciones correctas. Ahora, quiero tener una opción para decirle al algoritmo "escriba una explicación completa de cómo llegó a la solución". Mi objetivo es poder usar el algoritmo en demostraciones en línea, clases tutoriales, etc. Todavía quiero tener una opción para ejecutar el algoritmo en tiempo real, sin las explicaciones. ¿Qué es un buen patrón de diseño para usar?

EJEMPLO: Supongamos que implemento este método para encontrar el mayor 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.

El resultado debe devolverse de manera que se pueda visualizar fácilmente tanto en la consola como en aplicaciones basadas en web.

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

    
pregunta Erel Segal-Halevi 11.05.2016 - 07:36
fuente

4 respuestas

50

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

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

    
respondido por el Doc Brown 11.05.2016 - 07:59
fuente
7

Un buen patrón es el observador. enlace

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

Dependiendo de su lenguaje de programación, puede haber diferentes maneras de hacerlo rápido. Por ejemplo, en Java (trátelo como pseudocódigo, por brevedad; hacer que sea "correcto", con captadores, definidores, se deja al lector):

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 comprobación de ==null debería ser lo más rápida posible.

(Tenga en cuenta que en el caso general, observer probablemente sería Vector observers en lugar de permitir más de un observador; por supuesto, esto también es posible y no conllevará más sobrecarga; aún puede ingresar la optimización que estableció observers=null en lugar de tener un Vector vacío.)

Por supuesto, implementarías diferentes tipos de observadores dependiendo de lo que quieras lograr. También puedes poner estadísticas de tiempo, etc., o hacer otras cosas sofisticadas.

    
respondido por el AnoE 11.05.2016 - 15:43
fuente
5

Como una ligera mejora en el 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 del 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 subprocesos ingresen cosas entre los pasos de algo
  2. En mi versión Java de esta clase (llamada simplemente "Depurar"), no agrego cadenas como entradas de registro, sino lambdas que producen cadenas. Estos lambdas solo se evalúan SI se realizará el registro real, es decir, si el objeto Depurar encuentra que su nivel de registro está activado actualmente. De esta manera, no hay una sobrecarga de rendimiento al construir cadenas de registro innecesariamente.

EDITAR: Como comentaron otros, los lambdas tienen una sobrecarga, por lo que tendría que realizar una prueba comparativa 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 del registro a menudo no son literales simples, pero implican obtener Información contextual de los objetos participantes).

    
respondido por el Cornel Masson 11.05.2016 - 14:24
fuente
0

Generalmente busco la ramificación, lo que significa que busco sentencias if. Debido a que estos indican que evalúo un valor, eso controlará el flujo del algoritmo. En cada una de esas situaciones (cada condición) puedo registrar la ruta elegida y por qué se eligió.

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

    
respondido por el Richard Tyregrim 11.05.2016 - 14:03
fuente

Lea otras preguntas en las etiquetas