Jak powinienem przetestować losowość?

127

Rozważ metodę losowego tasowania elementów w tablicy. Jak napisałbyś prosty, ale solidny test jednostkowy, aby upewnić się, że działa?

Wymyśliłem dwa pomysły, z których oba mają zauważalne wady:

  • Potasuj tablicę, a następnie upewnij się, że jej kolejność różni się od poprzedniej. Brzmi to dobrze, ale kończy się niepowodzeniem, jeśli losowanie jest losowe w tej samej kolejności. (Nieprawdopodobne, ale możliwe.)
  • Potasuj tablicę ze stałym ziarnem i sprawdź ją z ustalonym wynikiem. Zależy to od funkcji losowej, która zawsze zwraca te same wartości dla tego samego ziarna. Jednak czasami jest to nieprawidłowe założenie .

Rozważ drugą funkcję, która symuluje rzuty kostką i zwraca losową liczbę. Jak przetestowałbyś tę funkcję? Jak przetestowałbyś tę funkcję ...

  • nigdy nie zwraca liczby poza podanymi granicami?
  • zwraca liczby w prawidłowym rozkładzie? (Jednolity dla jednej kości, normalny dla dużej liczby kości.)

Szukam odpowiedzi oferujących wgląd w testowanie nie tylko tych przykładów, ale ogólnie losowych elementów kodu. Czy testy jednostkowe są tu nawet właściwym rozwiązaniem? Jeśli nie, jakie to są testy?


Aby uspokoić wszystkich, nie piszę własnego generatora liczb losowych.

dlras2
źródło
35
Mocne połączenie pokazuje głowę. Przekaż obiekt, który generuje liczby losowe. Następnie podczas testowania możesz przekazać obiekt, który generuje określony zestaw liczb, dla którego wiesz, jak wygląda talia po tasowaniu. Możesz przetestować losowość generatora liczb losowych osobno.
Martin York
1
Zdecydowanie rozważę użycie istniejącej procedury bibliotecznej do odtwarzania losowego (java Collections.shuffle () lub podobna). Na stronie developer.com/tech/article.php/616221/... znajduje się przestroga dotycząca pisania błędnego algorytmu losowego. Aby napisać funkcję d6 (), należy przetestować ją wystarczająco, aby mieć pewność, że nie wygeneruje ona liczby spoza zakresu, a następnie wykonać test chi kwadrat na rozkładzie (chi kwadrat jest dość wrażliwy na pseudolosowe sekwencje). Spójrz również na współczynnik korelacji szeregowej.
„Zależy to od funkcji losowej, która zawsze zwraca te same wartości przy tym samym ziarnie. Jednak czasami jest to nieprawidłowe założenie”. Połączyłem się z linkiem i nie widzę nieprawidłowego założenia. Mówi to dość wyraźnie: „Jeżeli wielokrotnie używa się tego samego materiału siewnego, generowana jest ta sama seria liczb”.
Kyralessa
@ Kyralessa „Wdrożenie generatora liczb losowych w klasie Random nie jest gwarantowane, że pozostanie takie samo w głównych wersjach .NET Framework.” Więc nie jest to duży problem, ale wciąż coś do rozważenia.
dlras2
4
@ Kyralessa Przegapiłem ważną połowę cytatu: „W rezultacie kod aplikacji nie powinien zakładać, że ten sam materiał źródłowy spowoduje taką samą pseudolosową sekwencję w różnych wersjach .NET Framework.”
dlras2

Odpowiedzi:

102

Nie sądzę, aby testy jednostkowe były właściwym narzędziem do testowania losowości. Test jednostkowy powinien wywołać metodę i przetestować zwróconą wartość (lub stan obiektu) względem wartości oczekiwanej. Problem z testowaniem losowości polega na tym, że nie ma oczekiwanej wartości dla większości rzeczy, które chcesz przetestować. Możesz testować z danym ziarnem, ale to tylko testuje powtarzalność . Nie daje ci żadnego sposobu, aby zmierzyć, jak losowy jest rozkład lub czy w ogóle jest losowy.

