Test des fonctions probabilistes

Question

J'ai besoin d'une fonction qui retourne un tableau dans un ordre aléatoire. Je veux m'assurer que c'est aléatoire, mais je ne sais pas comment on pourrait écrire les tests pour s'assurer que le tableau est vraiment aléatoire. Je peux exécuter le code plusieurs fois et voir si j'ai la même réponse plus d'une fois. Bien que les collisions soient peu probables pour les tableaux de grande taille, il est très probable que celles-ci soient de petite taille (disons deux éléments).

Comment dois-je m'y prendre?

Answer 1

En gros, l’astuce consiste à extraire le caractère aléatoire de la classe que vous testez. Cela vous permettra de tester la classe en injectant la formule du caractère aléatoire de votre test qui, bien entendu, ne le serait pas du tout.

Exemple 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-utilisation:

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

Answer 2

Cedric recommande une approche dans laquelle vous exécutez la fonction suffisamment de fois pour obtenir une analyse statistique. échantillon significatif et vérifiez les propriétés de vos échantillons.

Donc, pour le brassage, vous voudrez probablement vérifier que la relation entre les éléments a une très petite covariance, que la position attendue de chaque élément est N / 2, etc.

Answer 3

D'autres articles ont recommandé d'utiliser une valeur de départ fixe pour le générateur de nombres aléatoires, se moquant du générateur de nombres aléatoires. Ce sont de bonnes recommandations que je suis souvent. Parfois, cependant, je vais plutôt tester le caractère aléatoire.

Étant donné le tableau cible que vous souhaitez renseigner de manière aléatoire à partir d'un tableau source, envisagez les actions suivantes. Chargez le tableau source avec des entiers consécutifs. Créez un troisième tableau appelé 'somme' et chargez-le avec des zéros. Maintenant, peuplez la cible de manière aléatoire, puis ajoutez chaque élément de la cible à l'élément de somme correspondant. Faites-le encore mille fois. Si la distribution est vraiment aléatoire, alors les sommes doivent être à peu près les mêmes. Vous pouvez faire un simple -delta & Lt; attendu < + comparaison delta sur chaque élément du tableau sum.

Vous pouvez également faire une moyenne et une valeur des éléments du tableau sum et en faire une comparaison delta.

Si vous définissez les limites correctement et effectuez suffisamment d'itérations, cela suffira bien. Vous pourriez être tenté de penser que cela peut vous donner un faux négatif, mais si vous définissez les limites correctement, il sera plus probable qu'un rayon cosmique modifie l'exécution du programme.

Answer 4

Tout d’abord, vous devez utiliser une valeur de départ fixe pour le générateur de nombres aléatoires, sinon le test peut échouer de manière aléatoire (c’est-à-dire que parfois ils peuvent être dans l’ordre - c'est le problème du caractère aléatoire ). Vous pouvez ensuite procéder à quelques vérifications simples, par exemple que les valeurs ne sont pas dans l’ordre et que, à chaque exécution, les valeurs sont différentes.

Voici un exemple de tests que j'ai écrits pour ma propre mise en œuvre du 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));
        }
    }
}

Voici l'implémentation, au cas où vous voudriez la voir aussi:

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

Inutile de tester le caractère aléatoire - cela est déjà implicite dans votre choix d'algorithme et de générateur de nombres aléatoires. Utilisez l’algorithme de mélange Fisher-Yates / Knuth:

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

L'implémentation Java de cette page 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;
    }
}