Test probabilistische Funktionen

Question

Ich brauche eine Funktion, die ein Array in zufälliger Reihenfolge zurückgibt. Ich möchte sicherstellen, dass es randomish ist, aber ich habe keine Ahnung, wie man über das Schreiben der Tests gehen würde, um sicherzustellen, dass das Array wirklich zufällig ist. Ich kann den Code ein paar Mal laufen und sehen, ob ich die gleiche Antwort mehr als einmal haben. Während Kollisionen unwahrscheinlich, dass für große Arrays sind, ist es sehr wahrscheinlich für kleinen Arrays (etwa zwei Elemente).

Wie soll ich vorgehen?

Answer 1

Grundsätzlich ist der Trick ist, die Zufälligkeit aus der Klasse extrahieren Sie testen. Dies ermöglicht es Ihnen, die Klasse zu testen, indem Sie die Formel für die Zufälligkeit von Ihrem Test Injektion, die natürlich überhaupt nicht zufällig sein würde.

C # Beispiel:

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 Verbrauch:

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

Answer 2

Cedric empfiehlt einen Ansatz, bei dem Sie die Funktion oft genug laufen eine statistisch zu erhalten und signifikante Stichprobe überprüfen Sie die Eigenschaften von Ihnen Proben.

Also für schlurfend, dann würden Sie wahrscheinlich wollen, um zu überprüfen, dass die Beziehung zwischen den Elementen sehr kleine Kovarianz, dass die erwartete Position jedes Elements ist N / 2, etc.

Answer 3

Weitere Artikel haben unter Verwendung eines festen Samen für den Zufallszahlengenerator empfohlen, den Zufallszahlengenerator spöttisch. Dies sind feine Empfehlungen, und ich folge ihnen oft. Manchmal jedoch, werde ich die Zufälligkeit testen, statt.

ein Ziel-Arrays, die Sie zufällig aus einer Quelle Array auffüllen möchten sollten Sie die folgenden tun. Legen Sie das Quellenarray mit aufeinanderfolgenden ganzen Zahlen. Erstellen Sie eine dritte Array namens ‚Summe‘ und laden Sie es mit Nullen. Jetzt zufällig das Ziel füllen und dann jedes Element des Ziels zu dem entsprechenden Elemente der Summe addieren. Tun Sie das weitere tausend Mal. Wenn die Verteilung wirklich zufällig ist, dann sollten die Summen alle in etwa gleich sein. Sie können eine einfache -delta tun

Sie können auch einen mittleren und stdev der Elemente des Summenarrays tun und einen Delta-Vergleich von ihnen tun.

Wenn Sie die Grenzen richtig eingestellt, und genug Wiederholungen tun, wird dies gut ausreichen. Vielleicht haben Sie es zu denken, versucht sein, können Sie ein falsch negatives geben, aber wenn man die Grenzen richtig eingestellt wird es wahrscheinlicher sein, dass eine kosmische Strahlen, die Ausführung des Programms zu ändern.

Answer 4

Zu allererst Sie einen festen Samen für den Zufallszahlengenerator verwendet werden sollen, oder auf andere Weise kann der Test nicht zufällig (dh manchmal können sie in Ordnung sein - das ist das Problem mit dem Zufall ). Dann könnten Sie ein paar einfache Kontrollen zu tun, zum Beispiel, dass die Werte nicht in Ordnung sind, und dass auf jedem läuft die Werte unterschiedlich sind.

Hier ist ein Beispiel von Tests, die ich für meine eigene Shuffle Tasche Implementierung.

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

Hier ist die Implementierung, falls Sie es sehen auch:

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

Keine Notwendigkeit für Zufälligkeit zu testen - das ist bereits implizit in Ihrer Wahl des Algorithmus und Zufallszahlengenerators. Verwenden Sie die Fisher-Yates / Knuth Misch-Algorithmus:

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

Die Java-Implementierung von der Wikipedia-Seite:

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