Testowanie jednostkowe algorytmów z natury losowych / niedeterministycznych

41

Mój obecny projekt, zwięźle, polega na tworzeniu „zdarzeń losowo możliwych”. Generalnie generuję harmonogram inspekcji. Niektóre z nich opierają się na ścisłych harmonogramach; raz w tygodniu przeprowadzasz kontrolę w piątek o godzinie 10:00. Inne kontrole są „losowe”; istnieją podstawowe konfigurowalne wymagania, takie jak „inspekcja musi odbywać się 3 razy w tygodniu”, „inspekcja musi odbywać się między godzinami 9–21” i „nie powinny być dwie inspekcje w tym samym okresie 8 godzin”, ale niezależnie od ograniczeń skonfigurowanych dla określonego zestawu inspekcji, wynikające z nich daty i godziny nie powinny być przewidywalne.

Testy jednostkowe i TDD, IMO, mają wielką wartość w tym systemie, ponieważ można je wykorzystać do stopniowego budowania go, podczas gdy jego pełny zestaw wymagań jest wciąż niekompletny, i upewnij się, że nie jestem „nadmiernie inżynieryjny”, aby robić rzeczy, które nie daję obecnie wiem, że potrzebuję. Surowe harmonogramy były dla TDD bułką z masłem. Jednak trudno mi zdefiniować, co testuję, pisząc testy dla losowej części systemu. Mogę stwierdzić, że wszystkie czasy generowane przez program planujący muszą mieścić się w ograniczeniach, ale mógłbym zaimplementować algorytm, który przejdzie wszystkie takie testy bez faktycznego czasu bardzo „losowego”. W rzeczywistości tak właśnie się stało; Znalazłem problem, w którym czasy, choć nie do końca dokładnie przewidywalne, mieściły się w niewielkim podzbiorze dopuszczalnych zakresów daty / czasu. Algorytm nadal spełniał wszystkie stwierdzenia, które według mnie mógłbym rozsądnie sformułować, i nie mogłem zaprojektować zautomatyzowanego testu, który zawiódłby w tej sytuacji, ale przejść, gdy otrzyma „bardziej losowe” wyniki. Musiałem wykazać, że problem został rozwiązany przez restrukturyzację niektórych istniejących testów, aby powtórzyć się wiele razy i wizualnie sprawdzić, czy generowane czasy mieszczą się w pełnym dopuszczalnym zakresie.

Czy ktoś ma jakieś wskazówki dotyczące projektowania testów, które powinny oczekiwać zachowania niedeterministycznego?


Dziękujemy wszystkim za sugestie. Głównym opinia wydaje się, że muszę deterministycznego testu w celu uzyskania deterministyczne i powtarzalne wyniki, assertable . Ma sens.

Stworzyłem zestaw testów „piaskownicy”, które zawierają algorytmy kandydujące do procesu ograniczania (proces, w którym tablica bajtów, która może być dowolna, staje się długa między min a maksimum). Następnie uruchamiam ten kod przez pętlę FOR, która daje algorytmowi kilka znanych tablic bajtowych (wartości od 1 do 10 000 000 na początek) i ma algorytm ograniczający do wartości od 1009 do 7919 (używam liczb pierwszych, aby zapewnić algorytm nie przepuściłby jakiegoś nieoczekiwanego GCF między zakresami wejściowym i wyjściowym). Wynikowe ograniczone wartości są zliczane i generowany histogram. Aby „przejść”, wszystkie dane wejściowe muszą zostać odzwierciedlone w histogramie (rozsądek, aby upewnić się, że nie „straciliśmy” żadnego), a różnica między dowolnymi dwoma segmentami w histogramie nie może być większa niż 2 (tak naprawdę powinna wynosić <= 1 , ale bądźcie czujni). Zwycięski algorytm, jeśli taki istnieje, można wyciąć i wkleić bezpośrednio w kodzie produkcyjnym, a także przeprowadzić stały test regresji.

