Test Funzioni probabilistiche

Question

Ho bisogno di una funzione che restituisca un array in ordine casuale. Voglio assicurarmi che sia casuale, ma non ho idea di come si dovrebbe scrivere i test per garantire che l'array sia davvero casuale. Posso eseguire il codice un paio di volte e vedere se ho la stessa risposta più di una volta. Sebbene le collisioni siano improbabili per array di grandi dimensioni, è altamente probabile che si tratti di piccoli array (ad esempio due elementi).

Come dovrei farlo?

Answer 1

Fondamentalmente il trucco è estrarre la casualità dalla classe che stai testando. Questo ti permetterà di testare la classe iniettando la formula per la casualità dal tuo test che ovviamente non sarebbe affatto casuale.

C# esempio:

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

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

Answer 2

Cedric raccomanda un approccio in cui si esegue la funzione abbastanza volte per ottenere un campione statisticamente significativo e verificare le proprietà di voi campioni.

Così per rimescolamento, che vorreste probabilmente per verificare che il rapporto tra gli elementi hanno molto piccolo covarianza, che la posizione prevista di ogni elemento è N/2, ecc

Answer 3

Prima di tutto si dovrebbe usare un seme fisso per il generatore di numeri casuali, o altrimenti il ​​test potrebbe fallire casualmente (ad esempio a volte potrebbero essere in ordine - that's the problem with randomness). Quindi è possibile eseguire alcuni semplici controlli, ad esempio che i valori non siano in ordine e che su ogni corsa i valori siano diversi.

Ecco un esempio di test che ho scritto per la mia implementazione 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)); 
     } 
    } 
} 

Ecco l'attuazione, nel caso in cui si vuole vedere anche:

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

Altri articoli hanno raccomandato di utilizzare un seme fisso per il generatore di numeri casuali, beffardo il generatore di numeri casuali. Questi sono ottimi consigli e li seguo spesso. A volte, tuttavia, metterò alla prova la casualità.

Dato un array di destinazione che si desidera compilare in modo casuale da un array di origine, considerare quanto segue. Carica la matrice sorgente con interi consecutivi. Crea un terzo array chiamato 'sum' e caricalo con zeri. Ora popola a caso il bersaglio e poi aggiungi ciascun elemento del bersaglio all'elemento di somma corrispondente. Fatelo altre migliaia di volte. Se la distribuzione è davvero casuale, le somme dovrebbero essere tutte approssimativamente uguali. È possibile eseguire una semplice stima < + < + delta su ogni elemento dell'array somma.

Si può anche fare un mean e stdev degli elementi dell'array sum e fare anche un confronto delta di essi.

Se si impostano i limiti corretti e si eseguono iterazioni sufficienti, ciò sarà sufficiente. Potresti essere tentato di pensare che possa darti un falso negativo, ma se imposti correttamente i limiti sarà più probabile che un raggio cosmico modifichi l'esecuzione del programma.

Answer 5

Non c'è bisogno di testare la casualità - questo è già implicito nella scelta dell'algoritmo e del generatore di numeri casuali.Utilizzare l'algoritmo di mescolamento Fisher-Yates/Knuth:

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

L'implementazione Java da quella pagina di 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; 
    } 
}