Jak powinienem przetestować losowość?

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.

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).

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.

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.

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.

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:

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

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).

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.

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.

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!

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;