Podejście TDD do problemów algorytmicznych

Jeden z nich nie zdał testu algorytmicznego z Codility, ponieważ próbowałem znaleźć lepsze rozwiązanie, a ostatecznie nie miałem nic.

Więc pomyślałem, czy mógłbym zastosować podejście podobne do TDD? Tj. Czy zazwyczaj mogę stopniowo opracować rozwiązanie w podobny sposób?

Gdybym pisał algorytm sortowania, mógłbym przejść ze standardowego Bubblesorta do dwukierunkowego bąbelkowego sortowania, ale wtedy coś bardziej zaawansowanego jak Quicksort byłoby „skokiem kwantowym”, ale przynajmniej miałbym dane testowe, które mógłbym łatwo zweryfikować.

Inne wskazówki dotyczące takich testów? Następną rzeczą, którą zrobiłbym następnym razem, było użycie większej liczby metod / funkcji niż pętli wewnętrznych. Na przykład podczas sortowania często potrzebujesz wymiany. Gdyby to była metoda, musiałbym tylko zmodyfikować kod wywołujący. Mógłbym nawet mieć bardziej zaawansowane rozwiązania jako klasy pochodne.

Z problemami „algorytmicznymi” a „normalnymi” mam na myśli problemy, w których złożoność czasu jest ważna. Zamiast więc przechodzić więcej testów jak w TDD, sprawiłbyś, że „zachowuje się lepiej”.

Przez „podobny do TDD” mam na myśli:

1. Napisz stosunkowo automatyczny test, aby zaoszczędzić czas na ręcznych testach przyrostowych.
2. Rozwój przyrostowy.
3. Testowanie regresji, możliwość wykrycia, czy kod się psuje, a przynajmniej, jeśli funkcjonalność zmienia się między przyrostami.

Myślę, że to powinno być dość łatwe do zrozumienia, jeśli porównasz

1. Bezpośrednie pisanie sortowania powłoki
2. Skakanie z bąbelkowego do szybkiego (całkowite przepisanie)
3. Przechodzenie przyrostowe z jednokierunkowego sortowania bąbelkowego do sortowania skorupowego (jeśli to możliwe).

Zobacz także próbę Ron Jeffriesa, aby stworzyć solver Sudoku z TDD , co niestety nie zadziałało.

Algorytm wymaga znacznego zrozumienia zasad projektowania algorytmów. Dzięki tym zasadom rzeczywiście można postępować stopniowo, zgodnie z planem, tak jak zrobił to Peter Norvig .

W rzeczywistości w przypadku algorytmów wymagających nie trywialnego wysiłku projektowego prawie zawsze wysiłek ma charakter przyrostowy. Ale każdy „przyrost”, który jest niewielki w oczach projektanta algorytmu, wygląda jak skok kwantowy (aby pożyczyć frazę) osobie, która nie miała takiej samej wiedzy specjalistycznej lub wiedzy w tej szczególnej rodzinie algorytmów.

Dlatego tak samo ważna jest podstawowa edukacja z teorii CS w połączeniu z dużą ilością praktyki programowania algorytmów. Wiedza, że ​​istnieje szczególna „technika” (małe elementy składowe algorytmów), jest długą drogą do dokonania tych skokowych skoków kwantowych.

Istnieją jednak pewne ważne różnice między przyrostowym postępem w algorytmach a TDD.

Jedną z różnic wspomniano w JeffO : Test weryfikujący poprawność danych wyjściowych jest odrębny od testu, który potwierdza wydajność między różnymi implementacjami tego samego algorytmu (lub różnymi algorytmami, które starają się uzyskać to samo rozwiązanie).

W TDD dodaje się nowy wymóg w postaci testu, który to test początkowo nie powinien przejść (czerwony). Następnie wymaganie jest spełnione (kolor zielony). Na koniec kod jest refaktoryzowany.

W rozwoju algorytmu wymaganie zwykle się nie zmienia. Test weryfikacji poprawności wyników jest albo zapisywany jako pierwszy, albo wkrótce po zakończeniu szkicowej (bardzo pewnej, ale powolnej) implementacji algorytmu. Ten test poprawności danych jest rzadko zmieniany; nie zmienia się go w błąd (czerwony) w ramach rytuału TDD.

