Archiwa tagu: przedwczesna optymalizacja

Konkursy algorytmiczne a przedwczesna optymalizacja

Z algorytmami mam trochę jak z grą w szachy. Lubię sobie czasem pogłówkować, ale nigdy nie wystarczyło mi wytrwałości, żeby przysiąść, poczytać, zapamiętać i wznieść się na naprawdę wysoki poziom. W przypadku algorytmów, na (moje) szczęście, do potraktowania sprawy poważniej w pewnym stopniu zmusiły mnie uczelnia i życie zawodowe.

Wspominałam już, że mam ostatnio więcej czasu niż zwykle. Mimo że mój tymczasowo zalany prolaktyną mózg ma problemy z obliczeniem należnej reszty przy zakupach, postanowiłam rozerwać się, rozwiązując zadania ze startujących właśnie Potyczek Algorytmicznych. Potyczki to otwarty konkurs programistyczny organizowany przez Uniwersytet Warszawski, w którym przez kilka dni rozwiązuje się zadania online, a na koniec najlepsi uczestnicy zapraszani są do rywalizacji w stacjonarnym finale.

W weekend zapoznałam się z zadaniami z rundy próbnej i przeżyłam nieprzyjemne zaskoczenie. Okazało się, że udostępniana uczestnikom konkursu sprawdzarka nie przeprowadza kompletu testów, ani nawet reprezentatywnego ich podzbioru. Zamiast tego, testuje program jedynie na jednym bądź dwóch prostych przykładach par wejście/wyjście podanych w treści zadania. Dopiero po zamknięciu danej rundy nadesłane przez uczestnika konkursu rozwiązanie jest poddawane całemu pakietowi testów.

Czy umknął mi jakiś nowy trend? Tego typu podejście to norma czy wyjątek?

Takie stawianie sprawy budzi mój głęboki opór, ponieważ, cytując klasyka:

Przedwczesna optymalizacja jest źródłem wszelkiego zła.

– Donald Knuth

Przedwczesna optymalizacja to (u)znany antywzorzec projektowy. Po pierwsze, problemy często leżą zupełnie nie tam, gdzie się ich spodziewamy. Po drugie, optymalizacja często zmniejsza czytelność kodu. Jeśli nie jest potrzebna (program w oryginalnej wersji wykonuje się w czasie w zupełności akceptowalnym dla klienta), prowadzi do samych problemów, jak dodatkowe godziny pracy następnego programisty, który musi utrzymywać nieintuicyjnie napisany kod. Po trzecie wreszcie, jeśli nie zdefiniujemy granicy, optymalizować można właściwie w nieskończoność, lub przynajmniej do poziomu operacji na bitach.

Czy o to powinno chodzić w konkursie algorytmicznym? Rozumiem, że TDD (programowanie sterowane testami) dominuje w „przemyśle”, a konkursy rządzą się swoimi prawami, ale nie wydaje mi się dobrym pomysłem stawianie ich w takiej opozycji do dobrych praktyk.

PS. Smaczku całej sprawie dodaje fakt, że, przynajmniej w przypadku zadań próbnych, nie podano limitu czasowego, który obowiązuje w automatycznych testach…

PS2. Wykres w nagłówku w oryginalnej wersji był opisany, ale ostatecznie postanowiłam zamienić go na tematyczną zagadkę. Stawiam piwo pierwszej osobie, która poda pełne opisy X, Y, K i E 🙂