Na szczęście istnieje wiele testów statystycznych, które można uruchomić, takich jak Diehard Battery of Tests of Randomness . Zobacz też:

  1. Jak przetestować jednostkę pseudolosowy generator liczb losowych?

    • Steve Jessop zaleca znalezienie przetestowanej implementacji tego samego algorytmu RNG, którego używasz i porównanie jego wyników z wybranymi nasionami z własną implementacją.
    • Greg Hewgill zaleca zestaw testów statystycznych ENT .
    • John D. Cook odsyła czytelników do swojego artykułu CodeProject Proste generowanie liczb losowych , który obejmuje implementację testu Kołmogorowa-Smirnowa wspomnianego w tomie 2 Donalda Knutha, Seminumerical Al Algorytmy.
    • Kilka osób zaleca sprawdzenie, czy rozkład generowanych liczb jest jednolity, test chi-kwadrat i sprawdzenie, czy średnia i odchylenie standardowe mieszczą się w oczekiwanym zakresie. (Pamiętaj, że samo testowanie dystrybucji nie wystarczy. [1,2,3,4,5,6,7,8] jest rozkładem jednolitym, ale z pewnością nie jest losowe.)
  2. Testowanie jednostkowe z funkcjami, które zwracają losowe wyniki

    • Brian Genisio zwraca uwagę, że drwina z RNG jest jedną z opcji umożliwiających powtarzalność testów i zapewnia przykładowy kod C #.
    • Ponownie kilka innych osób wskazuje na stosowanie stałych wartości nasion dla powtarzalności i prostych testów dla równomiernego rozkładu, chi-kwadrat itp.
  3. Unit Testing Randomness to artykuł na wiki, który mówi o wielu wyzwaniach, które już się pojawiły podczas próby przetestowania tego, co z natury nie jest powtarzalne. Jeden interesujący fragment, który z niego wyciągnąłem, był następujący:

    Widziałem wcześniej program Winzip jako narzędzie do pomiaru losowości pliku wartości (oczywiście, im mniejszy może skompresować plik, tym mniej jest losowy).

Bill jaszczurka
źródło
Innym dobrym zestawem testów losowości statystycznej jest „ent” znaleziony na stronie fourmilab.ch/random .
1
Czy możesz podsumować niektóre zamieszczone linki, aby uzyskać kompletną odpowiedź?
dlras2
@ DanRasmussen Jasne, będę miał czas na weekend.
Bill the Jaszczurka
4
„Problem z… losowością polega na tym, że nie ma oczekiwanej wartości…” - jak na ironię, biorąc pod uwagę, że „oczekiwana wartość” jest dobrze zdefiniowanym terminem w statystykach. I choć nie o to ci chodziło, wskazuje na właściwe rozwiązanie: wykorzystanie znanych właściwości rozkładów statystycznych w połączeniu z losowym próbkowaniem i testami statystycznymi w celu ustalenia, czy algorytm działa z bardzo dużym prawdopodobieństwem. Tak, to nie jest klasyczny test jednostkowy, ale chciałem o nim wspomnieć, ponieważ w najprostszym przypadku chodzi tylko o rozkład… oczekiwanej wartości .
Konrad Rudolph
2
W Dieharder dostępna jest zaktualizowana wersja słynnej Baterii losowych testów Dieharda, która obejmuje pakiet statystyczny (STS) opracowany przez National Institute for Standards and Technology (NIST). Jest dostępny gotowy do uruchomienia w Ubuntu i przypuszczalnie w innych dystrybucjach: phy.duke.edu/~rgb/General/dieharder.php
nealmcb
21

1. Jednostka przetestuj swój algorytm

Na pierwsze pytanie zbudowałbym fałszywą klasę, w której podajesz sekwencję liczb losowych, dla których znasz wynik swojego algorytmu. W ten sposób upewnisz się, że algorytm zbudowany na podstawie funkcji losowej działa. Więc coś w stylu:

Random r = new RandomStub([1,3,5,3,1,2]);
r.random(); //returns 1
r.random(); //returns 3
...

2. Sprawdź, czy funkcja losowa ma sens

Do testu jednostkowego należy dodać test, który uruchamia się wiele razy i stwierdza, że ​​wyniki

  • mieszczą się w ustalonych granicach (więc rzut kostką wynosi od 1 do 6) i
  • pokaż rozsądny rozkład (wykonaj wiele testów i sprawdź, czy rozkład mieści się w x% oczekiwanych wartości, np. dla rzutu kostką powinieneś zobaczyć 2wzrost między 10% a 20% (1/6 = 16,67%) biorąc pod uwagę, że rzuciłeś go 1000 razy).

3. Test integracji algorytmu i funkcji losowej

Jak często można oczekiwać, że tablica jest sortowana w oryginalnym sortowaniu? Posortuj kilkaset razy i zapewnij, że tylko x% czasu sortowania się nie zmienia.

W rzeczywistości jest to już test integracyjny, testujesz algorytm razem z funkcją losową. Po użyciu prawdziwej funkcji losowej nie można już uciec od pojedynczych testów.