Jednak w tym aspekcie analiza danych wyraźnie różni się od rozwoju algorytmu, ponieważ wymagania analizy danych (zarówno zestawy danych wejściowych, jak i oczekiwane wyniki) są zdefiniowane tylko luźno w ludzkim rozumieniu. Zatem wymagania często zmieniają się na poziomie technicznym. Ta szybka zmiana stawia gdzieś analizę danych między opracowaniem algorytmu a ogólnym opracowaniem aplikacji - mimo że wciąż jest on obciążony algorytmem, wymagania zmieniają się również „zbyt szybko” na gust dowolnego programisty.

Jeśli wymaganie się zmienia, zwykle wymaga innego algorytmu.

W rozwoju algorytmu zmiana (zaostrzenie) testu porównania wydajności na niepowodzenie (czerwony) jest głupia - nie daje żadnego wglądu w potencjalne zmiany w algorytmie, które mogłyby poprawić wydajność.

Dlatego w rozwoju algorytmu zarówno test poprawności, jak i test wydajności nie są testami TDD. Zamiast tego oba są testami regresji . W szczególności test regresji poprawności zapobiega wprowadzaniu zmian w algorytmie, które zepsują jego poprawność; test wydajności zapobiega wprowadzaniu zmian w algorytmie, które spowodują jego wolniejsze działanie.

Nadal możesz włączyć TDD jako osobisty styl pracy, z tym wyjątkiem, że rytuał „czerwony - zielony - refaktor” nie jest absolutnie konieczny ani szczególnie korzystny dla procesu myślenia algorytmicznego.

Argumentowałbym, że ulepszenia algorytmu faktycznie wynikają z tworzenia losowych (niekoniecznie poprawnych) permutacji na diagramach przepływu danych bieżącego algorytmu lub mieszania i dopasowywania ich między poprzednimi implementacjami.

TDD jest używane, gdy istnieje wiele wymagań, które można stopniowo dodawać do zestawu testowego.

Alternatywnie, jeśli algorytm jest oparty na danych, każdy fragment danych testowych / przypadków testowych można dodawać przyrostowo. Przydałby się również TDD. Z tego powodu „podobne do TDD” podejście „dodawania nowych danych testowych - poprawiania kodu, aby poprawnie obsługiwał te dane - refaktoryzacja” będzie również działać w przypadku otwartej analizy danych, w której cele algorytmów są opisane u ludzi -centryczne słowa i ich miara sukcesu są również oceniane w kategoriach zdefiniowanych przez człowieka.

Ma na celu nauczyć sposób, aby uczynić go mniej przytłaczającym niż próba spełnienia wszystkich (dziesiątek lub setek) wymagań za jednym razem. Innymi słowy, TDD jest włączone, gdy możesz dyktować, że niektóre wymagania lub cele rozciągania mogą być tymczasowo ignorowane podczas wdrażania wczesnych wersji roboczych twojego rozwiązania.

TDD nie zastępuje informatyki. Jest kulą psychologiczną, która pomaga programistom pokonać szok związany z koniecznością spełnienia wielu wymagań naraz.

Ale jeśli masz już jedną implementację, która daje poprawny wynik, TDD uzna, że ​​jej cel został osiągnięty, a kod będzie gotowy do przekazania (do refaktoryzacji lub do innego użytkownika programisty). W pewnym sensie zachęca cię do nieoptymalizowania kodu przedwcześnie, poprzez obiektywny sygnał, że kod jest „wystarczająco dobry” (aby przejść wszystkie testy poprawności).

W TDD skupiono się również na „mikro-wymaganiach” (lub ukrytych cechach). Na przykład sprawdzanie poprawności parametrów, asercje, zgłaszanie wyjątków i obsługa itp. TDD pomaga zapewnić poprawność ścieżek wykonywania, które nie są często wykonywane w normalnym toku wykonywania oprogramowania.

