https://stackoverflow.com/questions/641318
-
22-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
배열을 무작위 순서로 반환하는 함수가 필요합니다. 나는 그것이 무작위인지 확인하고 싶지만 배열이 실제로 무작위인지 확인하기 위해 테스트를 작성하는 방법을 모르겠습니다. 코드를 여러 번 실행하고 동일한 답변이 두 번 이상 있는지 확인할 수 있습니다. 큰 배열의 경우 충돌이 가능하지 않지만 작은 배열 (예 : 두 요소)의 경우 가능성이 높습니다.
어떻게해야합니까?
해결책
기본적으로 트릭은 테스트중인 클래스에서 임의성을 추출하는 것입니다. 이렇게하면 테스트에서 무작위성에 대한 공식을 주입하여 물론 무작위가 아닌 클래스를 테스트 할 수 있습니다.
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));
다른 팁
세드릭 통계적으로 유의 한 샘플을 얻고 샘플의 특성을 확인할 수있는 기능을 충분히 실행하는 접근법을 권장합니다.
따라서 셔플 링의 경우 요소 간의 관계가 매우 작은 공분산을 가지고 있으며 각 요소의 예상 위치가 N/2 등을 확인하고 싶을 것입니다.
다른 기사는 임의 번호 생성기에 고정 된 시드를 사용하여 임의의 숫자 생성기를 조롱하는 것이 좋습니다. 이것들은 좋은 권장 사항이며, 종종 그들을 따릅니다. 그러나 때로는 무작위성을 대신 테스트 할 것입니다.
소스 배열에서 무작위로 채우려는 대상 배열이 주어지면 다음을 고려하십시오. 연속 정수로 소스 배열을로드하십시오. 'sum'이라는 세 번째 배열을 만들고 0으로로드하십시오. 이제 대상을 무작위로 채우고 대상의 각 요소를 해당 합의 요소에 추가하십시오. 더 천 번 더하십시오. 분포가 실제로 무작위 인 경우 합은 모두 거의 동일해야합니다. 합계 배열의 각 요소에 대해 간단한 -delta <예상 < +델타 비교를 수행 할 수 있습니다.
또한 합계 배열의 요소를 평균하고 stdev로 수행하고 델타 비교도 수행 할 수 있습니다.
한계를 올바르게 설정하고 충분한 반복을 수행하면 충분히 충분합니다. 당신은 그것이 당신에게 잘못된 부정적인 것을 줄 수 있다고 생각하는 유혹을받을 수도 있지만, 한계를 올바르게 설정하면 우주 광선이 프로그램의 실행을 바꿀 가능성이 높습니다.
우선 임의의 숫자 생성기에 고정 된 씨앗을 사용해야합니다. 그렇지 않으면 테스트가 무작위로 실패 할 수 있습니다 (즉, 때로는 순서대로있을 수 있습니다. 그것이 무작위성의 문제입니다). 예를 들어 값이 순서대로 정해지지 않고 모든 실행에서 값이 다르기 때문에 간단한 점검을 수행 할 수 있습니다.
다음은 내가 내 자신을 위해 쓴 테스트의 예입니다. 셔플 백 구현.
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;
}
}
임의성을 테스트 할 필요가 없습니다. 이미 알고리즘 및 임의의 숫자 생성기를 선택하는 데 이미 암시 적입니다. Fisher-Yates/Knuth Shuffling 알고리즘을 사용하십시오.
http://en.wikipedia.org/wiki/knuth_shuffle
해당 Wikipedia 페이지에서 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;
}
}
