Come fare TDD per qualcosa con molte permutazioni?

15

Quando si crea un sistema come un'intelligenza artificiale, che può percorrere molti percorsi diversi molto velocemente o in realtà un algoritmo con diversi input, il set di risultati possibile può contenere un numero elevato di permutazioni.

Quale approccio si dovrebbe adottare per utilizzare TDD quando si crea un sistema che produce molte, molte diverse permutazioni dei risultati?

    
posta Nicole 21.10.2011 - 06:05
fonte

5 risposte

7

Adottare un approccio più pratico a risposta di pdr . TDD è interamente basato sulla progettazione del software piuttosto che sul testing. Usi i test unitari per verificare il tuo lavoro mentre prosegui.

Quindi su un livello di test unitario è necessario progettare le unità in modo che possano essere testate in modo completamente deterministico. Puoi farlo prendendo tutto ciò che rende l'unità non deterministica (come un generatore di numeri casuali) e allontanandola. Diciamo che abbiamo un esempio ingenuo di un metodo che decide se una mossa è buona o meno:

class Decider {

  public boolean decide(float input, float risk) {

      float inputRand = Math.random();
      if (inputRand > input) {
         float riskRand = Math.random();
      }
      return false;

  }

}

// The usage:
Decider d = new Decider();
d.decide(0.1337f, 0.1337f);

Questo metodo è molto difficile da testare e l'unica cosa che puoi realmente verificare nei test unitari sono i suoi limiti ... ma ciò richiede un sacco di tentativi per arrivare ai limiti. Così, invece, andiamo ad astrarre la parte randomizzante creando un'interfaccia e una classe concreta che racchiuda la funzionalità:

public interface IRandom {

   public float random();

}

public class ConcreteRandom implements IRandom {

   public float random() {
      return Math.random();
   }

}

La classe Decider ora ha bisogno di usare la classe concreta attraverso la sua astrazione, cioè l'interfaccia. Questo modo di fare è chiamato dependency injection (l'esempio sotto è un esempio di iniezione del costruttore, ma puoi farlo anche con un setter):

class Decider {

  IRandom irandom;

  public Decider(IRandom irandom) { // constructor injection
      this.irandom = irandom;
  }

  public boolean decide(float input, float risk) {

      float inputRand = irandom.random();
      if (inputRand > input) {
         float riskRand = irandom.random();
      }
      return false;

  }

}

// The usage:
Decider d = new Decider(new ConcreteRandom);
d.decide(0.1337f, 0.1337f);

Potresti chiederti perché questo "codice gonfia" è necessario. Bene, per cominciare, ora puoi prendere in giro il comportamento della parte casuale dell'algoritmo perché il Decider ora ha una dipendenza che segue il "contratto" di IRandom s. È possibile utilizzare un framework di simulazione per questo, ma questo esempio è abbastanza semplice da codificare te stesso:

class MockedRandom() implements IRandom {

    public List<Float> floats = new ArrayList<Float>();
    int pos;

   public void addFloat(float f) {
     floats.add(f);
   }

   public float random() {
      float out = floats.get(pos);
      if (pos != floats.size()) {
         pos++;
      }
      return out;
   }

}

La parte migliore è che questo può sostituire completamente l'implementazione concreta "effettiva". Il codice diventa facile da testare in questo modo:

@Before void setUp() {
  MockedRandom mRandom = new MockedRandom();

  Decider decider = new Decider(mRandom);
}

@Test
public void testDecisionWithLowInput_ShouldGiveFalse() {

  mRandom.addFloat(0f);

  assertFalse(decider.decide(0.1337f, 0.1337f));
}

@Test
public void testDecisionWithHighInputRandButLowRiskRand_ShouldGiveFalse() {

  mRandom.addFloat(1f);
  mRandom.addFloat(0f);

  assertFalse(decider.decide(0.1337f, 0.1337f));
}

@Test
public void testDecisionWithHighInputRandAndHighRiskRand_ShouldGiveTrue() {

  mRandom.addFloat(1f);
  mRandom.addFloat(1f);

  assertTrue(decider.decide(0.1337f, 0.1337f));
}

Spero che questo ti dia le idee su come progettare la tua applicazione in modo che le permutazioni possano essere forzate in modo da poter testare tutti i casi limite e quant'altro.

    
risposta data 21.10.2011 - 10:05
fonte
3

Il TDD rigoroso tende ad abbattere un po 'per sistemi più complessi, ma ciò non importa troppo in termini pratici - una volta superato l'isolamento di singoli input, scegli alcuni casi di test che forniscono una copertura ragionevole e usa quelli.

Ciò richiede una certa conoscenza di ciò che l'implementazione sarà utile, ma è più una preoccupazione teorica - è altamente improbabile che si stia costruendo un'IA specificata in dettaglio da utenti non tecnici. È nella stessa categoria dei test di passaggio da hardcoding ai casi di test: ufficialmente il test è la specifica e l'implementazione è corretta e la soluzione più rapida possibile, ma in realtà non accade mai.

    
risposta data 21.10.2011 - 06:21
fonte
2

