Testowanie programów III: valgrind i time

Dziś opowiemy o dwóch przydatnych narzędziach podczas debugowania – valgrind i time.

valgrind

Narzędzia valgrind używamy, gdy nasz program nie kończy się poprawinie lub dostajemy RTE (Runtime Exception) na sprawdzaczce. Powiem nam ono, w której linijce wychodzimy poza tablicę, odwołujemy się do miejsca spoza przydzielonej pamięci, dzielimy przez zero itp. Przypuśćmy, że mamy taki kod:

Jeśli go skompilujemy i uruchomimy, program zakończy się z błędem „Segmentation fault”. Jak zlokalizować, w której linijce jest błąd?

Kompilujemy nasz program z flagą -g, doda ona do pliku binarnego informacje pomocne przy debugowaniu.

lub

Uruchamiamy program z narzędziem valgrind:

 (gdy chcemy wprowadzić dane wejściowe, uruchamiamy tak:   )

valgrind uruchomi nasz program wyświetlając wszystkie napotkane błędy:

Poniższe frazy świadczą o tym, że błąd tkwi w linijce 18 w pliku program.cpp.

Wychodzimy w niej poza przydzieloną pamięć:

I rzeczywiście, po chwili zastanowienia dochodzimy do wniosku, że powinna wyglądać ona tak:

/usr/bin/time

Za pomocą narzędzia /usr/bin/time możemy zmierzyć, ile czasu i pamięci zużywa nasz program na dowolnym teście. Robimy to tak:

UWAGA! Pamiętajmy, żeby wpisać   zamiast tylko   . Ta druga komenda mierzy tylko czas. Flaga  również jest bardzo ważna, bez niej output narzędzia będzie średnio czytelny.

Powinniśmy dostać coś takiego:

Z linijek:

możemy wywnioskować, że wykonanie programu zajęło 10.4 sekundy i program potrzebował ok. 10.5MB pamięci. Podane wartości (zwłaszcza dla pamięci) mogą nie być w 100% zgodne ze sprawdzarką, jednak stanowią dość dobre przybliżenie.

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.

 

Testowanie programów I: Podstawy

Bardzo rzadko zdarza się, że kod, który napisaliśmy działa za pierwszym uruchomieniem. Często testowanie programów i znajdowanie w nich błędów to żmudny i czasochłonny proces. Dziś pokażemy, jak sprawić, by trwał on jak najkrócej.

Zadanie

Mamy za zadanie napisać program, który sortuje podany ciąg liczb. Ponieważ rozwiązywanie tego problemu nie jest dzisiaj naszym celem, wyobraźmy sobie, że wpadliśmy na pomysł, by zaimplementować algorytm bąbelkowy i nasz kod wygląda teraz jakoś tak:

Jeśli niektóre z użytych poleceń są dla Ciebie nie jasne, koniecznie przeczytaj ten wpis.

Zanim wyślemy kod na sprawdzarkę, chcemy go przetestować. Pamiętaj o najważniejszej zasadzie przy rozwiązywaniu zadań:

Nigdy nie wysyłaj nieprzetestowanego kodu!

Jak to zrobić? Najprostszym wyjściem jest uruchomienie programu i wprowadzenie testu ręcznie. Sposób ten, o ile jest rzeczywiście prosty, o tyle w przypadku większego testu jest strasznie nieefektywny – wyobraź sobie chociażby sytuację, gdy testujesz program na ciągu zawierający 10 liczb i program zwrócił złą odpowiedź. Poprawiłeś jedną linijkę i chcesz sprawdzić, czy kod już jest poprawny. Musisz wpisywać cały ciąg od początku.

Testowanie z pliku

Istnieje dużo efektywniejszy sposób. Żeby nie wpisywać testów za każdym razem, zapiszmy go do pliku w folderze, w którym znajduje się kod. Następnie uruchomimy program z przekierowanym wejściem – z klawiatury do pliku. Nasz kod będzie myślał, że wczytuje dane z klawiatury a tak naprawdę będzie pobierał je z wcześniej przygotowanego pliku.

No dobra, ale jak to zrobić? Otwórz terminal/wiersz poleceń (ctrl+alt+T na Linuksie lub ‚cmd’ w polu Uruchom na Windowsie) i postępuj zgodnie z instrukcjami na filmiku:

OK, jeszcze raz, co tutaj się wydarzyło. W terminalu przeszliśmy do katalogu z plkiem źródłowym. Skompilowaliśmy program (Ty możesz to uczynić w programie z interfejsem graficznym, jak Dev-C++ czy Codeblocks), następnie stworzyliśmy plik tekstowy w folderze z kodem (tutaj również możesz użyć dowolnego programu) i uruchomiliśmy program, tak by wczytywał dane z pliku. Komenda wygląda tak (na Windowsie):

nazwa_programu.exe < plik_z_testem.txt

