परीक्षण संभाव्य कार्य

Question

मुझे एक फ़ंक्शन की आवश्यकता है जो यादृच्छिक क्रम में एक सरणी देता है। मैं यह सुनिश्चित करना चाहता हूं कि यह यादृच्छिक है लेकिन मुझे नहीं पता कि परीक्षण करने के बारे में कोई कैसे होगा, यह सुनिश्चित करने के लिए कि सरणी वास्तव में यादृच्छिक है। मैं कोड को कई गुना चला सकता हूं और देख सकता हूं कि मेरे पास एक ही जवाब एक से अधिक बार है या नहीं। जबकि टक्कर बड़े सरणी के लिए असंभव हैं, यह छोटे सरणी (दो तत्वों का कहना है) के लिए अत्यधिक संभव है।

मुझे इसके बारे में कैसे जाना चाहिए?

Answer 1

मूल रूप से यह चाल उस कक्षा के बाहर यादृच्छिकता निकालने के लिए है जिसे आप परीक्षण कर रहे हैं। यह आपको अपने परीक्षण से यादृच्छिकता के लिए फॉर्मूला इंजेक्शन करके कक्षा का परीक्षण करने की अनुमति देगा जो निश्चित रूप से यादृच्छिक नहीं होगा।

सी # उदाहरण:

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 एक दृष्टिकोण है जहाँ आप एक सांख्यिकीय महत्वपूर्ण नमूना मिलता है और आप के नमूने के गुणों को सत्यापित करने के समारोह के लिए पर्याप्त बार चलाने की सिफारिश की गई।

तो पुथल के लिए, तो आप शायद यह सत्यापित करने के तत्वों के बीच के रिश्ते, बहुत छोटे सहप्रसरण है एन/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' नामक एक तीसरी सरणी बनाएं और इसे शून्य से लोड करें। अब यादृच्छिक रूप से लक्ष्य को पॉप्युलेट करें और फिर लक्ष्य के प्रत्येक तत्व को योग के संबंधित तत्व में जोड़ें। वह एक और हज़ार बार करो। यदि वितरण वास्तव में यादृच्छिक है, तो रकम सभी मोटे तौर पर समान होनी चाहिए। आप एक सरल-डेल्टा < अपेक्षित < + योग सरणी के प्रत्येक तत्व पर डेल्टा तुलना कर सकते हैं।

आप योग सरणी के तत्वों का एक औसत और stdev भी कर सकते हैं और उनमें से एक डेल्टा तुलना भी कर सकते हैं।

यदि आप सीमाएं सही करते हैं, और पर्याप्त पुनरावृत्ति करते हैं, तो यह अच्छी तरह से पर्याप्त होगा। आपको यह सोचने में लुभाना पड़ सकता है कि यह आपको झूठा नकारात्मक दे सकता है, लेकिन यदि आप सीमाओं को सही तरीके से सेट करते हैं तो कार्यक्रम के निष्पादन को बदलने के लिए एक वैश्विक किरण की संभावना अधिक होगी।

Answer 5

यादृच्छिकता के लिए परीक्षण करने की कोई आवश्यकता नहीं है - यह पहले से ही एल्गोरिदम और यादृच्छिक संख्या जनरेटर की आपकी पसंद में निहित है।फिशर-येट्स/नुथ की उथल एल्गोरिथ्म का उपयोग करें:

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

कि विकिपीडिया पृष्ठ से जावा कार्यान्वयन:

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