Oto kod:

    private void TestConstraintAlgorithm(int min, int max, Func<byte[], long, long, long> constraintAlgorithm)
    {
        var histogram = new int[max-min+1];
        for (int i = 1; i <= 10000000; i++)
        {
            //This is the stand-in for the PRNG; produces a known byte array
            var buffer = BitConverter.GetBytes((long)i);

            long result = constraintAlgorithm(buffer, min, max);

            histogram[result - min]++;
        }

        var minCount = -1;
        var maxCount = -1;
        var total = 0;
        for (int i = 0; i < histogram.Length; i++)
        {
            Console.WriteLine("{0}: {1}".FormatWith(i + min, histogram[i]));
            if (minCount == -1 || minCount > histogram[i])
                minCount = histogram[i];
            if (maxCount == -1 || maxCount < histogram[i])
                maxCount = histogram[i];
            total += histogram[i];
        }

        Assert.AreEqual(10000000, total);
        Assert.LessOrEqual(maxCount - minCount, 2);
    }

    [Test, Explicit("sandbox, does not test production code")]
    public void TestRandomizerDistributionMSBRejection()
    {
        TestConstraintAlgorithm(1009, 7919, ConstrainByMSBRejection);
    }

    private long ConstrainByMSBRejection(byte[] buffer, long min, long max)
    {
        //Strip the sign bit (if any) off the most significant byte, before converting to long
        buffer[buffer.Length-1] &= 0x7f;
        var orig = BitConverter.ToInt64(buffer, 0);
        var result = orig;
        //Apply a bitmask to the value, removing the MSB on each loop until it falls in the range.
        var mask = long.MaxValue;
        while (result > max - min)
        {
            mask >>= 1;
            result &= mask;
        }
        result += min;

        return result;
    }

    [Test, Explicit("sandbox, does not test production code")]
    public void TestRandomizerDistributionLSBRejection()
    {
        TestConstraintAlgorithm(1009, 7919, ConstrainByLSBRejection);
    }

    private long ConstrainByLSBRejection(byte[] buffer, long min, long max)
    {
        //Strip the sign bit (if any) off the most significant byte, before converting to long
        buffer[buffer.Length - 1] &= 0x7f;
        var orig = BitConverter.ToInt64(buffer, 0);
        var result = orig;

        //Bit-shift the number 1 place to the right until it falls within the range
        while (result > max - min)
            result >>= 1;

        result += min;
        return result;
    }

    [Test, Explicit("sandbox, does not test production code")]
    public void TestRandomizerDistributionModulus()
    {
        TestConstraintAlgorithm(1009, 7919, ConstrainByModulo);
    }

    private long ConstrainByModulo(byte[] buffer, long min, long max)
    {
        buffer[buffer.Length - 1] &= 0x7f;
        var result = BitConverter.ToInt64(buffer, 0);

        //Modulo divide the value by the range to produce a value that falls within it.
        result %= max - min + 1;

        result += min;
        return result;
    }

... a oto wyniki:

wprowadź opis zdjęcia tutaj

Odrzucenie LSB (przesunięcie liczby bitów, aż mieści się w zakresie) było STRASZNE, z bardzo łatwego do wyjaśnienia powodu; dzieląc dowolną liczbę przez 2, aż będzie ona mniejsza niż maksimum, rezygnujesz z niej natychmiast, a dla każdego nietrywialnego zakresu spowoduje to przesunięcie wyników w kierunku górnej jednej trzeciej (jak pokazano w szczegółowych wynikach histogramu ). Takie było dokładnie zachowanie, które widziałem od daty ukończenia; wszystkie czasy były po południu, w bardzo konkretne dni.

Odrzucenie MSB (usuwanie najbardziej znaczącego bitu z liczby pojedynczo, aż znajdzie się w zakresie) jest lepsze, ale znowu, ponieważ odcinasz bardzo duże liczby z każdym bitem, nie jest on równomiernie rozłożony; jest mało prawdopodobne, aby uzyskać liczby w górnym i dolnym końcu, więc otrzymujesz odchylenie w kierunku środkowej trzeciej. Może to przydać się komuś, kto chce „znormalizować” losowe dane w krzywą dzwonową, ale suma dwóch lub więcej mniejszych liczb losowych (podobnych do rzucania kostkami) dałaby bardziej naturalną krzywą. Dla moich celów zawodzi.

Jedynym, który zdał ten test, było ograniczenie przez podział modulo, który również okazał się najszybszy z trzech. Z definicji Modulo będzie wytwarzać możliwie równomierny rozkład, biorąc pod uwagę dostępne dane wejściowe.