Z doświadczenia (napisałem algorytm genetyczny) powiedziałbym, że należy połączyć test jednostkowy twojego algorytmu, test rozkładu twojej losowej funkcji i test integracji.

sebastiangeiger
źródło
14

Jednym z aspektów PRNG, o którym wydaje się, że się zapomina, jest to, że wszystkie jego właściwości mają charakter statystyczny: nie można oczekiwać, że przetasowanie tablicy spowoduje inną permutację niż ta, od której zacząłeś. Zasadniczo, jeśli używasz normalnego PRNG, jedyną gwarancją jest to, że nie używa on prostego wzorca (mam nadzieję) i że ma on równomierny rozkład między zestawem liczb, które zwraca.

Właściwy test dla PRNG będzie polegał na uruchomieniu go co najmniej 100 razy, a następnie sprawdzeniu rozkładu wyniku (co jest bezpośrednią odpowiedzią na drugą część pytania).

Odpowiedź na pierwsze pytanie jest prawie taka sama: uruchom test około 100 razy za pomocą {1, 2, ..., n} i policz, ile razy każdy element był w każdej pozycji. Powinny być one w przybliżeniu równe, jeśli metoda losowania jest dobra.

Zupełnie inną kwestią jest testowanie PRNG klasy kryptograficznej. Jest to kwestia, w której prawdopodobnie nie powinieneś się rozwodzić, chyba że naprawdę wiesz, co robisz. Ludzie znają się na niszczeniu (czytaj: otwieranie katastroficznych dziur) dobrych kryptosystemów za pomocą kilku „optymalizacji” lub trywialnych zmian.

EDYCJA: Dokładnie ponownie przeczytałem pytanie, najlepszą odpowiedź i moje własne. Podczas gdy podnoszone przeze mnie punkty są nadal aktualne, poparłbym odpowiedź Billa Jaszczura. Testy jednostkowe są z natury logiczne - albo kończą się niepowodzeniem, albo kończą się sukcesem, i dlatego nie nadają się do testowania „jak dobre” są właściwości PRNG (lub metody wykorzystującej PRNG), ponieważ każda odpowiedź na to pytanie byłaby ilościowa , a nie polarny.

K.Steff
źródło
1
Myślę, że masz na myśli, że liczba elementów każdego elementu w każdej pozycji powinna być w przybliżeniu równa. Jeśli są konsekwentnie dokładnie równe, coś jest bardzo nie tak.
octu
@terntern Dzięki, nie wiem, jak mogłem napisać, że ... do tej pory było całkowicie źle ...
K.Steff
6

Składają się na to dwie części: testowanie randomizacji i testowanie rzeczy korzystających z randomizacji.

Testowanie randomizacji jest stosunkowo proste. Sprawdzasz, czy okres generatora liczb losowych jest taki, jak się spodziewasz (dla kilku próbek z kilkoma rodzajami losowych nasion, w ramach pewnego progu) i czy rozkład wyniku na dużą wielkość próbki jest zgodny z oczekiwaniami powinno być (w ramach pewnego progu).

Testowanie rzeczy wykorzystujących randomizację najlepiej przeprowadzić za pomocą deterministycznego generatora liczb losowych psuedo-losowych. Ponieważ dane wyjściowe z randomizacji są znane w oparciu o ziarno (jego dane wejściowe), możesz testować jednostkowo w oparciu o dane wejściowe w porównaniu z oczekiwanymi wynikami. Jeśli twój RNG nie jest deterministyczny, kpij z nim, który jest deterministyczny (lub po prostu nieprzypadkowy). Przetestuj losowość w oderwaniu od kodu, który ją zużywa.

Telastyn
źródło
6

Pozwól mu działać kilka razy i wizualizuj swoje dane .

Oto przykład losowania z Horroru kodowania , możesz zobaczyć, że algorytm jest OK, czy nie:

wprowadź opis zdjęcia tutaj

Łatwo zauważyć, że każdy możliwy element jest zwracany co najmniej raz (granice są OK) i że rozkład jest OK.

Carra
źródło
1
Wizualizacja +1 jest kluczem. Zawsze podobał mi się przykład ze zdjęciem pingwina w dziale EBC w artykule o szyfrach blokowych ). Zautomatyzowane oprogramowanie rzadko wykrywa takie prawidłowości
Maksee
Co? Celem tej wizualizacji jest pokazanie, że rozkład nie jest prawidłowy . Naiwny algorytm losowania sprawia, że ​​niektóre zamówienia są znacznie bardziej prawdopodobne niż inne. Zauważ, jak daleko w prawo rozciągają się słupki 2341, 2314, 2143 i 1342?
hvd
4

