Jednym z zagadnień należących do zakresu pracy programisty jest rozwiązywanie różnego rodzaju problemów, wśród nich znajduje się optymalizacja algorytmów.

Problemy tego typu polegają na tym, że mamy do zaimplementowania pewną funkcjonalność, która musi działać w określonych warunkach, określonym czasie i spełniać zadane założenia. Zatem nie wystarczy że coś działa, musi to też działać odpowiednio szybko i bez nadmiernego zużywania zasobów.

Prosty przykład

Załóżmy że mamy wskazówkę, która obraca się wokół tarczy zawsze o 90 stopni w prawo.

Początkowe położenie to 0 stopni.

Naszym zadaniem jest napisanie funkcji, która określa w jakim położeniu znajdzie się wskazówka po określonej liczbie obrotów.

Najprostsza implementacja takiej funkcji może wyglądać następująco:

function rotate(int times): int
{
    int result = 0;
    for (int i = 0; i < times; i++) {
        result = result + 90;


        if (result === 360) {
            result = 0;
        }
    }

    return result;
}

W funkcji mamy wartość początkową 0 i pętlę, która w każdym kroku dodaje wartość 90, a jeśli wartość osiągnie 360 zamieniana jest na 0 (pełny obrót). Funkcja taka z pewnością zadziała i da oczekiwany rezultat, ale czy wykona się ona w możliwie najkrótszym czasie? Czas wykonania będzie uzależniony od ilości obrotów (argument int times). 

Poszukajmy lepszego rozwiązania

Poszukiwanie najlepszych rozwiązań problemu powinniśmy zacząć od ustalenia pewnych założeń, które nie zawsze są zdefiniowane w zadaniu lub są zdefiniowane między wierszami.

W naszym przykładzie możemy łatwo zauważyć, że wskazówka może mieć tylko 4 położenia: 0, 90, 180, 270 i położenia te są cykliczne, czyli np. dla wartości times =  10 będziemy mieć kolejno położenia:

Pierwszy obrót: 90

Drugi obrót: 180

Trzeci obrót: 270

Czwarty obrót: 0

Piąty obrót: 90

Szósty obrót: 180

Siódmy obrót: 270

Ósmy obrót: 0

Dziewiąty obrót: 90

Dziesiąty obrót: 180

Jak widać nasz rezultat, którym jest 180, pojawił się trzykrotnie, w obrotach: drugim, szóstym i dziesiątym, czyli ta sama wartość pojawia się co cztery razy. Wynika to stąd że mamy tylko cztery możliwe wartości. Nasz algorytm możemy więc zoptymalizować, ustalając kiedy pojawi się po raz pierwszy oczekiwana przez nas wartość i po jej ustaleniu przerwać pętlę, zwracając wartość. Przydatne tutaj będzie działanie modulo czyli dzielenie bez reszty. Proszę zauważyć, że każdy numer cyklu podzielony bez reszty przez ilość dostępnych wartości (4) daje cyklicznie te same wyniki:

Pierwszy obrót: 1 % 4 = 1

Drugi obrót: 2 % 4 = 2

Trzeci obrót: 3 % 4 = 3

Czwarty obrót: 4 % 4 = 0

Piąty obrót: 5 % 4 = 1

Szósty obrót: 6 % 4 = 2

Siódmy obrót: 7 % 4 = 3

Ósmy obrót: 8 % 4 = 0

Dziewiąty obrót: 9 % 4 = 1

Dziesiąty obrót: 10 % 4 = 2

Interesujący nas, dziesiąty cykl zwraca wartość 2, taka wartość pierwszy raz pojawia się w cyklu drugim, więc już wtedy możemy zwrócić szukaną przez nas wartość. Nasza funkcja może więc wyglądać tak:

function rotate(int times): int
{
    int result = 0;
    int expectedModulo = times % 4;


    for (int i = 0; i < times; i++) {
        result = result + 90;


        if (result === 360) {
            result = 0;
        }

        if (i % 4 == expectedModulo) {
            break;
        }
    }

    return result;
}

Czy już jest dobrze?

Funkcja kończy się dużo szybciej, ponieważ przerywa pętlę po znalezieniu pierwszego wystąpienia poszukiwanej przez nas wartości. Czy ta funkcja jest już jednak możliwie najlepiej zoptymalizowana? Czy w ogóle potrzebujemy w niej pętli?

Wracając do przedstawionych wcześniej list wyników i modulo po każdym obrocie zauważymy, że łatwo można powiązać modulo uzyskane w każdym cyklu z odpowiednim wynikiem:

Pierwszy obrót: 1 => 90

Drugi obrót: 2 => 180

