728 x 90

If czy case? Czyli czego używa się w menu

If czy case? Czyli czego używa się w menu

Ostatnio przyszło mi pisać skrypt w systemie Linux, w którym użytkownik, podając parametry wejściowe, decydował o tym, co wykona program. Skrypt był prosty i przyjąłem, że można wykonać tylko jedną akcję na raz, ale trzeba się było zastanowić, jak sprawdzać, którą opcję wybrał użytkownik. Pomysły na zrealizowanie tego były dwa: seria if albo case. Zdecydowałem się na ten drugi sposób. Ale może najpierw krótkie przypomnienie.

Programistom tych funkcji przybliżać nie trzeba, bo są to jedne z pierwszych rzeczy których się uczymy. Dla ludzi, którzy jeszcze nie mieli zbyt dużo do czynienia z programowaniem zrobię jednak krótki wstęp. Na początku powiem tylko, że w zależności od języka, w którym piszemy postać tych funkcji może się różnić, a to co opiszę poniżej jest tylko ogólnym schematem.

 

IF

Instrukcja if ma następujący schemat:

if (warunek) { polecenia 1 }
else { polecenia 2}

Oznacza to: jeżeli warunek podany po if jest spełniony, to wykonaj “polecenia 1”, w przeciwnym wypadku (else) wykonaj “polecenia 2”. Po else możemy wpisać kolejne polecenie if i w ten sposób sprawdzać kolejne warunki do czasu znalezienia tego, który zostanie spełniony. W if możemy również sprawdzać kilka warunków na raz, sprawdzając czy wszystkie są spełnione (łączymy warunki operatorami logicznymi AND) lub czy którykolwiek z nich jest spełniony (operator logiczny OR).

 

SWITCH/CASE

Instrukcja switch w języku C++ ma następujący schemat:

switch (zm1)
{
case 1: polecenia 1; break;
case 2: polecenia 2; break;
...
default: polecenia X; break;
}

Po instrukcji switch wpisujemy nazwę zmiennej, którą będziemy sprawdzać. Slowa case wskazują przypadki, które rozpatrzy switch. Oznacza to, że jeżeli zmienna zm1 będzie miała wartość 1, to zostaną wykonane polecenia 1, jeżeli będzie miała wartość 2 – to wykonają się polecenia 2, itd. W przypadku gdyby żadna z wartości case nie odpowiadałaby wartości zm1 – wykonane zostaną polecenia przypisane do default, czyli takiego naszego wyjścia awaryjnego, np. w momencie gdy nastąpił błąd. Instrukcja break kończąca każdy przypadek case jest potrzebna, żeby wykonane zostały tylko te fragmenty kodu, które są przypisane do danego warunku. Gdyby tego nie umieścić, po odnalezieniu odpowiedniego case zostałyby wykonane wszystkie komendy poniżej, łącznie z komendami umieszczonymi w default.

 

Wszyscy wiemy już jak mniej więcej działają te dwie funkcje, ale teraz jest pytanie: czego lepiej używać, jeżeli będziemy chcieli zrobić menu w swoim programie lub skrypcie?

Szukając odpowiedzi na to pytanie postanowiłem sprawdzić, której z tych funkcji użyli programiści systemów Linux do sprawdzania opcji, które podajemy przy poleceniach typu ls, rm czy mkdir. A może użyli jeszcze innego sposobu?

Zajrzyjmy więc do kodu jednego z programów Linuxa – mkdir, czyli programu do tworzenia katalogów z poziomu konsoli.


while ((optc = getopt_long (argc, argv, "pm:vZ", longopts, NULL)) != -1)
    {
      switch (optc)
        {
        case 'p':
          options.make_ancestor_function = make_ancestor;
          break;
        case 'm':
          specified_mode = optarg;
          break;
        case 'v': /* --verbose  */
          options.created_directory_format = _("created directory %s");
          break;
        case 'Z':
          if (is_smack_enabled ())
            {
              /* We don't yet support -Z to restore context with SMACK.  */
              scontext = optarg;
            }
          else if (is_selinux_enabled () > 0)
            {
              if (optarg)
                scontext = optarg;
              else
                options.set_security_context = true;
            }
          else if (optarg)
            {
              error (0, 0,
                     _("warning: ignoring --context; "
                       "it requires an SELinux/SMACK-enabled kernel"));
            }
          break;
        case_GETOPT_HELP_CHAR;
        case_GETOPT_VERSION_CHAR (PROGRAM_NAME, AUTHORS);
        default:
          usage (EXIT_FAILURE);
        }
    }

