Test automatici per algoritmo di differenziazione

5

Stiamo progettando un algoritmo di differenziazione (basato su Longest Common Subsequence) che confronta un testo sorgente e una copia modificata per estrarre il nuovo contenuto (cioè il contenuto che è solo nella copia modificata). Attualmente sto compilando una libreria di dati del test case.

Dobbiamo essere in grado di eseguire test automatici che verificano i casi di test, ma non vogliamo verificarne la precisione. Data la natura euristica del nostro algoritmo, abbiamo bisogno che il nostro test pass / failures sia sfocato. Vogliamo specificare una soglia di sovrapposizione tra il risultato desiderato e il risultato effettivo (cioè il contenuto che viene estratto).

Ho alcuni schizzi nella mia mente su come risolvere questo problema, ma qualcuno ha già fatto questo? Qualcuno ha una guida o idee su come farlo in modo efficace?

    
posta Matthew Rodatus 09.07.2012 - 16:59
fonte

2 risposte

1

Sembra che tu abbia un strong vincolo per produrre una serie corretta di differenze e un obiettivo per produrre un insieme minimo di differenze.

Per verificare il vincolo, devi unire le differenze in uno degli input e vedere se ottieni l'altro input. Fortunatamente, questo è già stato fatto. Tutto quello che devi fare è mostrare le differenze nel formato previsto dalla patch GNU.

Per testare il secondo, devi solo assicurarti che l'output non diventi inaccettabilmente grande. Dato che puoi cambiare il programma in modo che una serie di differenze si riduca mentre un'altra diventa più grande, spetterà a te definire una misura di bontà e una soglia di accettabilità.

    
risposta data 09.07.2012 - 18:09
fonte
1

Come @kevin cline ha sottolineato ci sono due diversi vincoli. Chiamerò questi la precisione e i vincoli di efficienza.

Controllare il vincolo di accuratezza dovrebbe essere semplice. Fondamentalmente, tutto ciò che devi fare è testare che è possibile ricreare i dati originali. Questo dovrebbe essere semplice poiché puoi usare strumenti come Patch come suggerisce kevin.

Ma il vincolo di efficienza è più complicato. Penso che impostare una soglia sia una cattiva idea. Supponiamo che tu imposti le soglie al 10% in meno rispetto alle prestazioni correnti degli algoritmi.

  1. Cosa succede se l'efficienza dell'algoritmo scende dell'1% come risultato di una modifica? I tuoi test non te ne parleranno.
  2. Che cosa succede se l'efficienza dell'algoritmo aumenta dell'1%, noterai?
  3. Che cosa accade se l'algoritmo viene migliorato del 20% e quindi diminuito del 10%, sei ancora ben al di sopra delle soglie iniziali, quindi il test non ti aiuterà.

Il problema è che i vincoli di efficienza non sono una preoccupazione pass / fail. Cercare di forzarlo in un test superato / fallito con una soglia non è una buona idea.

Penso che dovresti trattare questo come il test delle prestazioni. Per ogni revisione, eseguire tutti i test e raccogliere i dati di efficienza. Traccia tutti i dati su un grafico che mostra la variazione dell'efficienza con diverse revisioni. Ogni volta che l'efficienza di una prova diminuisce, invia automaticamente un'e-mail a qualcuno che possa fare una valutazione se sia accettabile o meno.

    
risposta data 09.07.2012 - 19:58
fonte

Leggi altre domande sui tag