Niektóre typy kodu algorytmu również zawierają te rzeczy; podlegają one TDD. Ponieważ jednak ogólny przebieg pracy algorytmu nie jest TDD, takie testy (dotyczące sprawdzania poprawności parametrów, asercji oraz zgłaszania wyjątków i obsługi) mają tendencję do pisania po napisaniu (przynajmniej częściowo) kodu implementacyjnego.

W przypadku Twojego problemu masz dwa testy:

1. Test mający na celu sprawdzenie, czy algorytm jest nadal dokładny. np. czy jest poprawnie posortowany?
2. Test porównania wydajności - poprawił wydajność. Może to być trudne, więc pomaga uruchomić test na tym samym komputerze, tych samych danych i ograniczyć użycie innych zasobów. Specjalna maszyna pomaga.

Co do przetestowania lub pełny zakres testów jest dyskusyjny, ale myślę, że złożone części aplikacji, które wymagają dopracowania (bardzo często zmieniane), są idealnymi kandydatami do testów automatycznych. Te części aplikacji są zwykle identyfikowane bardzo wcześnie. Zastosowanie podejścia TDD w tym kawałku miałoby sens.

Zdolność do rozwiązywania złożonych problemów nie powinna być utrudniona przez niechęć do próbowania różnych podejść. Posiadanie automatycznego testu powinno pomóc w tym zakresie. Przynajmniej będziesz wiedział, że nie pogarszasz tego.

Zamiast więc przechodzić więcej testów jak w TDD, sprawiłbyś, że „zachowuje się lepiej”.

Raczej.

Możesz przetestować czas działania i złożoność. Testy wykonawcze będą musiały być trochę wybaczające, aby umożliwić rywalizację o zasoby systemowe. Ale w wielu językach można również zastępować lub wprowadzać metody i liczyć rzeczywiste wywołania funkcji. A jeśli masz pewność, że Twój obecny algorytm nie jest optymalny, możesz wprowadzić test, który po prostu wymaga, aby sort()wywołać go compare()mniej razy niż naiwna implementacja.

Lub możesz porównać sort()na dwóch zestawach i upewnić się, że skalują się one w compare()połączeniach według docelowej złożoności (lub w innych miejscach, jeśli oczekujesz pewnej niespójności).

A jeśli teoretycznie możesz udowodnić, że zestaw rozmiarów Npowinien wymagać wyłącznie N*log(N)porównań, rozsądne może być ograniczenie już działającej pracy sort()do N*log(N)wywołań compare()...

Jednak ...

Spełnienie wymagań dotyczących wydajności lub złożoności nie gwarantuje, że podstawową implementacją jest {AlgorytmX} . I twierdzę, że jest to normalnie OK. Nie powinno mieć znaczenia, jaki algorytm jest używany, pod warunkiem, że trafienie implementacji spełnia wymagania, w tym wszelkie ważne wymagania dotyczące złożoności, wydajności lub zasobów.

Ale jeśli chcesz upewnić się, że używany jest określony algorytm, musisz być bardziej nużący i uzyskać więcej informacji. Rzeczy jak..

• Zapewnienie wykonania dokładnie oczekiwanej liczby połączeń compare()i swap()(lub cokolwiek)
• Zawijanie wszystkich głównych funkcji / metod i zapewnianie, z przewidywalnym zestawem danych, że wywołania będą występować w dokładnie oczekiwanej kolejności
• Badanie stanu pracy po każdym z N kroków, aby upewnić się, że zmieniło się dokładnie zgodnie z oczekiwaniami

Ale znowu, jeśli próbujesz upewnić się, że w szczególności używany jest {AlgorytmX} , prawdopodobnie są to funkcje {AlgorytmX}, na których zależy ci, które są ważniejsze w testowaniu niż to, czy {AlgorytmX} faktycznie został użyty w końcu ...

Należy również pamiętać, że TDD nie neguje konieczności badania, myślenia lub planowania rozwoju oprogramowania. Nie neguje to również potrzeby burzy mózgów i eksperymentów, nawet jeśli nie możesz łatwo stwierdzić na swoim Googlingu i tablicy w swoim zautomatyzowanym zestawie testów.