Ogólne wskazówki, które uważam za przydatne w przypadku kodu, który pobiera dane losowe: Sprawdź przypadki skrajne oczekiwanej losowości (wartości maks. I min. Oraz wartości maks. + 1 i min-1, jeśli dotyczy). Sprawdź miejsca (na, powyżej i poniżej), w których liczby mają punkty przegięcia (tj. -1, 0, 1 lub więcej niż 1, mniej niż 1 i nieujemne dla przypadków, w których wartość ułamkowa może zepsuć funkcję). Sprawdź kilka miejsc całkowicie poza dozwolonym wejściem. Sprawdź kilka typowych przypadków. Możesz również dodać losowe dane wejściowe, ale w przypadku testu jednostkowego, który ma niepożądany efekt uboczny, ta sama wartość nie jest testowana za każdym razem, gdy test jest uruchamiany (podejście początkowe może jednak działać, przetestuj pierwsze 1000 liczb losowych z nasion S lub jakoś).

W celu przetestowania wyniku funkcji losowej ważne jest określenie celu. W przypadku kart, czy celem jest sprawdzenie jednolitości losowego generatora 0-1, aby ustalić, czy w wyniku pojawią się wszystkie 52 karty, czy jakiś inny cel (może cała ta lista i więcej)?

W konkretnym przykładzie musisz założyć, że generator liczb losowych jest nieprzejrzysty (tak jak nie ma sensu testowanie systemowe OSScall lub malloc - chyba że piszesz OS). Przydatny może być pomiar generatora liczb losowych, ale Twoim celem nie jest napisanie generatora liczb losowych, tylko po to, aby zobaczyć, że za każdym razem dostajesz 52 karty i że zmieniają kolejność.

To długa droga do powiedzenia, że ​​tak naprawdę są tutaj dwa zadania testowe: testowanie, czy RNG wytwarza prawidłowy rozkład i sprawdzanie, czy kod tasowania karty używa tego RNG do generowania losowych wyników. Jeśli piszesz RNG, użyj analizy statystycznej, aby udowodnić swoją dystrybucję, jeśli piszesz tasownikiem kart, upewnij się, że na każdym wyjściu znajdują się 52 powtarzające się karty (jest to lepszy przypadek do przetestowania przez sprawdzenie, czy używasz RNG).

zaraz
źródło
4

Możesz polegać na bezpiecznych generatorach liczb losowych

Właśnie pomyślałem sobie okropnie: nie piszesz własnego generatora liczb losowych, prawda?

Zakładając, że nie jesteś, powinieneś przetestować kod, za który jesteś odpowiedzialny , a nie kod innych osób (np. SecureRandomImplementację twojego frameworka).

Testowanie kodu

Aby sprawdzić, czy kod reaguje poprawnie, normalnym jest stosowanie metody o niskiej widoczności do generowania liczb losowych, aby można je było łatwo zastąpić klasą testów jednostkowych. Ta przesłonięta metoda skutecznie wyśmiewa generator liczb losowych i daje pełną kontrolę nad tym, co jest produkowane i kiedy. W związku z tym możesz w pełni ćwiczyć kod, który jest celem testów jednostkowych.

Oczywiście sprawdzisz warunki brzegowe i upewnisz się, że tasowanie odbywa się dokładnie tak, jak nakazuje twój algorytm, biorąc pod uwagę odpowiednie dane wejściowe.

Testowanie bezpiecznego generatora liczb losowych

Jeśli nie masz pewności, że bezpieczny generator liczb losowych dla twojego języka nie jest naprawdę przypadkowy lub zawiera błędy (zapewnia wartości spoza zakresu itp.), Musisz przeprowadzić szczegółową analizę statystyczną wyniku na kilkaset milionów iteracji. Narysuj częstotliwość występowania każdej liczby i powinna ona pojawić się z jednakowym prawdopodobieństwem. Jeśli wyniki są zniekształcone w taki czy inny sposób, należy zgłosić swoje ustalenia projektantom ram. Z pewnością będą zainteresowani rozwiązaniem problemu, ponieważ bezpieczne generatory liczb losowych są podstawą wielu algorytmów szyfrowania.

Gary Rowe
źródło
1