KeithS
źródło
2
Tak więc ostatecznie chcesz program, który wygląda na wyjście generatora liczb losowych i decyduje, czy jest losowy? Jak w „5,4,10,31,120,390,2,3,4” było losowe, ale „49, 39, 1, 10, 103,12, 189” nie było?
psr
Nie, ale fajne byłoby unikanie wprowadzania uprzedzeń między faktycznym PRNG a wynikiem końcowym.
KeithS
Wygląda na to, że kpienie z PRNG byłoby w porządku. Nie potrzebujesz rzeczywistych losowych wartości, aby sprawdzić, czy nie zmieniasz wartości. Jeśli masz błąd polegający na wyciskaniu losowych wartości w zbyt mały podzbiór dopuszczalnych zakresów, być może źle podajesz niektóre wartości.
psr
Powinieneś także przetestować kombinacje. Posiadanie w przybliżeniu równych oczekiwanych inspekcji na godzinę nie ochroni przed przypadkiem, w którym, powiedzmy, we wtorek po inspekcji o 11 rano zawsze następuje po południu w czwartek i 10 w piątek.
David Thornley,
To bardziej test samego PRNG; test mechanizmów ograniczających, jak skonstruowano powyżej, zawsze kończyłby się takim testem, ponieważ otrzymuje kompletnie nieprzypadkowy zestaw danych. Zakładając, że mechanizm ograniczenia nie stara się „uporządkować” losowych danych, które nazwałbym „testowaniem zewnętrznych”, co jest czymś, czego nie powinien robić test jednostkowy.
KeithS

Odpowiedzi:

17

Zakładam, że faktycznie chcesz tutaj przetestować to, że biorąc pod uwagę określony zestaw wyników z randomisera, reszta twojej metody działa poprawnie.

Jeśli to co szukasz następnie wyśmiewać się z randomiser, aby deterministyczny wewnątrz sfery testu.

Zasadniczo mam próbne obiekty dla wszystkich rodzajów niedeterministycznych lub nieprzewidywalnych (w momencie pisania testu) danych, w tym generatory GUID i DateTime.Now.

Edytuj, z komentarzy: Musisz wyśmiewać PRNG (ten termin uciekł mi zeszłej nocy) na najniższym możliwym poziomie - tj. gdy generuje tablicę bajtów, a nie po przekształceniu ich w Int64. Lub nawet na obu poziomach, więc możesz przetestować konwersję do tablicy Int64 działa zgodnie z przeznaczeniem, a następnie osobno przetestować, czy konwersja do tablicy DateTimes działa zgodnie z przeznaczeniem. Jak powiedział Jonathon, możesz to po prostu zrobić, ustawiając ziarno lub możesz podać tablicę bajtów do zwrócenia.

Wolę ten drugi, ponieważ nie złamie się, jeśli zmieni się implementacja PRNG w ramach ramowych. Jednak jedną z zalet nadania mu nasion jest to, że jeśli znajdziesz przypadek w produkcji, który nie działał zgodnie z przeznaczeniem, musisz zalogować tylko jedną liczbę, aby móc go zreplikować, w przeciwieństwie do całej tablicy.

To powiedziawszy, musisz pamiętać, że z jakiegoś powodu nazywa się to Pseudo Random Number Generator. Na tym poziomie mogą występować pewne uprzedzenia.

pdr
źródło
1
Nie. W tym przypadku chcę przetestować sam randomizator i stwierdzić, że „losowe” wartości generowane przez randomizator mieszczą się w określonych ograniczeniach, a jednocześnie są „losowe”, ponieważ nie są ukierunkowane na nierównomierny rozkład w dopuszczalnym zakresie zakresy czasowe. Mogę i wykonuję deterministyczny test, czy konkretna data / czas poprawnie mija lub nie spełnia określonego ograniczenia, ale prawdziwym problemem, jaki napotkałem, było to, że daty wygenerowane przez randomizator były stronnicze, a zatem przewidywalne.
KeithS
Jedyne, co mogę wymyślić, to wyrzucenie przez randomizatora kilku dat i utworzenie histogramu, a następnie stwierdzenie, że wartości są względnie równomiernie rozłożone. Wydaje się to niezwykle ciężkie i wciąż nie deterministyczne, ponieważ każdy naprawdę losowy zestaw danych może wykazywać pozorne uprzedzenie, które mógłby następnie obalić większy zestaw.
KeithS
1
To jest test, który czasem się przerwie i nieprzewidziany. Nie chcesz tego Szczerze mówiąc, chyba źle zrozumiałeś mój punkt widzenia. Gdzieś w tym, co nazywasz randomiserem, musi być linia kodu, która generuje losowy numer, nie? Ta linia jest tym, co nazywam randomiserem, a resztę tego, co nazywacie randomiserem (rozkład dat na podstawie „losowych” danych), jest tym, co chcesz przetestować. A może coś mi brakuje?
pdr
właściwie statystyki statystyczne losowych sekwencji (korelacja, korelacja blokowa, średnia, odchylenia standardowe itp.) nie spełnią twojego zakresu oczekiwań tylko wtedy, gdy wykonasz naprawdę małe próbki. Zwiększyć swoje zestawy próbkowania i / lub zwiększyć dozwolone słupki błędów
lurscher
1
„pewne odchylenie nawet na tym poziomie” Jeśli użyjesz dobrego PRNG, nie będziesz w stanie znaleźć żadnego testu (z realistycznymi granicami obliczeniowymi), który mógłby go odróżnić od prawdziwej losowości. W praktyce można więc założyć, że dobry PRNG nie ma żadnego uprzedzenia.
CodesInChaos
23

