¿Cómo hacer TDD para algo con muchas permutaciones?

15

Al crear un sistema como un AI, que puede tomar muchas rutas diferentes muy rápidamente, o en realidad cualquier algoritmo que tenga varias entradas diferentes, el posible conjunto de resultados puede contener una gran cantidad de permutaciones.

¿Qué enfoque se debe tomar para usar TDD cuando se crea un sistema que genera muchas, muchas diferentes permutaciones de resultados?

    
pregunta Nicole 21.10.2011 - 06:05
fuente

5 respuestas

7

Adoptando un enfoque más práctico para respuesta del pdr . TDD tiene que ver con el diseño de software en lugar de las pruebas. Utiliza pruebas unitarias para verificar su trabajo a medida que avanza.

Por lo tanto, en un nivel de prueba de unidad necesita diseñar las unidades para que puedan ser probadas de una manera completamente determinista. Puede hacer esto tomando cualquier cosa que haga que la unidad no sea determinista (como un generador de números aleatorios) y abstraiga eso. Digamos que tenemos un ejemplo ingenuo de un método que decide si un movimiento es bueno o no:

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

Este método es muy difícil de probar y lo único que realmente se puede verificar en las pruebas unitarias son sus límites ... pero eso requiere muchos intentos para llegar a los límites. Entonces, en lugar de eso, abstraemos la parte aleatoria creando una interfaz y una clase concreta que envuelva la funcionalidad:

public interface IRandom {

   public float random();

}

public class ConcreteRandom implements IRandom {

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

}

La clase Decider ahora necesita usar la clase concreta a través de su abstracción, es decir, la interfaz. Esta forma de hacer las cosas se denomina inyección de dependencia (el siguiente ejemplo es un ejemplo de inyección de constructor, pero también puede hacerlo con un definidor):

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

Puede preguntarse por qué es necesario este "código inflado". Bueno, para empezar, ahora puede burlarse del comportamiento de la parte aleatoria del algoritmo porque el Decider ahora tiene una dependencia que sigue al "contrato" de IRandom s. Puedes usar un marco de burla para esto, pero este ejemplo es lo suficientemente simple como para codificarte:

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 mejor parte es que esto puede reemplazar completamente la implementación concreta "real". El código se vuelve fácil de probar de esta manera:

@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));
}

Espero que esto te dé ideas sobre cómo diseñar tu aplicación para que las permutaciones puedan ser forzadas para que puedas probar todos los casos de borde y todo eso.

    
respondido por el Spoike 21.10.2011 - 10:05
fuente
3

Strict TDD tiende a descomponerse un poco para sistemas más complejos, pero eso no importa demasiado en términos prácticos: una vez que llegue más allá de poder aislar entradas individuales, simplemente seleccione algunos casos de prueba que brinden una cobertura razonable y usar esos.

Esto requiere cierto conocimiento de lo que será la implementación para que funcione bien, pero eso es más una preocupación teórica: es muy poco probable que esté creando una IA que fue especificada en detalle por usuarios no técnicos. Está en la misma categoría que pasar las pruebas mediante codificación en los casos de prueba: oficialmente, la prueba es la especificación y la implementación es correcta y la solución más rápida posible, pero en realidad nunca sucede.

    
respondido por el Tom Clarkson 21.10.2011 - 06:21
fuente
2

TDD no se trata de pruebas, se trata de diseño.

Lejos de derrumbarse por la complejidad, sobresale en estas circunstancias. Lo llevará a considerar el problema mayor en piezas más pequeñas, lo que llevará a un mejor diseño.

No intente probar cada permutación de su algoritmo. Solo construye prueba tras prueba, escribe el código más simple para hacer que la prueba funcione, hasta que tengas tus bases cubiertas. Debería ver a qué me refiero con romper el problema porque se lo alentará a que simule partes del problema mientras prueba otras, para evitar tener que escribir 10 mil millones de pruebas para 10 mil millones de permutaciones.

Editar: quería agregar un ejemplo, pero no tenía tiempo antes.

