https://stackoverflow.com/questions/641318
-
22-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
配列をランダムな順序で返す関数が必要です。ランダムであることを確認したいのですが、配列が実際にランダムであることを確認するためのテストをどのように書くかはわかりません。コードを何度も実行して、同じ回答が複数回あるかどうかを確認できます。大きな配列では衝突は起こりそうにありませんが、小さな配列（2つの要素など）では非常に可能性が高くなります。
どうすればいいですか？
解決
基本的には、テストするクラスからランダム性を抽出するのがコツです。 これにより、テストからランダム性の式を注入することでクラスをテストできます。もちろん、まったくランダムではありません。
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));
他のヒント
Cedric は、統計を取得するのに十分な回数、関数を実行するアプローチを推奨しています。重要なサンプルを作成し、サンプルのプロパティを確認します。
シャッフルのために、おそらく要素間の関係の共分散が非常に小さいこと、各要素の予想される位置がN / 2などであることを確認する必要があります。
他の記事では、乱数ジェネレーターの固定シードを使用して、乱数ジェネレーターをモックすることを推奨しています。これらはすばらしい推奨事項であり、私はしばしばそれに従います。ただし、時々、代わりにランダム性をテストします。
ソース配列からランダムに入力するターゲット配列を考えると、次のことを検討してください。ソース配列に連続した整数をロードします。 「sum」という3番目の配列を作成し、ゼロでロードします。ここで、ターゲットにランダムにデータを入力してから、ターゲットの各要素を合計の対応する要素に追加します。それをさらに千回行います。分布が実際にランダムな場合、合計はほぼ同じになるはずです。単純な-delta <！> lt;を実行できます。期待される<！> lt; +合計配列の各要素のデルタ比較。
また、合計配列の要素の平均と標準偏差を行い、それらのデルタ比較を行うこともできます。
制限を適切に設定し、十分な反復を行う場合、これで十分です。偽陰性になる可能性があると思われるかもしれませんが、制限を正しく設定すると、宇宙線がプログラムの実行を変更する可能性が高くなります。
まず、乱数ジェネレーターに固定シードを使用する必要があります。そうしないと、テストがランダムに失敗する場合があります（つまり、順序どおりになることがあります-ランダム性の問題）。次に、いくつかの簡単なチェックを行うことができます。たとえば、値が順番になっていないこと、実行ごとに値が異なることなどです。
これは、私自身のシャッフルバッグの実装用に作成したテストの例です。
>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シャッフルアルゴリズムを使用します。
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;
}
}
所属していません StackOverflow