To zabrzmi jak głupia odpowiedź, ale zamierzam ją tam wyrzucić, bo tak to widziałem wcześniej:

Oddziel swój kod od PRNG - przekaż ziarno randomizacji do całego kodu używającego randomizacji. Następnie możesz określić „działające” wartości z pojedynczego nasiona (lub wielu z nich, aby poczuć się lepiej). To da ci możliwość odpowiedniego przetestowania twojego kodu bez konieczności polegania na prawie wielkich liczb.

Brzmi to głupio, ale tak właśnie robi to wojsko (albo to, albo używają „losowej tabeli”, która tak naprawdę wcale nie jest losowa)

Jonathan Rich
źródło
Dokładnie: jeśli nie możesz przetestować elementu algorytmu, wyodrębnij go i wyśmiej
Steve Greatrex,
Nie podałem deterministycznej wartości nasion; zamiast tego całkowicie usunąłem element „losowy”, więc nie musiałem nawet polegać na konkretnym algorytmie PRNG. Byłem w stanie przetestować, że biorąc pod uwagę szeroki zakres równomiernie rozłożonych liczb, algorytm, z którym poszedłem, może ograniczyć je do mniejszego zakresu bez wprowadzania uprzedzeń. Sam PRNG powinien zostać odpowiednio przetestowany przez każdego, kto go opracował (używam RNGCryptoServiceProvider).
KeithS
Jeśli chodzi o podejście oparte na „tabeli losowej”, można również zastosować implementację testową, która zawiera „odwracalny” algorytm generujący liczby. Pozwala to „przewinąć” PRNG lub nawet zapytać go, aby zobaczyć, jakie były ostatnie N wyników. Umożliwiłoby to o wiele bardziej dogłębne debugowanie w niektórych scenariuszach.
Darien
To nie jest aż tak głupie - to ta sama metoda, której Google używa do odtworzenia zastrzyku awarii w testach Spannera zgodnie z ich dokumentem :)
Akshat Mahajan
6

„Czy to przypadkowe (wystarczająco)” okazuje się niezwykle subtelnym pytaniem. Krótka odpowiedź jest taka, że ​​tradycyjny test jednostkowy po prostu go nie wycina - musisz wygenerować kilka losowych wartości i poddać je różnym testom statystycznym, które dają ci pewność, że są one wystarczająco losowe dla twoich potrzeb.

Pojawi się wzorzec - w końcu używamy generatorów liczb losowych psuedo. Ale w pewnym momencie wszystko będzie „wystarczająco dobre” dla twojej aplikacji (gdzie wystarczająco dobre różni się DUŻO między grami powiedzmy na jednym końcu, gdzie wystarczą stosunkowo proste generatory, aż do kryptografii, gdzie naprawdę potrzebujesz sekwencji, które są niemożliwe do ustalenia przez zdecydowanego i dobrze wyposażonego napastnika).

Artykuł w Wikipedii http://en.wikipedia.org/wiki/Randomness_tests i odnośniki do niego zawierają więcej informacji.

James Iry
źródło
Nawet mierne PRNG nie wykażą żadnych wzorców w żadnych testach statystycznych. W przypadku dobrych PRNG praktycznie niemożliwe jest odróżnienie ich od rzeczywistych liczb losowych.
CodesInChaos
4

Mam dla ciebie dwie odpowiedzi.

=== PIERWSZA ODPOWIEDŹ ===

