Pattern per algoritmo che fornisce una spiegazione di come arriva a una soluzione quando necessario

Question

Pattern per algoritmo che fornisce una spiegazione di come arriva a una soluzione quando necessario

#1 da (50 voti)
#2 da (7 voti)
#3 da (5 voti)
#4 da (0 voti)

14

Il seguente scenario mi è successo diverse volte.

Ho programmato un algoritmo che risolve un certo problema. Funziona bene e trova le soluzioni corrette. Ora, voglio avere un'opzione per dire all'algoritmo "scrivi una spiegazione completa di come sei arrivato alla soluzione". Il mio obiettivo è essere in grado di utilizzare l'algoritmo in dimostrazioni online, lezioni di tutorial, ecc. Voglio comunque avere un'opzione per eseguire l'algoritmo in tempo reale, senza le spiegazioni. Qual è un buon modello di design da usare?

ESEMPIO: Supponiamo di implementare questo metodo per trovare il massimo comun divisore . Il metodo attualmente implementato restituisce la risposta corretta, ma senza spiegazioni. Voglio avere un'opzione per il metodo per spiegare le sue azioni, come:

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.

L'output dovrebbe essere restituito in modo tale che possa essere facilmente visualizzato sia in console sia in applicazioni basate sul web.

Qual è un buon schema per fornire spiegazioni quando necessario, senza danneggiare le prestazioni in tempo reale dell'algoritmo quando le spiegazioni non sono necessarie?

design-patterns algorithms

posta Erel Segal-Halevi 11.05.2016 - 07:36

fonte

4 risposte

Leggi altre domande sui tag design-patterns algorithms

Come gestire i metodi che sono stati aggiunti per i sottotipi nel contesto del polimorfismo? Sta creando gli oggetti che ritieni di aver bisogno di essere ok in un primo test in TDD

score 50 · Answer 1

Il "pattern" che stai cercando è chiamato "logging", basta rendere verbose le istruzioni di logging quante ne servono. Utilizzando un framework di registrazione decente si dovrebbe essere in grado di accenderlo e spegnerlo in fase di esecuzione, fornire diversi livelli di dettaglio o personalizzare l'output per scopi diversi (come web o console).

Se questo ha un impatto notevole sulle prestazioni (anche se la registrazione è disattivata) dipenderà probabilmente dalla lingua, dalla struttura e dal numero di istruzioni di registrazione necessarie nel caso specifico. Nei linguaggi compilati, se questo diventa davvero un problema, è possibile fornire un commutatore per compilare "variante di registrazione" e una "variante non di registrazione" del codice. Tuttavia, consiglio vivamente di non ottimizzare "solo nel caso", senza prima misurare.

score 7 · Answer 2

Un buon modello è Observer. link

Nel tuo algoritmo, in ogni punto in cui vuoi produrre qualcosa, devi avvisare alcuni osservatori. Decidono quindi cosa fare, che sia per emettere il testo sulla console o per inviarlo al motore HTML / Apache, ecc.

A seconda del tuo linguaggio di programmazione ci possono essere diversi modi per renderlo veloce. Ad esempio, in Java (trattalo come pseudocodice, per brevità, rendendolo "corretto", con getter, setter, è lasciato al lettore):

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

Questo è un po 'prolisso, ma il controllo per ==null dovrebbe essere il più veloce possibile.

(Si noti che nel caso generale, observer sarebbe probabilmente un Vector observers invece di consentire più di un osservatore, anche questo è ovviamente possibile e non comporterà ulteriori overhead; l'ottimizzazione che hai impostato observers=null invece di avere un Vector vuoto.)

Naturalmente, dovrai implementare diversi tipi di osservatori a seconda di ciò che desideri ottenere. Puoi anche inserire statistiche temporali, ecc. O fare altre cose di fantasia.

score 5 · Answer 3

Come lieve miglioramento della registrazione diretta, crea una sorta di oggetto che modella un'esecuzione dell'algoritmo. Aggiungi un "passaggio" a questo oggetto contenitore ogni volta che il tuo codice fa qualcosa di interessante. Alla fine dell'algoritmo, registra i passaggi accumulati dal contenitore.

Questo ha alcuni vantaggi:

Puoi registrare l'intera esecuzione come una voce di log, spesso utile quando c'è la possibilità che altri thread registrino elementi tra i tuoi passi di algo
Nella mia versione Java di questa classe (chiamata semplicemente "Debug"), non aggiungo stringhe come voci di registro, ma lambdas che producono stringhe. Questi lambda vengono valutati solo se si verificherà la registrazione effettiva, ovvero se l'oggetto Debug rileva che il suo livello di registro è attualmente attivato. In questo modo, non ci sono overhead delle prestazioni nella costruzione di stringhe di log inutilmente.

EDIT: come commentato da altri, lambda ha overhead, quindi dovresti fare un benchmark per assicurarti che questo overhead sia inferiore alla valutazione non necessaria del codice richiesto per costruire la stringa di log (le voci di log spesso non sono semplici letterali, ma richiedono di ottenere informazioni contestuali da oggetti partecipanti).

score 0 · Answer 4

Di solito cerco la ramificazione, cioè cerco le if-statement. Perché questi indicano che valuto un valore, che controllerà il flusso dell'algoritmo. In ciascuna di queste situazioni (ogni condizione) posso quindi registrare il percorso scelto e perché è stato scelto.

Quindi fondamentalmente registrerei i valori di entrata (stato iniziale), ogni ramo scelto (condizionali) e i valori quando si entra nel ramo scelto (stato temporaneo).