Testowanie programów II: Piszemy losowe testy

Wymyślenie rozwiązania i zaimplementowanie go to nie wszystko. Musimy go jeszcze przetestować. Najlepiej przy użyciu dużej liczby testów. Długich i dużych testów. No dobrze, ale w jaki sposób je generować, skoro napisanie ręcznie jednego zajęłoby wieki? W tym poście postaram się opisać kilka najczęstszych typów testów, jakie mogą być przydatne do sprawdzenia naszego kodu.

Losowa permutacja

Wyjaśnienia mogą wymagać dwie pierwsze linijki funkcji main()

Funkcja main() jak każda inna funkcja może przyjmować argumenty, które możemy przesłać podczas wywołania programu (   to nazwa pliku wykonywalnego z naszym kodem)

W  znajduje się ilość argumentów (w naszym przykładzie 3 – nazwa programu + 2 przesłane) a w  ich wartości. W naszym przykładzie tablica ta zawiera kolejno „solution”, „123” i „argument2”. Wszystkie jej wartości są stringami (a dokładniej c-stringami).

W programie do generowania losowej permutacji przesyłamy jako pierwszy argument rozmiar permutacji, jaką chcemy otrzymać. Tak jak wspomniałem nawet gdy przesyłamy liczbę, do   trafi ona jako string, więc potrzebujemy funkcji, która zmieni nam stringa na liczbę. Taką funkcją jest   (string to integer).

Żeby otrzymać permutację, np. 10 elementową program wywołujemy tak:

Jeśli chcemy zapisać ją do pliku przekierowujemy wyjście podając jego ścieżkę:

Losowa tablica liczb z określonego zakresu

Kilka słów o linijkach:

Pierwsza z nich tworzy obiekt typu  , który służy do zwrócenia losowej liczby przy użyciu sprzętu. Z pewnych powodów (o których można poczytać w internecie) użycie go do wygenerowania wielu liczb jest niepoprawne – z każdą kolejną, wygenerowane liczby stają się coraz mniej losowe. Dlatego używa się tzw. generator liczb pseudolosowych (ang. PRNG), które potrafią to robić lepiej, a   służy tylko do inicjalizacji generatora. Jednym z takich generatów jest  .

Założmy, że nas jednak nie interesują kompletnie losowe liczby, ale takie z pewnego określonego zakresu. W tym celu potrzebujemy utworzyć jeszcze jeden obiekt, który wskaże generatorowi rozkład, z którego chcemy losować.  określa rozkład jednostajny (czyli taki, gdzie każda liczba ma takie samo prawdopodobieństwo wylosowania) na określonym zakresie.

Liczbę generujemy tak:

Jeśli wywołamy nasz program np. w ten sposób

otrzymamy 10 losowych liczb z zakresu

Losowe drzewo

Żeby otrzymać losowe drzewo użyjemy tego, czego nauczyliśmy się w poprzednim punktcie, mianowicie dla każdego z wierzchołków wylosujemy jego rodzica.

Losowe drzewo z długimi ścieżkami

Czasem nie chcemy, by nasze drzewo było zupełnie losowe. Dla przykładu – jeśli podejrzewamy, że złożoność naszego rozwiązania może zależeć od głębokości drzewa, możemy spróbować wygenerować drzewo z wieloma długimi ścieżkami (oczywiście, drzewo o największej wysokości to ścieżka, ale wygenerowanie niej nie stanowi już dla nas problemu, zwłaszcza po przeczytaniu pierwszego punktu, prawda?)

Przepis na wygenerowanie drzewa z długimi ścieżkami:

  1. Generujemy losową permutację
  2. Dla każdego z wierzchołków (w wylosowanej kolejności):
    1. Z prawdopodobieństwem p podpinamy go pod poprzedni wierzchołek
    2. Z prawdopodobieństwem 1-p, losujemy dla niego rodzica spośród pozostałych poprzednich wierzchołków

Oczywiście, im większe ustawimy  tym dłuższe ścieżki będzie zawierać nasze drzewo (i bardziej przypominać ścieżkę).

Losowe drzewo binarne