Gdy tylko zobaczyłem tytuł twojego pytania, przyszedłem, by wskoczyć i zaproponować rozwiązanie. Moje rozwiązanie było takie samo jak to, co zaproponowało kilka innych: wyśmiewanie generatora liczb losowych. W końcu zbudowałem kilka różnych programów, które wymagały tej sztuczki, aby pisać dobre testy jednostkowe, i zacząłem sprawiać, że możliwy do uzyskania dostęp do liczb losowych jest standardową praktyką w całym moim kodowaniu.

Ale potem przeczytałem twoje pytanie. A dla konkretnego problemu, który opisujesz, to nie jest odpowiedź. Problem nie polegał na tym, że trzeba było przewidzieć proces, który używał liczb losowych (aby był testowalny). Problem polegał raczej na sprawdzeniu, czy algorytm odwzorował jednorodnie losowe dane wyjściowe z twojego RNG na jednolity wynik w ramach ograniczeń twojego algorytmu - że jeśli bazowy RNG był jednolity, spowodowałoby to równomiernie rozłożone czasy kontroli (z zastrzeżeniem ograniczenia problemów).

To naprawdę trudny (ale dość dobrze zdefiniowany) problem. Co oznacza, że ​​jest to CIEKAWY problem. Natychmiast zacząłem wymyślać naprawdę świetne pomysły na rozwiązanie tego problemu. Kiedy byłem programistą Hotshot, mogłem zacząć coś robić z tymi pomysłami. Ale nie jestem już programistą Hotshot ... Lubię to, że jestem teraz bardziej doświadczony i bardziej wykwalifikowany.

Zamiast zanurzyć się w trudny problem, pomyślałem sobie: jaka jest tego wartość? Odpowiedź była rozczarowująca. Twój błąd został już rozwiązany, a w przyszłości będziesz pilnie podchodził do tego problemu. Okoliczności zewnętrzne nie mogą wywołać problemu, a jedynie zmiany w algorytmie. JEDYNYM powodem rozwiązania tego interesującego problemu było zaspokojenie praktyk TDD (Test Driven Design). Jeśli jest jedna rzecz, której się nauczyłem, to ślepe stosowanie się do każdej praktyki, która nie jest cenna, powoduje problemy. Moja propozycja jest następująca: po prostu nie pisz tego testu i przejdź dalej.


=== DRUGA ODPOWIEDŹ ===

Wow ... co za fajny problem!

Musisz tutaj napisać test, który potwierdzi, że twój algorytm do wybierania dat i godzin inspekcji da wynik, który jest równomiernie rozłożony (w ramach ograniczeń problemu), jeśli RNG, którego używa, generuje jednolicie rozłożone liczby. Oto kilka podejść, posortowanych według poziomu trudności.

  1. Możesz zastosować brutalną siłę. Po prostu uruchom algorytm CAŁĄ liczbę razy, z prawdziwym RNG jako wejściem. Sprawdź wyniki wyjściowe, aby zobaczyć, czy są one równomiernie rozmieszczone. Twój test będzie musiał zakończyć się niepowodzeniem, jeśli rozkład różni się od idealnie jednorodnego o więcej niż pewien próg progowy, a aby upewnić się, że złapiesz problemy, próg progowy nie może być ZA NISKI. Oznacza to, że będziesz potrzebował OGROMNEJ liczby przebiegów, aby mieć pewność, że prawdopodobieństwo fałszywie dodatniego (niepowodzenie testu przypadkowo) jest bardzo małe (dobrze <1% dla średniej bazy kodu; jeszcze mniej dla podstawy duża baza kodu).

  2. Rozważ swój algorytm jako funkcję, która pobiera konkatenację wszystkich danych wyjściowych RNG jako dane wejściowe, a następnie generuje czasy inspekcji jako dane wyjściowe. Jeśli wiesz, że ta funkcja jest fragmentarycznie ciągła, istnieje sposób na przetestowanie swojej właściwości. Zamień RNG na próbny RNG i uruchom algorytm wiele razy, uzyskując równomiernie rozłożone wyjście RNG. Więc jeśli twój kod wymagał 2 wywołań RNG, każde w zakresie [0..1], możesz mieć test uruchamiający algorytm 100 razy, zwracając wartości [(0,0,0,0), (0,0,0,1), (0,0, 0.2), ... (0.0.0.9), (0.1.0.0), (0.1.0.1), ... (0.9,0.9)]. Następnie możesz sprawdzić, czy wynik 100 przebiegów był (w przybliżeniu) równomiernie rozłożony w dozwolonym zakresie.

  3. Jeśli NAPRAWDĘ potrzebujesz zweryfikować algorytm w wiarygodny sposób i nie możesz poczynić założeń dotyczących algorytmu LUB uruchomić go wiele razy, nadal możesz zaatakować problem, ale możesz potrzebować pewnych ograniczeń w sposobie programowania algorytmu . Sprawdź PyPy i ich podejście do Object Object jako przykład. Możesz stworzyć Przestrzeń Obiektową, która zamiast faktycznie wykonywać algorytm, po prostu obliczyła kształt rozkładu wyjściowego (zakładając, że wejście RNG jest jednolite). Oczywiście wymaga to zbudowania takiego narzędzia i zbudowania algorytmu w PyPy lub innym narzędziu, w którym łatwo jest wprowadzić drastyczne modyfikacje kompilatora i użyć go do analizy kodu.

