Prueba de funciones probabilísticas

Question

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

¿Cómo debo hacerlo?

Answer 1

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

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 ejecute la función suficientes veces para obtener una estadística muestra significativa y verifique las propiedades de sus muestras.

Entonces, para barajar, probablemente desee verificar que la relación entre los elementos tenga una covarianza muy pequeña, que la posición esperada de cada elemento sea N / 2, etc.

Answer 3

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

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

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

Si establece los límites correctamente 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 4

En primer lugar, debe usar una semilla fija para el generador de números aleatorios, o de lo contrario la prueba puede fallar aleatoriamente (es decir, a veces pueden estar en orden - ese es el problema con la aleatoriedad ). 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 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 implementación, en caso de que quiera verla 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 5

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

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

La implementación de Java desde esa 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;
    }
}