Umiejętność testowanie rozwiązań jest istotną częścią konkursów i bez jej opanowania trudno osiągnąć dobre wyniki w konkursach programistycznych. Umiejętność ta jest o tyle trudna w doskonaleniu, iż nie obowiązują tu ścisłe reguły, a jedyne co można polecić, to kilka poniższych rad i trening, trening, trening...

Jak zweryfikować poprawność rozwiązania?

1. Przypadki brzegowe - rozwiązanie powinno działać poprawnie dla wszystkich możliwych danych wejściowych, również tych minimalnych i maksymalnych (zwłaszcza ten ostatni przypadek bardzo często pojawia się w testach).
2. Odpowiednie typy zmiennych - chyba każdemu zdarzyło się kiedyś w swoim programie użyć zmiennych typu Integer (16-bitów), gdy konieczny był Longint (32-bity), czasami tego typu pomyłki mogą być bardzo bolesne, stąd warto poświęcić chwilę czasu na sprawdzenie, czy wszystkie zmienne są odpowiedniego typu.
3. Przygotowywanie testów - ograniczanie się do testowania poprawności jedynie na teście przykładowym nigdy nie przynosi dobrych efektów - zawsze warto przygotować chociaż 2-3 małe testy poprawnościowe. Przy generowaniu testów warto unikać zbędnych symetrii, czy uporządkowania danych (oczywiście jeśli warunki zadania tego nie wymagają). Jeśli tylko znajdzie się na to czas (o co zwykle trudno podczas konkursów), bardzo pożytecznym jest wygenerowanie dużych testów (np. z maksymalnym dopuszczalnym rozmiarem danych), oczywiście każdy test jest bezużyteczny, jeśli nie jest znana prawidłowa odpowiedź, stąd test powinien być tak skonstruowany, by "ręczne" obliczenie odpowiedzi było możliwe.
4. Często zawodnik staje przed dylematem, jakie rozwiązanie wybrać: szybkie, ale często dające niepoprawne odpowiedzi, czy wolne, ale dające gwarancję poprawności? Niestety nie ma na to pytanie uniwersalnej odpowiedzi, jednak bardzo często zdarza się, że dane testowe dokładnie wychwytują rozwiązania niepoprawne i takie rozwiązania otrzymują minimalne ilości punktów, natomiast rozwiązania poprawne zawsze (poza przypadkami patologicznymi) otrzymują punkty.
5. Odpowiednie nazwy plików - ten punkt jest oczywisty, ale w zamęcie spowodowanym przez konkurs łatwo o pomyłki, dobrze jest zawsze sprawdzić przed oddaniem rozwiązania, czy wszystkie pliki odpowiednio się nazywają.
6. Rozmiar danych - zazwyczaj w zadaniach podane są maksymalne rozmiary danych, np. maksymalna ilość wierzchołków w grafie. Wartości te często potem są wykorzystywane w wielu miejscach kodu, np. do indeksowania tablic, pętli itp. Stosowanie tych maksymalnych wartości explicite w każdym miejscu jest proszeniem się o kłopoty, o wiele czytelniej i bezpieczniej wygląda kod, w którym te wartości zapisane są jako stałe.
7. Kopie zapasowe - przed większymi zmianami w kodzie, lepiej zrobić kopię rozwiązania, dzięki temu zawsze będzie można wrócić do wersji oryginalnej.
8. Niektóre kompilatory udostępniają mechanizmy kontroli błędów, znakomicie ułatwiają one pisanie i testowanie rozwiązań. Jednak to co dobre podczas rozwiązywania zadania, wcale nie musi być dobre podczas oceniania - kontrola błędów wiąże się z dodatkowym narzutem czasowym na program i znakomicie spowalnia programy, w związku z czym przed oddaniem rozwiązania warto ją wyłączyć.
9. Technikalia - błędy nie zawsze muszą być skutkiem pomyłek programisty, czasami może to być wina samego narzędzia, jednak każdy jest odpowiedzialny za poznanie narzędzia, którego używa, jego dobrych cech, jak i również tych ciemniejszych. Ciemniejsze strony wcale nie muszą oznaczać błędów, czasami są to pewne cechy kompilatorów utrudniające życie programiście.

Jak ocenić efektywność rozwiązania?

1. Szacowanie - jeśli mamy daną złożoność rozwiązania, zawsze warto oszacować ilość operacji, których ono wymaga dla maksymalnych danych, np. algorytm o złożoności O(n³) dla n=1000, wymaga aż 1 000 000 000 operacji, co zazwyczaj oznacza czas wykonania rzędu kilku minut. Wybór granicy, od której można mieć wątpliwości, co do jakości rozwiązania, jest mocno związany z konkretnym zadaniem, jednak gdy z szacunków wynika, że rozwiązanie będzie wymagało grubo ponad 100 000 000 operacji, to przyszłość takiego rozwiązania rysuje się w czarnych barwach.
2. Testowanie - analiza złożoności rozwiązania jest dosyć często trudnym zadaniem, stąd w jej ocenie można posiłkować się testami (ale rozsądnie i z umiarem). Przygotowanie odpowiednich testów też nie jest trywialnym zadaniem, przypadki szczególne (np. graf pełny) wcale nie muszą oznaczać najgorszego przypadku, nawet testy losowe często okazują się niewystarczająco "złośliwe". Znalezienie testu, dla którego rozwiązanie działa wolno, stawia efektywność rozwiązania w wątpliwym świetle, jednak jeśli takie poszukiwania zakończą się porażką, to wcale nie musi oznaczać, że przy ocenianiu rozwiązania tego typu testy się nie znajdą ;-)
3. "Mierz siły na zamiary" - często spotykanym błędem jest zbytnie komplikowanie rozwiązań, wykorzystywanie zaawansowanych algorytmów do rozwiązywania prostych i małych problemów. Metody użyte w rozwiązaniach nie powinny być zbyt proste, ani zbyt skomplikowane, należy je tak dobrać, by działały odpowiednio dla maksymalnych danych z zadania, a nie np. 100 razy większych. Na przykład, gdy w rozwiązaniu trzeba w pewnym momencie posortować 10 elementową tablicę, wykorzystywanie do tego celu QuickSort'a nie jest zbyt ekonomiczne, równie dobrze (a właściwie nawet szybciej) poradzi sobie z tym problemem InsertionSort, którego implementacja jest znacznie prostsza.

Print friendly version