Prueba Probabilistic Functions

Question

Necesito una función que devuelve una matriz en orden aleatorio. Quiero asegurarme de que sea aleatorio, pero no tengo idea de cómo se escribirán las pruebas para garantizar que la matriz sea aleatoria. Puedo ejecutar el código un montón de veces y ver si tengo la misma respuesta más de una vez. Si bien las colisiones son improbables para matrices grandes, es muy probable que las matrices sean pequeñas (digamos dos elementos).

¿Cómo debo proceder?

Answer 1

Básicamente, el truco es extraer la aleatoriedad de la clase que está probando. Esto le permitirá probar la clase inyectando la fórmula para la aleatoriedad de su prueba que, por supuesto, no sería aleatoria.

ejemplo de C#:

public static List<int> Randomise(List<int> list, Func<bool> randomSwap) 
{ 
    foreach(int i in list) 
    { 
     if (randomSwap) 
     { 
      //swap i and i+1; 
     } 
    } 
    return list; 
} 

Pseudo Uso:

list = Randomise(list, return new Random(0, 1)); 

Answer 2

Cedric recomienda un enfoque en el que ejecuta la función de las veces suficientes para obtener una muestra estadísticamente significativa y verificar las propiedades de ustedes muestras.

Así que para barajar, lo que probablemente desee comprobar que la relación entre los elementos tienen muy pequeña covarianza, que la posición esperada de cada elemento es N/2, etc.

Answer 3

