Padrão para o algoritmo que gera uma explicação de como ele chega a uma solução quando necessário

14

O seguinte cenário aconteceu comigo várias vezes.

Eu programei um algoritmo que resolve um certo problema. Ele funciona bem e encontra as soluções corretas. Agora, eu quero ter uma opção para dizer ao algoritmo "escrever uma explicação completa de como você chegou à solução". Meu objetivo é ser capaz de usar o algoritmo em demonstrações online, aulas de tutorial, etc. Eu ainda quero ter uma opção para executar o algoritmo em tempo real, sem as explicações. O que é um bom padrão de design para usar?

EXEMPLO: Suponha que eu implemente este método para encontrar o maior divisor comum . O método implementado atual retorna a resposta correta, mas sem explicações. Eu quero ter uma opção para o método para explicar suas ações, 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.

A saída deve ser retornada para que possa ser facilmente exibida no console e em aplicativos baseados na web.

Qual é um bom padrão para fornecer explicações quando necessário, sem prejudicar o desempenho em tempo real do algoritmo quando as explicações não são necessárias?

    
por Erel Segal-Halevi 11.05.2016 / 07:36
fonte

4 respostas

50

O "padrão" que você está procurando é chamado de "logging", apenas torne as instruções de log tão detalhadas quanto as necessárias. Usando uma estrutura de registro decente, você deve ser capaz de ativá-lo e desativá-lo em tempo de execução, fornecer diferentes níveis de detalhamento ou adequar a saída para diferentes propósitos (como web vs. console).

Se isso tiver um impacto notável no desempenho (mesmo se o log estiver desativado) provavelmente dependerá do idioma, da estrutura e do número de instruções de log necessárias no caso específico. Em linguagens compiladas, se isso realmente se tornar um problema, você poderia fornecer um switch de compilador para construir "variante de registro" e uma "variante de não registro" do seu código. No entanto, recomendo strongmente contra a otimização "apenas no caso", sem medir primeiro.

    
por 11.05.2016 / 07:59
fonte
7

Um bom padrão é o Observer. link

Em seu algoritmo, em cada ponto em que você deseja gerar algo, você notifica alguns observadores. Eles então decidem o que fazer, seja para enviar seu texto no console ou para enviá-lo para o mecanismo HTML / Apache, etc.

Dependendo da sua linguagem de programação, pode haver maneiras diferentes de torná-lo rápido. Por exemplo, em Java (tratá-lo como pseudocódigo, por brevidade, tornando-o "correto", com getters, setters, é deixado para o leitor):

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

Isso é um pouco detalhado, mas a verificação de ==null deve ser a mais rápida possível.

(Observe que, no caso geral, observer provavelmente seria um Vector observers para permitir mais de um observador; isso também é possível e não levará a mais sobrecarga; você ainda pode colocar a otimização que você definiu observers=null em vez de ter um Vector vazio.)

Claro, você implementaria diferentes tipos de observadores dependendo do que você deseja alcançar. Você também pode colocar estatísticas de tempo etc., ou fazer outras coisas extravagantes.

    
por 11.05.2016 / 15:43
fonte
5

Como uma pequena melhoria no registro direto, crie algum tipo de objeto que modere uma execução do algoritmo. Adicione uma "etapa" a esse objeto contêiner sempre que seu código fizer algo interessante. No final do algoritmo, registre as etapas acumuladas no contêiner.

Isso tem algumas vantagens:

  1. Você pode registrar a execução completa como uma entrada de log, geralmente útil quando há a possibilidade de outros segmentos registrarem coisas entre as etapas do seu algoritmo
  2. Na minha versão Java dessa classe (chamada simplesmente de "Debug"), não adiciono strings como entradas de log, mas lambdas que produzem strings. Esses lambdas são avaliados apenas se o log real ocorrer, ou seja, se o objeto Debug descobrir que seu nível de log está ativado no momento. Dessa forma, não há sobrecarga de desempenho na construção de sequências de logs desnecessariamente.

EDIT: Como comentado por outros, lambdas tem sobrecarga, então você teria que comparar para garantir que essa sobrecarga é menor do que a avaliação desnecessária do código necessário para construir a cadeia de log (entradas de log não são simples literais, mas envolvem informações contextuais dos objetos participantes).

    
por 11.05.2016 / 14:24
fonte
0

Eu geralmente procuro a ramificação, o que significa que procuro declarações if. Porque estes indicam que eu avalio um valor, que irá controlar o fluxo do algoritmo. Em cada uma dessas ocorrências (cada condição), eu posso registrar o caminho escolhido e por que ele foi escolhido.

Então, basicamente eu iria registrar os valores de entrada (estado inicial), cada ramo escolhido (condicionais) e os valores ao entrar no ramo escolhido (estado temp).

    
por 11.05.2016 / 14:03
fonte