Przełącznik z ogromną liczbą przypadków

Question

Co się stanie, jeśli switch ma więcej niż 5000 case. Jakie są wady i jak możemy je zastąpić czymś szybszym?

Uwaga: Nie spodziewam się używać tablicy do przechowywania skrzynek, ponieważ jest taka sama.

Answer 1

Nie ma konkretnego powodu, aby sądzić, że chcesz czegoś innego niż instrukcji switch/case (i rzeczywiście bym się aktywnie spodziewał, że nie będzie to pomocne). Kompilator powinien utworzyć wydajny kod dyspozytorski, który może obejmować kombinację statycznych tabel [sparse] i bezpośredniego indeksowania, rozgałęzień binarnych itd .; ma wgląd w wartości statyczne skrzynek i powinien wykonać doskonałą pracę (retuning to w locie za każdym razem, gdy zmieniasz przypadki, podczas gdy nowe wartości, które nie pasują do ręcznie wykonanego podejścia - takie jak znacznie różniące się wartości gdy masz dość spakowane wyszukiwanie tablicy - może to wymagać przerobienia kodu lub po cichu spowodować rozdęcie pamięci lub spadek wydajności).

Ludzie naprawdę troszczyli się o tego rodzaju rzeczy, kiedy C próbował wygrać z programistami montażu hard-core ... kompilatory były odpowiedzialne za generowanie dobrego kodu. Innymi słowy - jeśli nie jest (wymiernie) zepsute, nie naprawiaj tego.

Ogólnie rzecz biorąc, świetnie jest być ciekawym tego typu rzeczy i uzyskać pomysły ludzi na temat alternatywnych rozwiązań i ich wpływu na wydajność, ale jeśli naprawdę jesteś pewien, że Twoja opieka i różnica w wydajności mogą być przydatne dla twojego programu (zwłaszcza jeśli profilowanie sugeruje to), a następnie zawsze testuj swój program wykonując prawdziwą pracę.

Answer 2

Spróbuj użyć klasy Dictionary z wartościami Delegata. Przynajmniej sprawia, że ​​kod jest trochę bardziej czytelny.

Answer 3

Jako pokarm do przemyśleń ... na wypadek, gdyby ktoś utknął w starym/wadliwym/nieefektywnym kompilatorze lub po prostu uwielbia hakować.

Wewnętrzna praca oświadczenia switch składa się z dwóch części. Znajdowanie adresu do skoku i dobrze skakać tam. W pierwszej części musisz użyć tabeli, aby znaleźć adres. Jeśli liczba przypadków wzrasta, stół staje się większy - wyszukiwanie adresu do skoku wymaga czasu. To właśnie kompilatory punktów starają się zoptymalizować, łącząc kilka technik, ale jednym prostym podejściem jest użycie tabeli bezpośrednio, która zależy od przestrzeni wartości wielkości liter.

Na odwrocie przykładu serwetki;

switch (n) { 
    case 1: foo(); break; 
    case 2: bar(); break; 
    case 3: baz(); break; 
} 

z takim kodem kompilatora kodu można utworzyć tablicę adresów_skrzyń i bezpośrednio uzyskać adres według tablicy [n]. Teraz szukanie zajęło O (1). Ale jeśli miał przełącznik jak poniżej:

switch (n) { 
    case 10: foo(); break; 
    case 17: bar(); break; 
    case 23: baz(); break; 
    // and a lot other 
} 

kompilator musi generować tabelę zawierającą case_id, jump_address par i kod do przeszukiwania tej struktury, która z najgorszych realizacji może trwać O (n). (Przyzwoite kompilatory optymalizują ten scenariusz, kiedy są w pełni uwolnieni dzięki włączeniu flag optymalizacyjnych w takim stopniu, że gdy zajdzie potrzeba debugowania takiego zoptymalizowanego kodu, twój mózg zacznie się smażyć).

To pytanie można zrobić wszystko na poziomie C, aby pokonać kompilator? i zabawne jest to, że podczas tworzenia tabel i przeszukiwania ich wydaje się łatwe, przeskakiwanie do zmiennej punktu przy użyciu goto nie jest możliwe w standardowym C. Istnieje więc szansa, że ​​jeśli nie zamierzasz używać wskaźników funkcji ze względu na obciążenie lub strukturę kodu, utkniesz ... cóż, jeśli nie używasz GCC. GCC ma niestandardową funkcję o nazwie Labels as Values, która pomaga uzyskać wskaźniki do etykiet.

Aby dokończyć przykład można napisać drugi switch z „etykiety jako wartości” funkcji tak:

const void *cases[] = {&&case_foo, &&case_bar, &&case_baz, ....}; 
goto *labels[n]; 
case_foo: 
    foo(); 
    goto switch_end; 
case_bar: 
    bar(); 
    goto switch_end; 
case_baz: 
    baz(); 
    goto switch_end; 
// and a lot other 
switch_end: 

oczywiście jeśli mówimy o 5000 przypadków, jest o wiele lepiej, jeśli napisać kawałek kodu, aby stworzyć ten kod dla ciebie - i prawdopodobnie jest to tylko sposób na utrzymanie takiego oprogramowania.

Jako uwagi końcowe; czy to poprawi twoją codzienną pracę? Nie. Czy to poprawi twoje umiejętności? Tak i rozmawiając z własnego doświadczenia, kiedyś przekonałem się, że poprawiłem algorytm bezpieczeństwa na karcie inteligentnej, właśnie poprzez optymalizację wielkości liter. To dziwny świat.

Answer 4

Instrukcja dużego przełącznika, generalnie generowanego automatycznie, może wymagać długiego czasu kompilacji. Ale podoba mi się pomysł, że kompilator optymalizuje instrukcję switcha.

Jednym ze sposobów rozpadają instrukcji switch jest użycie bucketing,

int getIt(int input) 
{ 
    int bucket = input%16; 
    switch(bucket) 
    { 
    case 1: 
     return getItBucket1(input); 
    case 2: 
     return getItBucket2(input); 
    ... 
    ... 
    } 
    return -1; 
} 

Więc w kodzie powyżej, rozpadł się nasz instrukcji switch jest na 16 części. Łatwo zmienić liczbę segmentów w automatycznie generowanym kodzie.

Kod ten dodał koszt wykonania jednej warstwy pośredniej lub wywołania funkcji. . Ale biorąc pod uwagę kubełki zdefiniowane w różnych plikach, szybciej jest je skompilować równolegle.