En primer lugar se debe utilizar una semilla fija para el generador de números aleatorios, o de lo contrario la prueba puede fallar al azar (es decir, a veces pueden estar en orden - that's the problem with randomness). Entonces podría hacer algunas comprobaciones simples, por ejemplo, que los valores no están en orden, y que en cada ejecución los valores son diferentes.

Aquí hay un ejemplo de pruebas que escribí para mi propia implementación shuffle bag.

import jdave.Specification; 
import jdave.junit4.JDaveRunner; 
import org.junit.runner.RunWith; 

import java.util.ArrayList; 
import java.util.Arrays; 
import java.util.List; 
import java.util.Random; 

/** 
* @author Esko Luontola 
* @since 25.2.2008 
*/ 
@RunWith(JDaveRunner.class) 
public class ShuffleBagSpec extends Specification<ShuffleBag<?>> { 

    public class AShuffleBagWithOneOfEachValue { 

     private ShuffleBag<Integer> bag; 
     private List<Integer> expectedValues = Arrays.asList(0, 1, 2, 3, 4, 5, 6, 7, 8, 9); 

     public ShuffleBag<Integer> create() { 
      bag = new ShuffleBag<Integer>(new Random(123L)); 
      for (Integer value : expectedValues) { 
       bag.add(value); 
      } 
      return bag; 
     } 

     public void onFirstRunAllValuesAreReturnedOnce() { 
      List<Integer> values = bag.getMany(10); 
      specify(values, does.containExactly(expectedValues)); 
     } 

     public void onFirstRunTheValuesAreInRandomOrder() { 
      List<Integer> values = bag.getMany(10); 
      specify(values.get(0), does.not().equal(0)); 
      specify(values.get(0), does.not().equal(1)); 
      specify(values.get(0), does.not().equal(9)); 
      specify(values, does.not().containInOrder(expectedValues)); 
      specify(values, does.not().containInPartialOrder(1, 2, 3)); 
      specify(values, does.not().containInPartialOrder(4, 5, 6)); 
      specify(values, does.not().containInPartialOrder(7, 8, 9)); 
      specify(values, does.not().containInPartialOrder(3, 2, 1)); 
      specify(values, does.not().containInPartialOrder(6, 5, 4)); 
      specify(values, does.not().containInPartialOrder(9, 8, 7)); 
     } 

     public void onFollowingRunsAllValuesAreReturnedOnce() { 
      List<Integer> run1 = bag.getMany(10); 
      List<Integer> run2 = bag.getMany(10); 
      List<Integer> run3 = bag.getMany(10); 
      specify(run1, does.containExactly(expectedValues)); 
      specify(run2, does.containExactly(expectedValues)); 
      specify(run3, does.containExactly(expectedValues)); 
     } 

     public void onFollowingRunsTheValuesAreInADifferentRandomOrderThanBefore() { 
      List<Integer> run1 = bag.getMany(10); 
      List<Integer> run2 = bag.getMany(10); 
      List<Integer> run3 = bag.getMany(10); 
      specify(run1, does.not().containInOrder(run2)); 
      specify(run1, does.not().containInOrder(run3)); 
      specify(run2, does.not().containInOrder(run3)); 
     } 

     public void valuesAddedDuringARunWillBeIncludedInTheFollowingRun() { 
      List<Integer> additionalValues = Arrays.asList(10, 11, 12, 13, 14, 15); 
      List<Integer> expectedValues2 = new ArrayList<Integer>(); 
      expectedValues2.addAll(expectedValues); 
      expectedValues2.addAll(additionalValues); 

      List<Integer> run1 = bag.getMany(5); 
      for (Integer i : additionalValues) { 
       bag.add(i); 
      } 
      run1.addAll(bag.getMany(5)); 
      List<Integer> run2 = bag.getMany(16); 

      specify(run1, does.containExactly(expectedValues)); 
      specify(run2, does.containExactly(expectedValues2)); 
     } 
    } 

    public class AShuffleBagWithManyOfTheSameValue { 

     private ShuffleBag<Character> bag; 
     private List<Character> expectedValues = Arrays.asList('a', 'b', 'b', 'c', 'c', 'c'); 

     public ShuffleBag<Character> create() { 
      bag = new ShuffleBag<Character>(new Random(123L)); 
      bag.addMany('a', 1); 
      bag.addMany('b', 2); 
      bag.addMany('c', 3); 
      return bag; 
     } 

     public void allValuesAreReturnedTheSpecifiedNumberOfTimes() { 
      List<Character> values = bag.getMany(6); 
      specify(values, does.containExactly(expectedValues)); 
     } 
    } 

    public class AnEmptyShuffleBag { 

     private ShuffleBag<Object> bag; 

     public ShuffleBag<Object> create() { 
      bag = new ShuffleBag<Object>(); 
      return bag; 
     } 

     public void canNotBeUsed() { 
      specify(new jdave.Block() { 
       public void run() throws Throwable { 
        bag.get(); 
       } 
      }, should.raise(IllegalStateException.class)); 
     } 
    } 
} 

Aquí está la aplicación, en caso de que quiera ver también:

import java.util.ArrayList; 
import java.util.List; 
import java.util.Random; 

/** 
* @author Esko Luontola 
* @since 25.2.2008 
*/ 
public class ShuffleBag<T> { 

    private final Random random; 

    /** 
    * Unused values are in the range {@code 0 <= index < cursor}. 
    * Used values are in the range {@code cursor <= index < values.size()}. 
    */ 
    private final List<T> values = new ArrayList<T>(); 
    private int cursor = 0; 

    public ShuffleBag() { 
     this(new Random()); 
    } 

    public ShuffleBag(Random random) { 
     this.random = random; 
    } 

    public void add(T value) { 
     values.add(value); 
    } 

    public T get() { 
     if (values.size() == 0) { 
      throw new IllegalStateException("bag is empty"); 
     } 
     int grab = randomUnused(); 
     T value = values.get(grab); 
     markAsUsed(grab); 
     return value; 
    } 

    private int randomUnused() { 
     if (cursor <= 0) { 
      cursor = values.size(); 
     } 
     return random.nextInt(cursor); 
    } 

    private void markAsUsed(int indexOfUsed) { 
     cursor--; 
     swap(values, indexOfUsed, cursor); 
    } 

    private static <T> void swap(List<T> list, int x, int y) { 
     T tmp = list.get(x); 
     list.set(x, list.get(y)); 
     list.set(y, tmp); 
    } 

    public void addMany(T value, int quantity) { 
     for (int i = 0; i < quantity; i++) { 
      add(value); 
     } 
    } 

    public List<T> getMany(int quantity) { 
     List<T> results = new ArrayList<T>(quantity); 
     for (int i = 0; i < quantity; i++) { 
      results.add(get()); 
     } 
     return results; 
    } 
} 

Answer 4

Otros artículos han recomendado utilizar una semilla fija para el generador de números aleatorios, burlando el generador de números aleatorios. Estas son buenas recomendaciones, y a menudo las sigo. A veces, sin embargo, voy a probar la aleatoriedad en su lugar.

Dada una matriz de destino que desea llenar aleatoriamente desde una matriz de origen, considere hacer lo siguiente. Cargue la matriz fuente con enteros consecutivos. Crea una tercera matriz llamada 'suma' y cárgala con ceros. Ahora rellene aleatoriamente el objetivo y luego agregue cada elemento del objetivo al elemento correspondiente de suma. Haz eso otras mil veces. Si la distribución es realmente aleatoria, entonces las sumas deberían ser aproximadamente las mismas. Puede hacer una simple comparación de delta < < + delta en cada elemento de la matriz de suma.

También puede hacer una media y una stdev de los elementos de la matriz de suma y hacer una comparación delta de ellos también.

Si establece los límites correctos, y realiza suficientes iteraciones, esto será suficiente. Puede sentirse tentado a pensar que puede darle un falso negativo, pero si establece los límites correctamente, será más probable que un rayo cósmico altere la ejecución del programa.

Answer 5

No es necesario probar la aleatoriedad, eso ya está implícito en su elección de algoritmo y generador de números aleatorios.Utilizar el algoritmo de barajar Fisher-Yates/Knuth:

http://en.wikipedia.org/wiki/Knuth_shuffle

La aplicación Java desde la página de Wikipedia:

public static void shuffle(int[] array) 
{ 
    Random rng = new Random();  // java.util.Random. 
    int n = array.length;   // The number of items left to shuffle (loop invariant). 
    while (n > 1) 
    { 
     n--;       // n is now the last pertinent index 
     int k = rng.nextInt(n + 1); // 0 <= k <= n. 
     // Simple swap of variables 
     int tmp = array[k]; 
     array[k] = array[n]; 
     array[n] = tmp; 
    } 
}