mcherm
źródło
3

W przypadku testów jednostkowych zamień generator losowy na klasę, która generuje przewidywalne wyniki obejmujące wszystkie przypadki narożne . To znaczy upewnij się, że twój pseudo-randomizator generuje najniższą możliwą wartość i najwyższą możliwą wartość, i ten sam wynik kilka razy z rzędu.

Nie chcesz, aby twoje testy jednostkowe pomijały np. Błędy off-by-one występujące, gdy Random.nextInt (1000) zwraca 0 lub 999.

użytkownik 281377
źródło
3

Warto przyjrzeć się Sevcikova i in .: „Zautomatyzowane testowanie systemów stochastycznych: podejście oparte na statystyce” ( PDF ).

Metodologia jest wdrażana w różnych przypadkach testowych dla platformy symulacyjnej UrbanSim .

krlmlr
źródło
To dobre rzeczy.
KeithS
2

Proste podejście do histogramu jest dobrym pierwszym krokiem, ale nie wystarcza do udowodnienia losowości. Dla jednolitego PRNG wygenerowałbyś również (przynajmniej) dwuwymiarowy wykres rozproszenia (gdzie x jest poprzednią wartością, a y jest nową wartością). Ta fabuła powinna być również jednolita. Jest to skomplikowane w twojej sytuacji, ponieważ w systemie występują celowe nieliniowości.

Moje podejście to:

  1. sprawdzić (lub przyjąć jako dane), że źródłowy PRNG jest wystarczająco losowy (przy użyciu standardowych miar statystycznych)
  2. sprawdzić, czy nieograniczona konwersja PRNG na datę i godzinę jest wystarczająco losowa w przestrzeni wyjściowej (weryfikuje to brak stronniczości w konwersji). Twój prosty test jednorodności pierwszego rzędu powinien wystarczyć.
  3. sprawdź, czy ograniczone przypadki są wystarczająco jednorodne (prosty test jednorodności pierwszego rzędu na prawidłowych pojemnikach).

Każdy z tych testów jest statystyczny i wymaga dużej liczby punktów próby, aby uniknąć fałszywie dodatnich i fałszywych negatywów o wysokim stopniu ufności.

Jeśli chodzi o naturę algorytmu konwersji / ograniczenia:

Podano: metodę generowania pseudolosowej wartości p, gdzie 0 <= p <= M

Potrzeba: wyjście yw (ewentualnie nieciągłym) zakresie 0 <= y <= N <= M

Algorytm:

  1. obliczyć r = floor(M / N), czyli liczbę kompletnych zakresów wyjściowych, które mieszczą się w zakresie wejściowym.
  2. obliczyć maksymalną dopuszczalną wartość dla p :p_max = r * N
  3. generuj wartości dla p, dopóki nie p_maxzostanie znaleziona wartość mniejsza lub równa
  4. Oblicz y = p / r
  5. jeśli y jest akceptowalne, zwróć je, w przeciwnym razie powtórz krok 3

Kluczem do sukcesu jest odrzucenie niedopuszczalnych wartości zamiast niejednorodnego składania.

w pseudokodzie:

# assume prng generates non-negative values
def randomInRange(min, max, prng):
    range = max - min
    factor = prng.max / range

    do:
        value = prng()
    while value > range * factor
    return (value / factor) + min

def constrainedRandom(constraint, prng):
    do:
        value = randomInRange(constraint.min, constraint.max, prng)
    while not constraint.is_acceptable(value)
Frank Szczerba
źródło
1