TDD non parla di testing, ma di design.

Lungi dal cadere a pezzi con la complessità, eccelle in queste circostanze. Ti guiderà a considerare il problema più grande in parti più piccole, il che porterà a un design migliore.

Non cercare di testare ogni permutazione del tuo algoritmo. Costruisci un test dopo l'altro, scrivi il codice più semplice per fare in modo che il test funzioni, finché non hai le basi coperte. Dovresti vedere cosa intendo per rompere il problema perché sarai incoraggiato a simulare parti del problema mentre collaudi altre parti, per evitare di dover scrivere 10 miliardi di test per 10 miliardi di permutazioni.

Modifica: volevo aggiungere un esempio, ma non avevo tempo prima.

Consideriamo un algoritmo di ordinamento sul posto. Potremmo andare avanti e scrivere test che coprono la parte superiore dell'array, la parte inferiore dell'array e ogni sorta di strane combinazioni nel mezzo. Per ognuno, dovremmo costruire una serie completa di un qualche tipo di oggetto. Ciò richiederebbe tempo.

Oppure potremmo affrontare il problema in quattro parti:

  1. Attraversa l'array.
  2. Confronta gli elementi selezionati.
  3. Cambia elementi.
  4. Coordinare i tre precedenti.

Il primo è l'unica parte complicata del problema ma, estraendolo dal resto, lo hai reso molto, molto più semplice.

Il secondo è quasi certamente gestito dall'oggetto stesso, almeno facoltativamente, in molti framework tipizzati static ci sarà un'interfaccia per mostrare se tale funzionalità è implementata. Quindi non è necessario testarlo.

Il terzo è incredibilmente facile da testare.

Il quarto tratta solo due puntatori, chiede alla classe trasversale di spostare i puntatori, richiede un confronto e in base al risultato di tale confronto, richiede che gli elementi vengano scambiati. Se hai simulato i primi tre problemi, puoi testarlo molto facilmente.

Come abbiamo portato a un design migliore qui? Diciamo che l'hai mantenuto semplice e implementato un bubble sort. Funziona ma, quando vai in produzione e deve gestire un milione di oggetti, è troppo lento. Tutto quello che devi fare è scrivere nuove funzionalità di attraversamento e scambiarlo. Non devi affrontare la complessità della gestione degli altri tre problemi.

Questo, troverai, è la differenza tra test unitario e TDD. Il tester dell'unità dirà che questo ha reso i test fragili, che se avessi testato input e output semplici, non avresti ora bisogno di scrivere più test per la tua nuova funzionalità. Il TDDer dirà che ho separato le preoccupazioni opportunamente in modo che ogni classe abbia fatto una cosa e una cosa bene.

    
risposta data 21.10.2011 - 09:38
fonte
1

Non è possibile testare ogni permutazione di un calcolo con molte variabili. Ma non è una novità, è sempre stato vero per qualsiasi programma al di sopra della complessità del giocattolo. Il punto delle prove è verificare la proprietà del calcolo. Ad esempio, l'ordinamento di una lista con 1000 numeri richiede un certo sforzo, ma ogni singola soluzione può essere verificata molto facilmente. Ora, anche se ce ne sono 1000! possibili (classi di) input per quel programma e non è possibile testarli tutti, è del tutto sufficiente generare solo 1000 input casualmente e verificare che l'output sia, effettivamente ordinato. Perché? Perché è quasi impossibile scrivere un programma che generi in modo affidabile 1000 vettori generati casualmente senza che sono anche corretti in generale (a meno che tu non lo elimini deliberatamente per manipolare determinati input magici ...)

Ora, in generale le cose sono un po 'più complicate. In realtà, hanno stati bug in cui un mailer non inviava email agli utenti se avevano una "f" nel loro nome utente e il giorno della settimana è venerdì. Ma considero lo spreco di sforzi cercare di anticipare tale stranezza. La tua suite di test dovrebbe garantire costantemente che il sistema faccia ciò che ti aspetti dagli input che ti aspetti. Se fa cose strane in certi casi funky lo noterai abbastanza presto dopo aver provato il primo caso funky, e poi puoi scrivere un test specifico contro quel caso (che di solito coprirà anche un'intera classe di casi simili).

    
risposta data 21.10.2011 - 08:26
fonte
0

Prendi i casi limite più un input casuale.

Per prendere l'esempio di ordinamento:

  • Ordina alcuni elenchi casuali
  • Fai un elenco già ordinato
  • Fai una lista in ordine inverso
  • Fai un elenco quasi in ordine

Se funziona velocemente per questi, puoi essere sicuro che funzionerà per tutti gli input.

    
risposta data 21.10.2011 - 09:36
fonte

Leggi altre domande sui tag