Oczywiście jeden test to za mało, by przekonać się, czy program na pewno działa poprawnie. Spróbuj wymyślić kilka innych i przetestować program w podobny sposób (zapisując test do pliku). Wróć tutaj, gdy znajdziesz test, na którym nasz kod zwraca zły wynik.

Wyświetlanie pomocniczych wartości

Już? OK. Rzeczywiście nasz program nie działa najlepiej. Oto przykładowy test, na którym program się myli:

Program zwraca:

Co teraz? Jeśli nie potrafimy znaleźć błędu patrząc tylko na kod, warto coś wypisać i sprawdzić, co nasz program robi krok po kroku. W tym przypadku wypiszmy pośrednie wyniki sortowania po każdym obrocie zewnętrznej pętli w funkcji sortuj(). Teraz nasza funkcja wygląda tak:

Zwróć uwagę na jedną rzecz: zamiast wypisywać na ekran poleceniem cout my używamy cerr. Jaka jest różnica między nimi? cerr (skrót do console-error) wypisuje tekst na tzw. standardowe wyjście błędów (standard error). Wizualnie nie zauważysz żadnych zmian, ale to polecenie ma jedną główną przewagę nad cout, z której skorzystamy – sprawdzarki kompletnie ignorują to, co wypisujesz za pomocą cerr. Zatem, gdy już znajdziesz wszystkie błędy i zdarzy ci się zapomnieć zakomentować linii wypisujących pomocniczy tekst za pomocą cerr, nie otrzymasz komunikatu Wrong Answer z tego powodu.

OK, sprawdźmy co wypisuje teraz nasz program:

Wychodzi na to, że pierwsze dwie liczby posortował poprawnie i dopiero z trzecią (2) ma problem. Dwójka powinna wylądować na początku ciągu 2 – 3 – 4 a jest w środku (trzecia linia). Dowiedzmy się dlaczego, tak się dzieje. Wypiszmy liczby, które aktualnie są porównywane. Kod funkcji wygląda teraz tak:

A program wypisuje:

Naszą uwagę przykuwa linijka:

Porównywanie dwóch tych samych liczb nigdy nie powinno się zdarzyć, skoro wszystkie liczby w naszym ciągu są różne. Szybki rzut oka na kod i widzimy, że zamiast porównywać:

My porównujemy:

Poprawiamy kod (2 linijki – jedną z ifem, drugą z wypisywaniem) i odpalamy kod raz jeszcze. Jeśli nie zamknąłeś terminala, wciśnij strzałkę do góry. Powinieneś zobaczyć poprzednio wpisane polecenie. To kolejna zaleta używania terminala.

Wszystko jest w porządku. Kod zwraca posortowany ciąg. Możesz usunąć teraz linijki z pomocniczym outputem (cerr) i spróbować wysłać program na sprawdzarkę. O, chociażby do tego problemu.

To wszystko na dziś. Warto jednak postawić sobie pytanie, czy przetestowanie kodu na kilku prostych testach jest wystarczające. Oczywiście, że nie. W ogóle nie sprawdziliśmy, jak nasz program radzi sobie w przypadku długich ciągów i czy jest dostatecznie szybki, by przejść limity czasowe. O tym porozmawiamy w drugiej części tego tutoriala, która już niebawem.

Szablon rozwiązania

Gdy przystępujesz do pisania kodu, zwykle rozpoczynasz od pewnego „szkieletu”, który pewnie wygląda jakoś tak:

Ale czy na pewno wiesz, do czego służy każda z linijek? Wyjaśnimy sobie co oznaczają poszczególne instrukcje:

#include <bits/stdc++.h> – plik nagłówkowy, którego możesz używać zamiast <iostream>, zawiera praktycznie wszystkie biblioteki, które będą ci potrzebne.

using namespace std; – w większych systemach często dochodzi do kolizji, gdy dwa różne obiekty posiadają tę samą nazwę i kompilator nie wie, którą wybrać. By temu zaradzić wprowadzono tzw. “przestrzenie nazw” (namespace). W C++ każdy obiekt oprócz tego że ma swoją nazwę jest również w pewnej przestrzeni i odnosimy się do niego tak:

nazwa_przestrzeni::nazwa_obiektu.

Strumienie cout i cin pochodzące z biblioteki standardowej (standard library) zawarte są w przestrzeni “std”, zatem musimy odnosić się do nich tak:

std::cout i std::cin

W mniejszych programach jest to dość niewygodne, więc możemy ustawić którą przestrzeń będziemy używać jako domyślną. Ta linijka właśnie do tego służy. Dzięki niej możesz opuścić przedrostek std:: i pisać po prostu tak:

cin >> n;

ios_base::sync_with_stdio(0) – w C++ możemy wczytywać/wypisać dane na dwa sposoby:

  • printf(…) i scanf(…) – za pomocą funkcji pochodzących z języka C lub
  • cout << … i cin >> … – strumieni wprowadzonych w C++

