Testowanie programów IV: „brut” i „wzorcówka”

Potrafimy już generować losowe testy dla naszych programów. Wykorzystajmy zdobytą dotychczas wiedzę do przetestowania naszego rozwiązania wzorcowego. Jednakże zanim zabierzemy się do pracy, zadajmy sobie następujące pytanie: czy kod rozwiązania brutalnego jest prostszy od kodu rozwiązania wzorcowego? Odpowiedź brzmi: tak.

Aby stworzyć rozwiązanie optymalne, musimy posługiwać się wieloma różnymi algorytmami, przy których zaklepywaniu możemy popełnić rozmaite błędy. Przy wyszukiwaniu binarnym możemy zapętlić się w nieskończoność; przy używaniu dodatkowej tablicy do zliczania elementów, możemy wyjść poza tę tablicę (zliczanie elementów o wartości wyższej niż rozmiar tablicy do zliczania), itd. Skoro przekonaliśmy się, że rozwiązanie brutalne jest na ogół prostsze, to czy można to jakoś wykorzystać?

Do testowania wzorcówki (rozwiązania wzorcowego) wykorzystajmy bruta (rozwiązanie brutalne). W jaki sposób? Uruchommy bruta oraz wzorcówkę na tych samych testach. Testy generujemy losowo tak, jak wcześniej się nauczyliśmy. Postępując w ten sposób otrzymamy wyniki osobno dla rozwiązania brutalnego i osobno dla rozwiązania. Otrzymane wyniki porównujemy ze sobą. Jeżeli dla któregoś testu wyniki się różnią, to na pewno co najmniej jedno z naszych rozwiązań jest błędne. Istnieje duża szansa, że błędnym rozwiązaniem jest tylko wzorcówka (dlatego, że jest trudniejsza do zaklepania). Analizujemy, dlaczego dla danego testu otrzymaliśmy dwa różne wyniki i staramy się znaleźć błąd w naszym programie. Jeśli wiemy już na czym polega testowanie wzorcówki za pomocą bruta, to przetestujmy wzorcówkę do poniższego ćwiczenia.

Ćwiczenie

Na kartce zapisano n liczb: t[1], t[2]…t[n]. Otrzymujesz q pytań. Każde pytanie to para liczb: a, b (a <= b), co oznacza: jaka jest suma liczb od elementu o numerze a do elementu o numerze b.

Wejście

n – ilość liczb zapisanych na kartce
t[1], t[2],…,t[n] – liczby zapisane na kartce
q- liczba pytań
a, b- pytanie: suma liczb od elementu o numerze a do elementu o numerze b

Wyjście

res[1], res[2], …,res[q] – odpowiedzi na pytania

Wyjście

1 <= n, q, a, b <= 1 000 000
1 <= t[1], t[2],…,t[n] <= 1 000 000 000

 

Testowanie rozwiązań

Aby przetestować wzorcówkę przy użyciu bruta, potrzebujemy:

  1. testowanej wzrocówki
  2. bruta do testowania
  3. programu generującego testy
  4. skryptu obsługującego trzy powyższe programy (skrypt testujący)

UWAGA!!!!!
1) Wszystkie cztery pliki muszą znajdować się w jednym folderze.
2) Skrypt obsługujący programy piszemy w bashu, więc aby sprawdzić testowanie rozwiązań na swoim komputerze, potrzebujesz Linuxa.

Wzorcówka

Rozwiązanie wzorcowe korzysta z sum prefiksowych, dzięki czemu możemy osiągnąć złożoność liniową.

 

Brut

Program dla każdego zapytania iteruje się maksymalnie przez całą tablicę, więc działa w czasie kwadratowym.

 

 

Program generujący testy

Zastanówmy się nad tym, w jaki sposób ma działać ten program?

  1. W konsoli muszę mieć możliwość podania wartości dla trzech zmiennych: n, min_t, max_t, q czyli: ilość w liczb w generowanej tablicy,  zakres losowanych wartości generowanej tablicy oraz liczba zapytań.
  2. Wypisuję liczbę n.
  3. Dla komórek tablicy t od 1. do n. elementu losuję wartość od min_t do max_t.
  4. Wypisuję zawartość tablicy t.
  5. Wypisuję q.
  6. Wykonaj kroki 7,  8. oraz 9. q razy.
  7. Losuję dla zmiennej a wartość od 1 do n.
  8. Losuję dla zmiennej b wartość od a do n.
  9. Wypisz a oraz b.

Oto nasz program:

UWAGA!!!
Jeżeli nie rozumiesz któreś linijki kodu, koniecznie zajrzyj tu.

 

Skrypt testujący

Skrypt napisany jest w bashu (języku Linuxa; rozszerznie:  .sh). Działa w następujący sposób:

  1. Wygeneruj plik tekstowy z testem (inputem).
  2. Odpal test na brucie i zapisz jako wynik dla bruta.
  3. Odpal test na wzorcówce i zapisz jako wynik dla wzorcówki.
  4. Porównaj oba wynik, jeśli te się różnią, to wypisz je w konsoli (za pomocą diff).
  5. Powyższe operacje wykonaj łącznie c razy.

Oto skrypt:

Jeżeli skompilowałeś wszystkie trzy programy, możesz wpisać do konsoli:

Jeżeli nie masz uprawnień, wpisz jeszcze do konsoli:

Twoim oczom powinno się w konsoli ukazać coś takiego:

W pierwszej linijce każdego testu widzisz wynik dla bruta, a w drugiej linijce dla wzorcówki. W przypadku, gdy wyniki są identyczne, nie są one wyświetlane (w ten sposób działa diff). Teraz postaraj się już samodzielnie odnaleźć błąd we wzorcówce 🙂

Dodaj komentarz

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

*