Powyższy kod pochodzi z pliku mkdir.c – pliku źródłowego polecenia mkdir. Uwzględniłem tylko instrukcję switch odpowiadającą za sprawdzenie, która opcja została wybrana i uruchomienie odpowiednich działań. Switch ten znajduje się w pętli while, która wykonuje się do czasu odczytania wszystkich podanych przez użytkownika parametrów.

Jeżeli zajrzymy do manuala programu mkdir zobaczymy, że może on przyjmować takie parametry jak te, zawarte w poszczególnych case:

Wiemy już, co zostało użyte do zaprogramowania mkdir. Zobaczmy jeszcze jak wygląda sytuacja w programie do zliczania linijek, znaków i bajtów w pliku jakim jest wc:

while ((optc = getopt_long (argc, argv, "clLmw", longopts, NULL)) != -1)
    switch (optc)
      {
      case 'c':
        print_bytes = true;
        break;
      case 'm':
        print_chars = true;
        break;
      case 'l':
        print_lines = true;
        break;
      case 'w':
        print_words = true;
        break;
      case 'L':
        print_linelength = true;
        break;
      case FILES0_FROM_OPTION:
        files_from = optarg;
        break;
      case_GETOPT_HELP_CHAR;
      case_GETOPT_VERSION_CHAR (PROGRAM_NAME, AUTHORS);
      default:
        usage (EXIT_FAILURE);
      }

Powyższy kod jest fragmentem pliku wc.c, czyli źródła dla programu wc. Mamy kolejny switch do sprawdzania, które opcje mają zostać wykorzystane w programie. Tak jak w poprzednim przykładzie porównajmy kod z zawartością manuala:

Opcje do wykorzystania w programie pokrywają się z case w kodzie. Tak samo sytuacja przedstawia się z innymi programami, takimi jak ls, cat, cp, chmod itd.

 

Na powyższych przykładach widać, że w kodach produkcyjnych jest używana funkcja switch przy takich wyborach. Czy to oznacza, że przy konstrukcji menu powinniśmy zawsze używać switch, a nie if…else? Zależy co chcemy uzyskać. Jeżeli sprawdzamy tylko jedną zmienną, która ma przyjmować konkretne wartości – to jak najbardziej switch jest dobrym rozwiązaniem. Moim zdaniem kod do sprawdzania takiego warunku z użyciem switch jest bardziej czytelny, niż gdybyśmy chcieli wykorzystać drabinkę if, zwłaszcza jeżeli różnych opcji będzie na prawdę dużo. Jednak nie ma dowodu na to, że switch działa szybciej niż if. W końcu komputer musi jakoś podjąć decyzję o tym, do którego case ma przeskoczyć w programie. Używając instrukcji if łatwo zauważyć jak zachowuje się program: sprawdza warunki if po kolei do momentu aż znajdzie ten, który jest spełniony, a po wykonaniu fragmentu programu, który odpowiadał danemu warunkowi, następuje przeskok za koniec drabinki if…else. A jak działa switch od wewnątrz?

Załóżmy, że opcje w case mają wartości liczbowe, żeby było łatwiej zrozumieć to co się dzieje. Switch może działać w różny sposób. To, jak to się dzieje, zależy od ilości warunków oraz od tego, jak odległe od siebie są poszczególne warunki.

