اختبار الوظائف الاحتمالية

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

توصي سيدريك هذا النهج حيث تقوم بتشغيل وظيفة مرات كافية للحصول على إحصائيا عينة كبيرة والتحقق من خصائص لك عينات.

وهكذا على سبيل خلط، وكنت ربما تريد أن تحقق من أن العلاقة بين العناصر لها التغاير صغيرة جدا، وهذا الموقف المتوقع من كل عنصر N / 2، وما إلى ذلك.

Answer 3

أوصت مقالات أخرى باستخدام بذرة ثابتة لمولد الأرقام العشوائية، ساخرة من مولد الأرقام العشوائية.هذه توصيات جيدة، وكثيرًا ما أتبعها.ومع ذلك، في بعض الأحيان، سأختبر العشوائية بدلاً من ذلك.

بالنظر إلى المصفوفة المستهدفة التي تريد تعبئتها بشكل عشوائي من مصفوفة مصدر، فكر في القيام بما يلي.قم بتحميل المصفوفة المصدر بأعداد صحيحة متتالية.قم بإنشاء مصفوفة ثالثة تسمى "sum" وقم بتحميلها بالأصفار.الآن قم بملء الهدف بشكل عشوائي ثم قم بإضافة كل عنصر من عناصر الهدف إلى عنصر المجموع المقابل.افعل ذلك ألف مرة أخرى.إذا كان التوزيع عشوائيًا حقًا، فيجب أن تكون جميع المبالغ متساوية تقريبًا.يمكنك إجراء مقارنة -delta < المتوقعة < + delta بسيطة على كل عنصر في مصفوفة المجموع.

يمكنك أيضًا إجراء متوسط ​​وقياسي لعناصر المصفوفة الإجمالية وإجراء مقارنة دلتا لها أيضًا.

إذا قمت بتعيين الحدود بشكل صحيح، وقمت بالتكرار الكافي، فسيكون هذا كافيًا بشكل جيد.قد تميل إلى الاعتقاد بأنه يمكن أن يعطيك نتيجة سلبية كاذبة، ولكن إذا قمت بتعيين الحدود بشكل صحيح، فمن المرجح أن يغير الأشعة الكونية تنفيذ البرنامج.

Answer 4

وقبل كل شيء يجب عليك استخدام البذور ثابت للمولد رقم عشوائي، أو قد تفشل اختبار عشوائيا (أي في بعض الأحيان قد تكون في النظام - <وأ href = "http://dilbert.com/strips/comic / 2001/10/25 / "يختلط =" نوفولو noreferrer "> هذه هي المشكلة مع العشوائية ). ثم هل يمكن أن تفعل بعض الاختبارات البسيطة، على سبيل المثال أن القيم ليست في النظام، وأنه في كل تشغيل قيم مختلفة.

وهنا مثال من الاختبارات التي كتبت عن بلدي خلط تنفيذ حقيبة .

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