Cóż, nigdy nie będziesz w 100% pewien, więc najlepsze, co możesz zrobić, to to, że liczby są losowe. Wybierz prawdopodobieństwo - powiedz, że próbka liczb lub przedmiotów pojawi się x razy, biorąc pod uwagę milion próbek, z marginesem błędu. Uruchom rzecz milion razy i sprawdź, czy mieści się w marginesie. Na szczęście komputery sprawiają, że jest to łatwe.

Matthew Flynn
źródło
Ale czy takie testy jednostkowe są uważane za dobrą praktykę ...? Zawsze uważałem, że test jednostkowy powinien być tak prosty, jak to tylko możliwe: żadnych pętli, gałęzi ani niczego innego, czego można by uniknąć.
dlras2
4
Testy jednostkowe powinny być prawidłowe . Jeśli to wymaga rozgałęzień, pętli, rekurencji - taka jest cena. Nie można testować jednostkowo wyjątkowo wyrafinowanych, wysoce zoptymalizowanych klas za pomocą testów jednostopniowych. Zaimplementowałem algorytm Dijkstry, aby raz przetestować klasę.
K.Steff
3
@ K.Steff, wow. Czy przeprowadziłeś test jednostkowy testu jednostkowego, aby zweryfikować poprawność algorytmu Dijkstry?
Winston Ewert
W rzeczy samej - tak, ale tym razem z „trywialnymi” testami. Były to jednak także testy jednostkowe oryginalnego programu (A *). Myślę, że to naprawdę dobra praktyka - ponowne testowanie szybkich algorytmów po kiepskich (ale poprawnych) implementacjach.
K.Steff
1

Aby sprawdzić, czy źródłem liczb losowych generuje coś, co przynajmniej ma wygląd losowości, musiałbym test generuje dość dużą sekwencję bajtów, zapisać je do pliku tymczasowego, a następnie wyłożyć na Fourmilab za ent narzędzia. Podaj przełącznik -t (zwięzły), aby wygenerował łatwy do przeanalizowania plik CSV. Następnie sprawdź różne liczby, aby zobaczyć, czy są „dobre”.

Aby zdecydować, które liczby są dobre, użyj znanego źródła losowości, aby skalibrować test. Test powinien prawie zawsze przejść pomyślnie, jeśli otrzyma dobry zestaw liczb losowych. Ponieważ nawet prawdziwie losowa sekwencja ma prawdopodobieństwo wygenerowania sekwencji, która wydaje się nieprzypadkowa, nie można uzyskać testu, który z pewnością przejdzie. Po prostu wybierasz progi, które sprawiają, że jest mało prawdopodobne, aby losowa sekwencja spowodowała błąd testu. Czy przypadkowość nie jest fajna?

Uwaga: Nie można napisać testu, który pokazuje, że PRNG generuje „losową” sekwencję. Możesz napisać test, który, jeśli przejdzie pomyślnie, wskazuje pewne prawdopodobieństwo, że sekwencja wygenerowana przez PRNG jest „losowa”. Witamy w radości losowości!

Wayne Conrad
źródło
1

Przypadek 1: Testowanie losowania:

Rozważ tablicę [0, 1, 2, 3, 4, 5], potasuj ją, co może pójść nie tak? Zwykłe rzeczy: a) w ogóle nie tasuje, b) tasuje 1-5, ale nie 0, tasuje 0-4, ale nie 5, tasuje i zawsze generuje ten sam wzór, ...

Jeden test, aby złapać je wszystkie:

Potasuj 100 razy, dodaj wartości w każdym gnieździe. Suma każdego gniazda powinna być podobna do siebie. Avg / Stddev można obliczyć. (5 + 0) /2=2.5, 100 * 2,5 = 25. Oczekiwana wartość wynosi na przykład około 25.

Jeśli wartości są poza zakresem, istnieje niewielka szansa, że ​​otrzymałeś fałszywie ujemny wynik. Możesz obliczyć, jak duża jest ta szansa. Powtórz test. Cóż - oczywiście istnieje niewielka szansa, że ​​test nie powiedzie się 2 razy z rzędu. Ale nie masz procedury, która automatycznie usuwa źródło, jeśli test jednostkowy się nie powiedzie, prawda? Uruchom ponownie!

Może zawieść 3 razy z rzędu? Może powinieneś spróbować szczęścia na loterii.

Przypadek 2: Rzuć kostką

Pytanie o rzut kostką jest tym samym pytaniem. Rzuć kostką 6000 razy.

for (i in 0 to 6000) 
    ++slot [Random.nextInt (6)];
return (slot.max - slot.min) < threshold;
nieznany użytkownik
źródło