switch ... case a if ... else ....

Dyskusja na zadany temat.

Switch został wprowadzony ze względu na szybkość wykonania - if...else ma pesymistycznie liniową złożoność (sprawdzenie wszystkich warunków po kolei), podczas gdy switch - zawsze stałą.
Switch jest implementowany przez tablicę z adresami (warunki są stałe i muszą być liczbowe) - cały wybór sprowadza się do jednego skoku goto opcje[argument] (pseudokod).
Kody warunków są umieszczone w programie koło siebie - stąd też potrzeba instrukcji break - jest to po prostu wstawienie goto do końca switcha.
(jeśli odstępy miedzy argumentami są naprawde duże kompilator może być zmuszony zrobić ze switcha zwykły if).

Kompilator i tak powinien wszystko zoptymalizować, ale tak to wyglądało w oryginale (warto sobie przypomnieć jak szybkie były komputery, gdy powstał C - bardziej zaawansowana optymalizacja była poza zasięgiem, więc cała robota spadała na człowieka).

@manfred: Gdybyś pomyślał, zauważyłbyś, że złożoność każdego switcha jest stała - tylko czasami ta stała złożoność jest równa maksymalnemu przypadkowi w liniowej (albo jest nawet większa).
4 switche po 256 przypadków albo 1 z 65k + 2 po 256.
Zamienianie switcha na if..else to tylko optymalizacja...

Co z tego wynika? Switch zawsze będzie albo szybszy, albo tak samo szybki jak if..else (optymalizacja jest bardzo łatwa). W drugą stronę już nie.

Switch ma złożoność logarytmiczną dla n danych wejściowych - tak jak napisał manfred. On zna asma, ja znam asma, a Ty najwyraźniej nie znasz go.

if'y mają złożoność liniową dla n' danych wejściowych - chyba, że zrobisz hierarchię w stylu drzewa (dziel i rządź) to też uzyskasz logarytmiczną złożoność, jednak czytelność kodu pójdzie do piachu.

/edit:
Mylisz pojęcie złożoności obliczeniowej algorytmu ze złożonością obliczeniową instrukcji. W złożoności obliczeniowej algorytmów if'y/switch'e traktuje się jako stałe ze względu na to, iż są to małe wartości w porównaniu do pętli. W przypadku gdy mówimy o złożoności instrukcji to liczymy ilość operacji, jakie należy wykonać, aby operacja dostarczyła oczekiwanego wyniku - de'facto na poziomie wysokiego języka programowania (jakim jest C++) złożoności instrukcji switch() nie widać (ale ona istnieje) i mogłoby się wydawać, że jest stała jednak tak nie jest.

W jaki sposób może mieć złożoność logarytmiczną od liczby warunków? I co ma asm do tego? Switch można zaimplementować jako zwykłą tablicę funkcji.
Switch i if..else mają złożoność zależną od ilości warunków, prawda? Więc switch to asymptotycznie O(1) a if..else O(n), gdzie n to ilość warunków...
W algorytmach switche/itd mają złożoność stałą bo złożoność to funkcja argumentu algorytmu (funkcji), a ilość warunków jest stała!

Hm... czyli twierdzisz, że:
wykona się w tym samym czasie co:

Praktycznie tak - w pierwszym wypadku kompilator zmieni to na jeden if (jedno porównanie), w drugim będzie to wyglądało tak (pseudokod):
(pomijam fakt, że kompilator zauważy, że w podanym przykładzie liczba = 50)
Jedno porównanie/skok (if .. goto)+ skok (break). Jeśli liczba byłaby charem, możliwa byłaby implementacja bez tego porównania - tablica adresów (case) miałaby wtedy 256 pól.
Więc, różnica jednej instrukcji (jeśli to int).

Z kolei if: jedno porównanie/skok, break niepotrzebny.
Ale if..else if to już porównanie/skok + skok + porównanie/skok.


Tyle co do liczb koło siebie. Teraz ciekawszy przypadek (nie odpowiadam na nic konkretnie, tylko rozwijam temat). Powiedzmy że mamy 100000 warunków, rozrzuconych po całym zakresie inta (4 miliardy). Zdecydowanie za dużo na jedną tablicę.
Więc realizacja będzie wyglądać tak:
Średnio na jeden case przypada 1,52587890625 (100000/2^16) możliwości, dla średniego przypadku kompilator wygeneruje 1,52587890625 porównania.
Czyli, złożoność ciągle jest praktycznie stała, nawet dla najgorszego (teoretycznie) przypadku.
Dlatego switch będzie zawsze albo szybszy, albo taki sam jak zwykłe if..else if.

(w przypadku kilkunastu warunków kompilator może wygenerować drugi switch - rozkład liczby warunków powinien zgadzać się z rozkładem gaussa)

W praktyce więcej niż ~2000 warunków raczej nie będzie - a to daje nam średnio 0,030518043793392843518730449378195 porównania/skok + jeden skok (w przypadku najgorszego możliwego rozstrzelenia liczb). W porównaniu do średnio 1000 porównań/skoków + 1 w if...else if.
A większość stałych/itd jest zazwyczaj koło siebie (wiadomości win api np).

Nigdzie tutaj nie ma złożoności logarytmicznej.

P.S. Taka ciekawostka - jak kiedyś, ręcznie, optymalizowano switchem
Duff's device

Moim zdaniem kompilator w momencie włączenia optymalizacji + release'a zrobi ze switch'a drzewo, a nie listę płaską jak sugerujesz. Przecież oczywistym jest, że ilość parametrów (wartości) będzie stała w switch'u, a co za tym idzie można zaimplementować dla niego algorytm, który z pesymistycznej złożoności liniowej zrobi logarytmiczną. Nie zmienia to faktu, że przy obliczeniach złożoności obliczeniowej i tak się traktuje tą operację jako stałą.

W związku z powyższym switch będzie szybszy niż if'y pomimo iż będzie realizował to samo. Możesz się z tym nie zgadzać, jednak takie jest moje zdanie, że będąc programistą tworzącym kompilator właśnie tak podszedłbym do implementacji switch'a.

/edit:
Hm... wydawało mi się, że złożoności obliczeniowe wyraża się w liczbach całkowitych, a nie po przecinku... O(0,000000001) - nigdzie nie uzyskasz przecież takiej złożoności obliczeniowej. Nie ma instrukcji, która się wykonuje w jednej milionowej czasu jednego taktu procesora. Każda instrukcja to minimum 1 takt, a rozpatrując wydajność switch'a właśnie takich jednostek używamy.

/edit2:
Skoro tak przekładasz na tablice... wyobraź sobie, że masz tablicę posortowaną rosnąco lub malejąco. Jakiej złożoności będzie algorytm, który będzie wyszukiwał czy istnieje dana wartość w tablicy? To jest dokładnie ten sam przypadek.