Spotykamy się również z zadaniami, w których drzewa mają określoną strukturą, np. są drzewami binarnymi. Jak sobie poradzić w takim przypadku?

  1. Generujemy losową permutację.
  2. Losujemy korzeń drzewa
    1. Założmy, że wylosowaliśmy i-ty wierzchołek (w wylosowanej kolejności)
    2. Wierzchołki 0, 1, …, i-1 będą stanowić jego lewe poddrzewo.
    3. Wierzchołki i+1, i+2, …, n-1 utworzą jego prawe poddrzewo.
  3. Wołamy się rekurencyjnie na lewym i prawym poddrzewie.

Losowy, spójny graf

Aby wygenerować losowy, spójny graf wystarczy:

  1. Wygenerować losowe drzewo.
  2. Dodawać krawędzie między losową parą wierzchołków.

Komenda

wygeneruje nam graf o 10 tys. wierzchołków i 50 tys. krawędzi między nimi.

Losowy gęsty/rzadki graf

W tej sytuacji wystarczy, gdy podamy odpowiednie  jako parametr przy uruchamianiu naszego generatora.

rand()

Często możemy się spotkać z programami, które generują losowe liczby za pomocą funkcji rand() . Funkcja ta ma sporo ograniczeń (np. na większości komputerów zwraca liczby 2 bitowe z zakresu 0…65535), dlatego nie powinieneś jej używać. Wszystkie sposoby, które zaprezentowałem w tym wpisie pochodzą z najnowszego standardu C++ i są zalecane przez jego twórców.

Tworzenie wielu testów

Pozostaje odpowiedzieć na pytanie: po co tak się męczyliśmy i podawaliśmy wszystkie parametry jako argumenty do funkcji  ? Teraz to wykorzystamy.

Zwykle jest tak, że nie chcemy wygenerować jednego testu – chcemy wygenerować ich jak najwięcej (zwłaszcza, że wszystkie nasze testy są losowe). Aby to zrobić musimy uruchomić nasz generator wiele razy. Najlepiej wtedy napisać skrypt w Bashu (języku obsługiwany przez terminal/konsolę). Pętla w tym języku wygląda tak:

Zapisujemy kod do pliku (np.  ) i uruchamiamy tak jak każdy inny plik wykonywalny

Zazwyczaj przed tym potrzebujemy ustawić zgodę na odpalenie tego pliku jak binarkę. Robi się to tak:

Powyższy skrypt powinien wypisać na ekran:

Czyli wszystko działa, jak powinno. Zmodyfikujmy kod, by uruchamiał nasz generator:

Uruchamia 5 razy generator z   i  i zapisuje jego wyjście do plików  ,   …

Odrobinę zmodyfikowałem program generujący losowy graf, tak, by wypisywał go na ekran. Teraz wygląda następująco:

Jeśli spojrzymy w zawartość dowolnego z wygenerowanych testów, powinniśmy ujrzeć coś na wzór:

Oczywiście dokładny format testu musimy dostować do zadania, które rozwiązujemy.

Możemy również łatwo uruchomić nasz program (plik  ) na wygenerowanych testach:

… i zapisać jego wyjście do plików  ,   itd.

Wykorzystajmy wreszcie to, że przesyłamy parametry do funkcji  .

Powyższy skrypt wygeneruje testy z grafami o różnej liczbie wierzchołków i krawędzi, zapisując je do plików z nazwami postaci   , uruchomi na nich nasz program i zapisze jego wynik do plików z rozszerzeniem  .

Zadania domowe

  • W jaki sposób spośród zbioru   liczb wylosować bez zwracania podzbiór    liczb?

Pokaż rozwiązanie

Wygeneruj losową permutację zbioru i weź z niej    pierwszych liczb.

  • Jak wygenerować losowy graf z  spójnymi składowymi?

Pokaż rozwiązanie

  1. Wygeneruj losową permutację.
  2. Podziel ją na   części (np. używając rozwiązania zadania 1. możesz wylosować   indeksów, które będą stanowić początki podzbiorów wierzchołków dla każdej ze składowych)
  3. Wygeneruj   losowych grafów, tak jak to robiliśmy wcześniej.

  • Jak wygenerować losowy string o długości  składający się z małych liter alfabetu łacińskiego  ?

Pokaż rozwiązanie

  1. Wylosuj  liczb z zakresu [0…25]
  2. Do każdej z nich dodaj ‚a’ i dołącz do tworzonego stringa.

 

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *

*