Тест вероятностных функций

Question

Мне нужна функция, которая возвращает массив в случайном порядке. Я хочу убедиться, что он случайный, но я понятия не имею, как можно написать тесты, чтобы убедиться, что массив действительно случайный. Я могу запустить код несколько раз и посмотреть, получу ли я один и тот же ответ более одного раза. В то время как столкновения маловероятны для больших массивов, высока вероятность для маленьких массивов (скажем, двух элементов).

Как мне это сделать?

Answer 1

Седрик рекомендует подход, при котором вы запускаете функцию достаточное количество раз, чтобы получить статистически значимый образец и проверить свойства ваших образцов.

Так что для перестановки вы, вероятно, захотите проверить, что отношения между элементами имеют очень маленькую ковариацию, что ожидаемая позиция каждого элемента равна N / 2 и т. Д.

Answer 2

В других статьях рекомендовалось использовать фиксированное начальное число для генератора случайных чисел, издеваясь над генератором случайных чисел. Это хорошие рекомендации, и я часто следую им. Однако иногда я проверю случайность.

Учитывая целевой массив, который вы хотите заполнить случайным образом из исходного массива, рассмотрите возможность сделать следующее. Загрузите исходный массив последовательными целыми числами. Создайте третий массив с именем sum и загрузите его с нулями. Теперь случайным образом заполните цель, а затем добавьте каждый элемент цели к соответствующему элементу суммы. Сделайте это еще тысячу раз. Если распределение действительно случайное, то все суммы должны быть примерно одинаковыми. Вы можете сделать простое сравнение -delta <ожидается <+ дельта для каждого элемента массива суммы. </p>

Вы также можете указать среднее и стандартное значение элементов массива sum и выполнить их дельта-сравнение.

Если вы установите правильные пределы и сделаете достаточно итераций, этого будет достаточно. У вас может возникнуть соблазн думать, что это может дать ложный отрицательный результат, но если вы правильно установите пределы, космический луч с большей вероятностью изменит исполнение программы.

Answer 3

По сути, трюк состоит в том, чтобы извлечь случайность из класса, который вы тестируете. Это позволит вам проверить класс, введя формулу для случайности из вашего теста, который, конечно, не будет случайным вообще.

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

Псевдоиспользование:

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

Answer 4

Нет необходимости проверять на случайность - это уже подразумевается в вашем выборе алгоритма и генератора случайных чисел. Используйте алгоритм перетасовки Фишера-Йейтса / Кнута:

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

Реализация Java со страницы 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;
    }
}

Answer 5

Прежде всего, вы должны использовать фиксированное начальное число для генератора случайных чисел, иначе тест может случайно провалиться (т. Е. Иногда они могут быть в порядке - , это проблема со случайностью ). Затем вы можете сделать несколько простых проверок, например, что значения не в порядке, и что при каждом запуске значения разные.

Вот пример тестов, которые я написал для моей собственной реализации 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));
        }
    }
}

Вот реализация, на случай, если вы захотите ее увидеть:

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