Najpierw załóżmy, że warunki nie są zbyt odległe. W przypadku, kiedy mamy mniej niż 256 case`ów (wszystkie da się ponumerować i zapisać jako bajt), wtedy switch zostanie rozpisany w języku assemblera na dwie tablice, na podstawie których wykonywane są przeskoki do odpowiednich warunków. Co jeżeli będzie 256 i więcej warunków case? Można powiedzieć, że ułatwia to zadanie, ponieważ zostanie utworzona tylko jedna tablica z ponumerowanymi przypadkami case.

Sytuacja utrudnia się w momencie, kiedy mamy do czynienia z warunkami o odległych wartościach, np. 100, 300, 450, 600, 700, 950. Wówczas kompilator, podczas optymalizacji kodu, zapisze naszego switch jako serię komend if, dzięki czemu zostanie użyty algorytm BST (Binary Search Tree).

Przykład drzewa BST:

Polega to na tym, że przyjmujemy jeden z warunków jako początkowy i sprawdzamy, czy wartość, której szukamy, jest mniejsza, większa czy równa od tego warunku. Jeżeli jest równa, to nie musimy dalej szukać i wykonujemy dany kawałek kodu, a następnie wychodzimy ze switch. Jeżeli tak nie jest, to musimy przejść na którąś z gałęzi drzewa i sprawdzać dalej. Jeżeli żaden z warunków nie będzie pasował, zostanie wybrany default.

W specyficznym przypadku, np. gdy kilka warunków ma zbliżone wartości, a pomiędzy następnymi jest duży przeskok kompilator może połączyć wymienione wcześniej metody, aby jak najszybciej zrealizować dany switch.

Niestety jak widać, przy używaniu switch nie da się całkowicie uniknąć instrukcji if.

Czy jesteśmy jednak skazani na to, że kompilator sam określa, co zrobi z danym programem? Oczywiście nie. Możemy optymalizować działanie naszego programu poprzez umiejętne przestawianie fragmentów kodu. Potrzebujemy jednak do tego odpowiednich danych. Możemy je zdobyć np. poprzez analizowanie jak użytkownicy używają naszego programu i przygotować odpowiednie statystyki, w których będziemy uwzględniali, która opcja jest najczęściej używana podczas wykonywania programu, a które z możliwości są używane najrzadziej. Mając takie dane możemy podzielić przypadki w naszym programie na gorące i zimne. Gorące to takie, których używamy najczęściej, zwykle jest ich mało w stosunku do wszystkich możliwych do wybrania opcji. Zimne to takie, które są prawie nieużywane w całym czasie działania programu. Mając taki podział możemy stosować różne strategie optymalizacji kodu.

Jedną ze strategii optymalizowania kodu, w którym dokonujemy wyboru, jest Hot Case Hoisting, czyli podnoszenie gorących przypadków. Jest ona prosta. Otóz gorące przypadki ustawiamy możliwie najwcześniej w kodzie, aby zostały sprawdzone jako pierwsze. W przypadku serii if od razu widać jaki będzie efekt. W przypadku case nie wiemy co prawda jak kompilator przetworzy nasze przypadki i czego użyje do obsługi, ale nawet jeśli zostanie użyta tablica skoków, możemy w ten sposób niebezpośrednio uniknąć obciążenia tablicy.

Kolejną strategią jest Hot Default Case Promotion. Na podstawie analizy działania naszego programu możemy stwierdzić, że jakaś wartość nie uwzględniana w żadnym case, czyli obsługiwana przez default, pojawia się bardzo często przy wyborze. Kompilator w zależności od rozłożenia przypadków case może zastosować różne strategie działania, więc ciężko przewidzieć, czy dany przypadek będzie sprawdzany szybko, np. jeśli ma wartość większą niż największy uwzględniony case w przypadku sprawdzania w tablicy skoków, czy wręcz przeciwnie, np. kiedy będzie trzeba znaleźć ten przypadek na drodze przeszukiwania drzewa binarnego. W drugim przypadku możemy stracić sporo czasu. Strategia Hot Default Case Promotion polega na tym, że dany częsty przypadek wyciągamy z default i tworzymy dla niego oddzielny case. Możemy przy okazji zastosować też technikę z poprzedniego akapitu i umieścić ten przypadek w odpowiednim miejscu kodu. W ten sposób nie tracimy czasu w przypadku przeszukiwania drzewa lub szukania dziur w tablicy skoków.

Zoptymalizować kod z instrukcją switch możemy również za pomocą metody Switch-Case Partitioning. Polega ona na tym, że zimne case wrzucamy do default, a wewnątrz domyślnego przypadku tworzymy nową instrukcję switch. Dzięki takiemu rozwiązaniu możemy zmniejszyć czas szukania odpowiednich case. Dla przykładu: powiedzmy że mamy program, w którym jest 40 opcji w menu, z czego tylko 10 jest często używanych. Taki stan rzeczy może wydłużyć czas szukania przypadku, który nas interesuje, ponieważ zimne case są poprzeplatane z gorącymi. Jeżeli wykluczymy rzadko używane opcje z głównego switch i umieścimy je w nowym switch wewnątrz default, czas szukania często używanych przypadków zostanie skrócony, a nie stracimy żadnych opcji w programie. Komputer ma mniej pracy i szybciej wykonuje określone polecenia.

Optymalizacja kodu za pomocą powyższych metod wymaga przeprowadzenia analiz użytkowania, a te najczęściej możemy uzyskać dopiero, kiedy oprogramowanie trafi do użytku. Musimy więc być gotowi na to, że trzeba będzie aktualizować nasze programy, jeżeli będziemy chcieli, aby działały jak najefektywniej, ponieważ w fazie testów dane mogą być niewystarczające.

Dla utrwalenia i pokazania na przykładzie metod optymalizacji omówionych powyżej przemyślmy pewien przykład. Załóżmy, że mamy program, w którym mamy switch z opcjami będącymi literami alfabetu: a,b,…,z. Przypadki case są zapisane w programie po kolei, tak samo jak litery alfabetu. W sumie będziemy mieli 26 przypadków case i default. Program ten trafił już do użytku i została przeprowadzona analiza użytkowania. Tak przedstawiają się ogólne statystyki:

a,f,i,k,u,x 98%
Pozostałe opcje + default 2%

6 opcji z przygotowanych 26 są używane przez cały czas, a pozostałe bardzo rzadko, niektóre w ogóle nie zostały użyte. Opcje wymienione w pierwszym wierszu tabeli będą naszymi gorącymi przypadkami, pozostałe, łącznie z default są zimne. Przy takich statystykach możemy mieć różne wyniki szybkości, w zależności od przyjętej przez kompilator techniki zapisu switch. Jeżeli stworzy drzewo BST do przeszukiwania odpowiedniego case, a np. x będzie na końcu tego drzewa, to przez nadmiar zimnych opcji czas dojścia do szukanego przypadku znacznie się wydłuży.

Możemy to zmienić, stosując omówione wcześniej metody optymalizacji. Zastosujmy najpierw Hot Case Hoisting, czyli przenieśmy te opcje, które są najczęściej używane na pierwsze pozycje w switch.

Po wykonaniu tego kroku możemy mieć w kodzie układ podobny jak w poniższym grafie:

Najczęściej używane case mamy już na początku switch. Co możemy dalej zrobić?

Gdyby w naszych statystykach użytkowania pojawiła się jakaś wartość, która często trafia do menu ale ląduje w default, wypadałoby zrobić dla tej wartości osobny case zgodnie ze strategią Hot Default Case Promotion. Wtedy dany przypadek trafiłby prawdopodobnie do części z gorącymi case.  Jeżeli nie ma takiej wartości to możemy przejść do trzeciej omawianej przeze w tym artykule strategii.

Wiemy, że przypadki zimne są bardzo rzadko używane, ale nie możemy ich wyrzucić. Możemy natomiast przenieść je w inne miejsce tak, żeby nie powodowały spowolnienia głównej części switch – czyli do default.

Zróbmy w default dodatkowy switch, w którym umieścimy 20 przypadków zimnych z głównej instrukcji switch. Otrzymamy następujący układ w programie:

W ten sposób zoptymalizowaliśmy program, który otrzymaliśmy w poprzednim kroku za pomocą strategii Switch-Case Partitioning, czyli najmniej używane przypadki obsługujemy w dodatkowym switch wewnątrz opcji default.

 

Podsumujmy wszystko co omówiłem do tej pory:

Menu możemy zrealizować za pomocą serii if…else lub switch. W pierwszym przypadku sprawdzamy wszystko po kolei, więc najlepiej by było przewidzieć, które warunki będą najbardziej prawdopodobne i zapisać je w pierwszej kolejności, aby trochę przyspieszyć pracę programu. Przy instrukcji switch kompilator optymalizuje kod wykonywany tak, aby wykonywał się jak najszybciej. Ma do tego dwie główne metody: utworzenie tablicy skoków lub wykorzystać algorytm BST. Metody te są dopasowywane do konkretnego przypadku i mogą być łączone, aby zapewnić jak największą efektywność. Oczywiście w przypadku, kiedy mamy do sprawdzenia kilka opcji, tak jak przy poleceniach w systemie Linux, należy umieścić sprawdzanie warunków w odpowiednich pętlach.

W kodach produkcyjnych switch jest wykorzystywany częściej niż drabinka if…else, jednak nie jest to obowiązkowe. Każdy powinien sam wybrać czego będzie używał w swoich programach. Jednak osobiście uważam, że zastosowanie instrukcji switch zwiększa czytelność kodu przy większej ilości warunków, niż gdyby miała zostać do tego użyta seria if.

Prędkość działania naszego programu zależy również od tego, czy nasz kod będzie zoptymalizowany. Jeżeli najczęściej wybierana opcja będzie sprawdzana zawsze na końcu, komputer będzie wykonywał dużo operacji na marne, zatem warto się zastanowić również nad ustawieniem poszczególnych opcji oraz nie bać się aktualizacji kodu w trakcie użytkowania go.

Leave a Comment

Your email address will not be published. Required fields are marked with *

Cancel reply

Inne artykuły