Oprócz sprawdzania, czy kod nie zawiedzie lub generuje odpowiednie wyjątki w odpowiednich miejscach, możesz utworzyć prawidłowe pary danych wejściowych / odpowiedzi (nawet obliczając to ręcznie), podaj dane wejściowe w teście i upewnij się, że zwraca oczekiwaną odpowiedź. Nie wspaniale, ale to prawie wszystko, co możesz zrobić, imho. Jednak w twoim przypadku nie jest to tak naprawdę przypadkowe, po utworzeniu harmonogramu możesz przetestować zgodność z regułami - musisz mieć 3 kontrole tygodniowo, między 9-9; nie ma rzeczywistej potrzeby ani możliwości testowania dokładnych czasów, kiedy miała miejsce inspekcja.

Evgeni
źródło
1

Naprawdę nie ma lepszego sposobu niż uruchamianie go kilka razy i sprawdzanie, czy uzyskasz żądaną dystrybucję. Jeśli masz 50 dozwolonych potencjalnych harmonogramów kontroli, uruchom test 500 razy i upewnij się, że każdy harmonogram jest używany prawie 10 razy. Możesz kontrolować losowe nasiona generatora, aby uczynić go bardziej deterministycznym, ale to także sprawi, że twoje testy będą ściślej powiązane ze szczegółami implementacji.

Karl Bielefeldt
źródło
Ale jeśli jest to naprawdę losowe, to od czasu do czasu jakiś harmonogram nie zostanie w ogóle wykorzystany; a czasami jakiś harmonogram zostanie wykorzystany ponad 20 razy. Nie wiem, jak zamierzasz przetestować, czy każdy harmonogram jest używany „prawie 10 razy”, ale niezależnie od testowanego tutaj warunku, będziesz miał test, który czasami kończy się niepowodzeniem, gdy program działa zgodnie ze specyfikacją.
Dawood mówi, że przywróć Monikę
@DawoodibnKareem z wystarczającą wielkością próby (i rozsądnymi limitami jednorodności) możesz zmniejszyć prawdopodobieństwo, że test nie osiągnie 1 miliarda. I ogólnie takie statystyki są wykładnicze z n, więc dotarcie do tych liczb zajmuje mniej niż się spodziewasz.
mbrig
1

Nie można przetestować mglistego stanu, który nie ma konkretnej definicji. Jeśli wygenerowane daty przejdą wszystkie testy, teoretycznie aplikacja działa poprawnie. Komputer nie może powiedzieć, czy daty są „wystarczająco losowe”, ponieważ nie może potwierdzić kryteriów takiego testu. Jeśli wszystkie testy zakończą się pomyślnie, ale zachowanie aplikacji nadal nie jest odpowiednie, wówczas pokrycie testowe jest empirycznie nieodpowiednie (z perspektywy TDD).

Moim zdaniem najlepiej jest wdrożyć dowolne ograniczenia generowania dat, aby dystrybucja przeszła test ludzkiego zapachu.

Lew
źródło
2
Możesz bezwzględnie określić losowość za pomocą automatycznych testów. Po prostu wygenerujesz wystarczająco dużą liczbę próbek i zastosujesz standardowe testy losowości, aby wykryć błędy w systemie. Jest to dość standardowe ćwiczenie z programowania.
Frank Szczerba
0

Po prostu zapisz dane wyjściowe swojego randomizatora (pseudo lub kwantowo / chaotycznie lub w świecie rzeczywistym). Następnie zapisz i odtwórz te „losowe” sekwencje, które pasują do twoich wymagań testowych lub które ujawniają potencjalne problemy i błędy, podczas budowania testów jednostkowych.

hotpaw2
źródło
0

Ten przypadek wydaje się idealny do testów opartych na właściwościach .

Krótko mówiąc, jest to tryb testowania, w którym środowisko testowe generuje dane wejściowe dla testowanego kodu, a twierdzenia testowe sprawdzają właściwości danych wyjściowych. Struktura może być wystarczająco inteligentna, aby „zaatakować” testowany kod i spróbować doprowadzić go do błędu. Framework jest zwykle wystarczająco inteligentny, aby przejąć kontrolę nad generatorem liczb losowych. Zazwyczaj można skonfigurować środowisko do generowania co najwyżej N przypadków testowych lub co najwyżej N sekund i zapamiętywanie nieudanych przypadków testowych od ostatniego uruchomienia i ponowne uruchomienie ich najpierw dla nowszej wersji kodu. Pozwala to na szybki cykl iteracji podczas programowania i powolne, kompleksowe testowanie poza pasmem / w CI.

Oto (głupi, nieudany) przykład testowania sumfunkcji:

@given(lists(floats()))
def test_sum(alist):
    result = sum(alist)
    assert isinstance(result, float)
    assert result > 0
  • środowisko testowe wygeneruje jedną listę na raz
  • zawartość listy będzie liczbami zmiennoprzecinkowymi
  • sum jest wywoływany, a właściwości wyniku są sprawdzane
  • wynik jest zawsze zmiennoprzecinkowy
  • wynik jest pozytywny

W tym teście znajdziesz kilka „błędów” sum(skomentuj, jeśli sam potrafisz odgadnąć wszystkie ):

  • sum([]) is 0 (int, nie float)
  • sum([-0.9]) jest ujemny
  • sum([0.0]) nie jest ściśle pozytywne
  • sum([..., nan]) is nan co nie jest pozytywne

Przy ustawieniach domyślnych hpythesisprzerywa test po znalezieniu 1 „złego” wejścia, co jest dobre dla TDD. Myślałem, że można go skonfigurować tak, aby zgłaszał wiele / wszystkie „złe” dane wejściowe, ale nie mogę teraz znaleźć tych opcji.

W przypadku OP zatwierdzone właściwości będą bardziej złożone: kontrola typu A obecna, kontrola typu A trzy razy w tygodniu, czas kontroli B zawsze o godzinie 12:00, kontrola typu C od 9 do 9, [podany harmonogram obejmuje tydzień] kontrole typów A, B, C wszystkie obecne itp.

Najbardziej znaną biblioteką jest QuickCheck dla Haskell, patrz strona Wikipedii poniżej, aby uzyskać listę takich bibliotek w innych językach:

https://en.wikipedia.org/wiki/QuickCheck

Hipoteza (dla Pythona) ma dobre zdanie na temat tego rodzaju testowania:

https://hypothesis.works/articles/what-is-property-based-testing/

Dima Tisnek
źródło
-1

testem jednostkowym jest logika określająca, czy losowe daty są ważne, czy też należy wybrać inną losową datę.

Nie ma sposobu, aby przetestować generator losowych dat bez zebrania wielu dat i podjęcia decyzji, czy są one odpowiednio losowe.

Ryathal
źródło
-1

Twoim celem nie jest pisanie testów jednostkowych i zaliczanie ich, ale upewnienie się, że Twój program spełnia jego wymagania. Jedynym sposobem, aby to zrobić, jest przede wszystkim precyzyjne zdefiniowanie wymagań. Na przykład wspomniałeś o „trzy cotygodniowe kontrole w losowych momentach”. Powiedziałbym, że wymagania są następujące: (a) 3 kontrole (nie 2 lub 4), (b) w momentach, których ludzie nie chcą przewidzieć niespodziewanie, i (c) niezbyt blisko siebie - dwie inspekcje w odstępie pięciu minut są prawdopodobnie bezcelowe, być może też nie są zbyt daleko od siebie.

Więc zapisujesz wymagania dokładniej niż ja. (a) i (c) są łatwe. W przypadku (b) możesz napisać kod tak sprytnie, jak to możliwe, który próbuje przewidzieć następną inspekcję i aby przejść test jednostkowy, kod ten nie może przewidzieć lepiej niż zwykłe zgadywanie.

I oczywiście musisz pamiętać, że jeśli twoje kontrole są naprawdę losowe, każdy algorytm prognozowania może być poprawny przypadkiem, więc musisz mieć pewność, że ty i twoje testy jednostkowe nie panikują, jeśli tak się stanie. Może wykonaj jeszcze kilka testów. Nie zawracałbym sobie głowy testowaniem generatora liczb losowych, ponieważ ostatecznie liczy się harmonogram inspekcji i nie ma znaczenia, w jaki sposób został utworzony.

gnasher729
źródło
Nie, po prostu nie. Testy jednostkowe dowodzą, że program spełnia jego wymagania, więc oba są takie same. Nie zajmuję się pisaniem oprogramowania predykcyjnego w celu inżynierii losowej algorytmów. Gdybym tak był, nie powiedziałbym ci o tym, robiłbym zabijanie, włamując się do bezpiecznych stron internetowych, przewidując ich klucze i sprzedając sekrety najlepszemu oferentowi. Moja firma pisze harmonogram, który tworzy czasy, które są ograniczone, ale nieprzewidywalne w ramach ograniczeń, i potrzebuję testów deterministycznych, aby to udowodnić, a nie probabilistycznych, które mówią, że jestem całkiem pewien.
KeithS