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

Question

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

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

Answer 1

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

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 2

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

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

Answer 3

Прежде всего, вы должны использовать фиксированное семя для генератора случайных чисел, иначе тест может произойти случайным образом (т.е. иногда они могут быть в порядке - that's the problem with randomness). Затем вы можете сделать несколько простых проверок, например, что значения не в порядке, а на каждом прогоне значения разные.

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

Answer 4

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

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

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

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

Answer 5

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

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

Реализация Java с этой страницы Википедии:

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