switch ... case a if ... else ....
Ostatnio zmodyfikowano 2009-06-25 11:18
manfred |
» 2009-06-24 13:55:19 Dobra, dobra... Kod w Ruby (case.rb): puts "#include <iostream>\nusing std::cout;\nint main()\n{\n volatile int foo = 666;\n switch(foo)\n {" 2000.times do foo = rand(2**32) printf " case %d: cout << \"%d\" << '\\n'; break;\n", foo, foo end puts " }\n}\n" I teraz zrób : ruby case.rb > case.cpp g++ -O3 -S -masm=intel -o case.S case.cpp geany case.S #czy jakikolwiek inny edytor Przyjrzyj się co kompilator zrobił i przestań, pompom, wprowadzać w błąd. |
|
manfred |
» 2009-06-25 00:50:29 No człowiek-mięsiączka normalnie. A kiedy łaskawie zauważysz, że ja o tym wyraźnie pisałem - kompilator sobie zrobi jumptabelę, jeśli wartości jest mało i są blisko siebie, w przeciwnym razie puści coś logarytmicznego/liniowego? Tak ogólnie to chyba nie rozumiesz złożoności - switch jako if..else if..else będzie liniowy w liczbę casów, w przypadku wyszukiwania binarnego logarytmiczny w liczbę casów. Chyba, że wymyśliłeś nową definicję złożoności. |
|
manfred |
» 2009-06-25 11:18:49 to kompilator wygeneruje implementację z porównaniami, bo tak jest szybciej. Z tego wynika że switch ma zawsze złożoność stałą |
Ech. Sam sobie przeczysz - jeśli z porównaniami, to raczej nie stałą. Tak samo jak quicksort (...) następuje przełączanie na algorytm heapsort (albo inny). |
Ale wtedy to nie jest quicksort, tylko introspective sort. Zresztą, widać że nie odpaliłeś tego mojego kodu, jawnie byś zobaczył, że stałej złożoności nie ma... |
|
1 2 « 3 » |