Consideremos un algoritmo de clasificación en el lugar. Podríamos seguir adelante y escribir pruebas que cubran el extremo superior de la matriz, el extremo inferior de la matriz y todo tipo de combinaciones extrañas en el medio. Para cada uno, tendríamos que construir una matriz completa de algún tipo de objeto. Esto llevaría tiempo.

O podríamos abordar el problema en cuatro partes:

  1. Recorre la matriz.
  2. Comparar elementos seleccionados.
  3. Cambiar elementos.
  4. Coordina los tres anteriores.

La primera es la única parte complicada del problema, pero al abstraerla del resto, la has hecho mucho más simple.

El segundo es casi seguro que el objeto lo maneja, al menos opcionalmente, en muchos marcos de tipo estático, habrá una interfaz para mostrar si se implementa esa funcionalidad. Así que no necesitas probar esto.

El tercero es increíblemente fácil de probar.

El cuarto solo maneja dos punteros, le pide a la clase transversal que mueva los punteros, pide una comparación y, basándose en el resultado de esa comparación, pide que se intercambien los elementos. Si ha fingido los primeros tres problemas, puede probar esto muy fácilmente.

¿Cómo hemos llevado a un mejor diseño aquí? Digamos que lo has mantenido simple e implementado una clasificación de burbuja. Funciona, pero cuando vas a la producción y tienes que manejar un millón de objetos, es demasiado lento. Todo lo que tiene que hacer es escribir una nueva funcionalidad de recorrido e intercambiarla. No tiene que lidiar con la complejidad de manejar los otros tres problemas.

Esto, usted encontrará, es la diferencia entre las pruebas de unidad y TDD. El probador de unidad dirá que esto ha hecho que tus pruebas sean frágiles, que si hubieras probado entradas y salidas simples, ahora no tendrías que escribir más pruebas para tu nueva funcionalidad. El TDDer dirá que he separado las preocupaciones de manera adecuada para que cada clase que tengo haga una cosa y una cosa bien.

    
respondido por el pdr 21.10.2011 - 09:38
fuente
1

No es posible probar cada permutación de un cálculo con muchas variables. Pero eso no es nada nuevo, siempre ha sido cierto para cualquier programa que supere la complejidad de los juguetes. El punto de las pruebas es verificar la propiedad del cálculo. Por ejemplo, ordenar una lista con 1000 números requiere un poco de esfuerzo, pero cualquier solución individual se puede verificar muy fácilmente. Ahora, aunque hay 1000! posibles (clases de) entradas para ese programa y no puede probarlas todas, es completamente suficiente para generar 1000 entradas al azar y verificar que la salida, de hecho, esté ordenada. ¿Por qué? Debido a que es casi imposible escribir un programa que ordene de manera confiable 1000 vectores generados aleatoriamente sin también ser correcto en general (a menos que lo manipules deliberadamente para manipular ciertas entradas mágicas ...)

Ahora, en general las cosas son un poco más complicadas. Realmente han sido errores donde un remitente no enviaría correos electrónicos a los usuarios si tienen una 'f' en su nombre de usuario y el día de la semana es el viernes. Pero considero que fue un esfuerzo inútil intentar anticipar semejante rareza. Su conjunto de pruebas debe proporcionarle una confianza constante de que el sistema hace lo que espera en las entradas que espera. Si hace cosas extravagantes en ciertos casos extraños, lo notará lo suficientemente pronto después de probar el primer caso original, y luego podrá escribir una prueba específicamente contra ese caso (que generalmente también cubrirá una clase completa de casos similares).

    
respondido por el Kilian Foth 21.10.2011 - 08:26
fuente
0

Tome los casos de borde más una entrada aleatoria.

Para tomar el ejemplo de clasificación:

  • Ordenar algunas listas aleatorias
  • tomar una lista que ya está ordenada
  • tomar una lista que está en orden inverso
  • Toma una lista que esté casi ordenada

Si funciona rápido para estos, puede estar seguro de que funcionará para todas las entradas.

    
respondido por el Carra 21.10.2011 - 09:36
fuente

Lea otras preguntas en las etiquetas