Niektóre programy używają obu tych sposobów na zmianę (tak jest np. w większych systemach, gdzie różne moduły są pisane przez różnych ludzi na przestrzeni lat). Potrzebna jest wtedy synchronizacja między nimi tak, by mogły działać naprzemiennie (w przeciwnym wypadku mogłoby się zdarzyć, że jedna funkcja wczyta pierwsze pół wyrazu a druga pozostałe pół, tego byśmy nie chcieli). Minusem używania synchronizacji jest to, że spowalnia ono wczytywanie/wypisywanie – za każdym razem system musi sprawdzać, czy może wczytywać/pisać na ekran. Synchronizacja jest włączona domyślnie. Do naszych zastosowań jednak zupełnie nie jest potrzebna, piszemy bowiem krótkie programy, używając tylko jednego ze sposobów. Powyższa linijka wyłącza synchronizację i przyspiesza działanie programu. Używaj jej zawsze, jeśli korzystasz z cout << … i cin >> ….

return 0; – każda funkcja musi coś zwracać, również main. 0 informuje, że program zakończył się bez błędów.

 

Komunikaty serwera

Gdy wyślemy plik z kodem, po kilku sekundach zostanie on skompilowany na serwerze i poddany testom. Każdy test to jeden plik z danymi wejściowymi. Żeby program mógł przejść test z sukcesem, musi wypisać dokładnie to samo, co program wzorcowy napisany przez autorów zadania. Zazwyczaj pod treścią znajdują się tzw. testy przykładowe. Składają się z dwóch rzeczy – pola Input (wejścia programu) i pola Output (odpowiedzi). Zanim wyślesz kod na sprawdzarkę koniecznie przetestuj, czy twój program zwraca (wypisuje na ekran) dokładnie to, co powinien na każdym teście przykładowym. Spróbuj również wymyślić kilka swoich, by mieć pewność, że program na pewno działa poprawnie.

Po zakończeniu sprawdzania, serwer zwraca jeden z poniższych komunikatów:

Compilation error (Błąd kompilacji) — kod nie kompiluje się. Możliwe są trzy scenariusze: masz drobny błąd w kodzie, musisz przekompilować u siebie i poprawić go, wysłałeś zły plik (wysyłamy plik .cpp z kodem źródłowym) lub wybrałeś zły kompilator (dla języka C++ wybierz GNU G++11 lub 14). Czasem (bardzo rzadko) zdarza się, że kod kompiluje się u nas lokalnie a na serwerze już nie. Warto wtedy sprawdzić podany komunikat błędu (np. na Codeforces jest dostępny po kliknięciu na “Compilation error”). Jeśli dalej nie wiesz, co jest przyczyną błędu, napisz na forum.

Wrong answer on test X (Zła odpowiedź na teście #X) — twój program zwraca zły wynik na teście X, tzn. że po wpisaniu danych wejściowych twój program podał złą odpowiedź (niepoprawną liczbę, niepoprawne słowo lub dodatkowe, niepotrzebne znaki). Pamiętaj: dla wejścia podanego w treści zadania w polu Input twój program musi wypisać na ekran dokładnie to, co znajduje się w polu Output! Nie wypisujemy żadnych dodatkowych tekstów typu “Podaj liczbę:”, “Oto wynik:” itp.

Time limit exceeded on test X (Przekroczony limit czasu na teście #X) — kod działa za wolno. Program musi kończyć się na każdym teście po najwyżej kilku sekundach (konkretne limity podane są w opisie zadania). Spróbuj przetestować go na największych możliwych danych wejściowych (dla największych liczb, jakie mogą zostać podane, każda liczba ma swoje “widełki”, które możesz znaleźć w treści zadania).

Runtime error on test #X (Błąd wykonania na teście #X) — twój program nie kończy się poprawnie, “crashuje się” w trakcie działania (np. z powodu wyjścia poza tablicę, podzielenia przez zero itp.). Spróbuj przetestować swój kod na “brzegowych przypadkach”, np. ciągu o długości 1 (jeśli w zadaniu wczytujesz ciąg liczb), najmniejszych i największych limitach dla każdej ze zmiennej.

Memory limit exceeded #X (Przekroczony limit pamięci #X) — twój program zużywa za dużo pamięci. Upewnij się, że tworzysz tablice o dozwolonych rozmiarach. Łączna ich długość nie powinna przekraczać limitu podanego w treści zadania, dla przykładu: jeśli tworzysz 5 tablic typu int o długości milion zużywasz 5 milionów * 4 bajty = 20 megabajtów. Błąd ten może powodować też nieskończona rekurencja – jeśli limit pamięci jest dość niski, szybciej skończy się pamięć niż czas.

Presentation error on test #X (Błąd formatowania na teście #X) — zdarza się tylko w starszych wersjach sprawdzarek, przez nowsze ten błąd jest ignorowany. Oznacza, że twój output nie jest poprawnie sformatowany: zawiera niepoprawnie wstawione spacje lub puste linie.

Accepted — brawo. Rozwiązałeś zadanie 🙂