Trzeci obrót: 3 => 270

Czwarty obrót: 0 => 0

Piąty obrót: 1 => 90

Szósty obrót: 2 => 180

Siódmy obrót: 3 => 270

Ósmy obrót: 0 => 0

Dziewiąty obrót: 1 => 90

Dziesiąty obrót: 2 => 180

Wynika z tego prosty wniosek: znając resztę z dzielenia ilości cykli przez ilość dostępnych rozwiązań uzyskamy numer cyklu, a wynik uzyskamy mnożąc numer cyklu razy 90. W przykładzie szukamy wartości dla dziesiątego cyklu, a więc równanie wygląda następująco:

(10 % 4) * 90 = 2 * 90 = 180

Zatem nasza funkcja w rezultacie będzie wyglądać następująco:

function rotate(int times): int
{
    return (times % 4) * 90;
}

Wygląda dużo prościej, prawda? I do tego nie zawiera żadnych pętli, a więc będzie się wykonywać w czasie zależnym jedynie od szybkości działania równań modulo i mnożenia. Czas wykonania pozostanie więc podobny (i przewidywalny) zarówno dla wartości times=10 jak i dla times = 31772⁹

Powyższy przykład jest bardzo prosty i ma na celu pokazanie jak można dokonać optymalizacji patrząc na problem w nieco inny sposób, w tym przypadku poszukując cyklicznych zależności.

Testy

Dla zobrazowania korzyści płynących z przedstawionej optymalizacji napisałem kod php i testy do tego kodu, które znajdziecie na GitHub: https://github.com/jakubthedeveloper/CyclesTest

Są dwa testy, jeden testuje wersję z pętlą, drugi testuje wersję zoptymalizowaną. Oba testy wykonują funkcję 10 razy, z ilością cykli kolejno:

9⁰ 9¹ 9² 9³ 9⁴ 9⁵ 9⁶ 9⁷ 9⁸ 9⁹

Wyniki prezentują się następująco:

• Test funkcji z pętlą wykonał się w czasie 13.55s
• Test funkcji zoptymalizowanej wykonał się w czasie 0.086s

Zatem dla zadanych wartości testowych czas wykonania skrócił się ponad 150 razy! Jak widać zysk jest ogromny przy tak prostym zadaniu. Jeśli chcesz zająć twój komputer na dłuższą chwilę, spróbuj wykonać test zmieniając w pętli testującej wartość 9 na jakąś większą wartość 🙂

Sprawdzanie warunków brzegowych

Niekiedy warto sprawdzić czy przed wykonaniem założonych działań funkcja nie powinna sprawdzić jakiś warunków brzegowych, których sprawdzenie jest mało kosztowne, a sprawi że nie będzie trzeba dokonywać bardziej złożonych obliczeń. Dla przykładu posłużę się grą kółko i krzyżyk.

Mamy do napisania metodę, która po każdym ruchu któregoś z graczy sprawdza czy nastąpiła wygrana. Istnieje wiele sposobów sprawdzenia czy dany symbol pojawił się trzykrotnie w rzędzie, kolumnie lub ukośnie, jednak gdy sobie na kartce kilka razy zagrasz w kółko i krzyżyk, być może zauważysz że nie da się wygrać w pierwszych czterech ruchach, ponieważ nie jest możliwe umieszczenie tego samego symbolu 3 razy w ciągu czterech kolejek. Zatem możemy dokonać prostej optymalizacji: na początku naszej metody sprawdzamy czy ilość ruchów jest mniejsza lub równa cztery, jeśli tak to zwracamy FALSE, co oznacza że wygrana nie nastąpiła.

Bardziej skomplikowane przypadki

Celem tego artykułu było pokazanie pewnego sposobu myślenia, który pozwala spojrzeć na problem nieco inaczej i znaleźć pewne niuanse, które pozwolą nam usprawnić nasze algorytmy. W przypadku rzeczywistych aplikacji nasze problemy optymalizacyjne będą ściśle powiązane z konkretnymi przypadkami z jakimi się spotkamy, technik optymalizacji jest wiele, zaliczamy do nich optymalizację zapytań do baz danych czy cache’owanie danych ale są to techniki używające już konkretnych rozwiązań, często dostępnych od ręki w używanych przez nas frameworkach, ja natomiast zachęcam do korzystania równolegle ze znanymi technikami innego podejścia do problemów, poszukiwania zależności, unikania skomplikowanych wyliczeń kiedy tylko to możliwe i kombinowania – tak, kombinowania – ponieważ praca programisty to praca umysłowa i często najlepsze rozwiązania nie znajdują się w wyszukiwarce internetowej, tylko między naszymi uszami 🙂