Kleine Frage zu "Auswahl-Verfahren"

[joffal]

nabend,

mir ist vorhin so etwas in den Sinn gekommen wie ich den Status einer Variable möglichst effizient abfragen kann.
Es gibt ja:

int a = wert;
switch(a)
case 0:
     blabla;
     break;
case 1:
     blabla;
     break;

int a = wert;
if (a == 0)
blabla;
if (a == 1)
blabla;
if (a == 2)
blabla;

int a = wert;
if (a == 0)
blabla;
else if (a == 1)
blabla;
else if (a == 2)
ihrkenntdasja_blabla;

int a = wert;
int b = andererwert;
int c = nochmalandererwert;
if (a == b)
bla;
else if (a ==c)
....
// hier kann ich wieder das spielchen spielen mit if if if ... oder switch (a) case b: ....

Frage nun, was ist denn am besten?
bei if if if if vergleicht er jedes mal, das weiß ich nun, aber wie ist das mit switch und wenn man ganz kurze bzw. lange vergleiche durchführen möchte, wäre es dann nicht besser if if if bzw. if elsif elseif zu verwenden?

 

[Fragile Heart]

Hallo Schalte doch bei deinen Compiler mal die ASM Codeausgabe an, dann siehst was der Compiler daraus macht.

Zur Frage selber, es ist nicht immer eindeutig zu beantworten was besser ist. Es hängt in diesen Fall immer vom jeweiligen Fall ab. Allerdings sollte man sich mit solchen Sachen immer erst dann beschäftigen, wenn es notwendig ist (nach Messungen am Projekt)

 

[AMD]

Switch und Case ist an sich eine ganz gute Sache - obwohl ich persönlich garkein Fan davon bin
Wenn ich mir Codebeispiel 2 und 3 angucke, kannst du 3 in die Tonne kloppen!
Ob du nun machst:

if (a == 1)
if (a == 2)
...

oder

if (a == 1)
else if (a == 2)
...

ist ja letztendlich egal, weil du hast das selbe Ergebnis aber naja, diese ganze ebige Verzweigung ist halt nicht unbedingt so schön.

Zu Beispiel 4:
Wenn du natürlich irgendwelche Werte von einer Funktion bekommst oder in der selben Funktion berechnest, dann musst du das natürllich in eine Variable auslagern. (Ok musst nicht aber dazu gleich mehr).
Das ist zumindest für spätere Codes von Vorteil so zu arbeiten aber wenn du definitiv weisst, dass b defintiv 2 ist, dann musst du das nicht extra in eine Variable definieren.

Zu dem, man muss es nicht unbedingt machen: Wenn man einen Wert durch eine Funktion berechnen lässt und dieses mit einem return zurückgibt, dann kann das direkt in der If Bedinung erfolgen und muss nicht erst in eine Variable... aber nunja, mir scheint so als ob das bei dir ohnehin noch keine Anwendung findet und sowas kommt dann später von selbst.


Aber nach jetzigem Stand, würde ich Code #2 als optimale Lösung für dich erachten.

 

[Fragile Heart]

Aber nach jetzigem Stand, würde ich Code #2 als optimale Lösung für dich erachten.

Also mich überrascht es jetzt doch etwas, dass du mit solcher Sicherheit eine solche Aussagen treffen kannst?!?

Wir wissen über das eigentliche Problem, wenn ich das richtig verstanden habe gibt es gar keins, rein gar nichts und eine pauschale Aussage, auch wenn er sie sich wünscht, gibt es einfach nicht. Wenn man schon sowas von hand optimieren will/muss, dann muss man schon einen verdammt guten Grund haben warum man die Compiler Optimierungen übergehen will.

 

[joffal]

hey,

@fragile heart: ASM? WTF?
also kann ich erstmal machen was ich will?^^
Nur ich hab hier wie gesagt eine "Auswahl" wo ich aus vielen fällen auswählen muss und keine möglichkeit habe sie zusammenzufassen (sind über tausend, deswegen wollte ich im vorfeld fragen, was da besser ist )

Edit: oh du hast vor mir gepostet xD
-> naja mein problem steht ja jetzt hier

Zu dem, man muss es nicht unbedingt machen: Wenn man einen Wert durch  eine Funktion berechnen lässt und dieses mit einem return zurückgibt,  dann kann das direkt in der If Bedinung erfolgen und muss nicht erst in  eine Variable... aber nunja, mir scheint so als ob das bei dir ohnehin  noch keine Anwendung findet und sowas kommt dann später von selbst.[/QUOTE]

Musste ich auch schon anwenden^^ bzw. hab ich einfach mal gemacht, um mir das zwischenspeichern in einer Variable zu sparen
Hab auch nochmal geschaut, in meinem Buch steht auch nichts so direkt zu der Frage, welche der Methoden wann besser ist :daumen2:


[QUOTE="AMD, post: 3141619, member: 4812"]
Aber nach jetzigem Stand, würde ich Code #2 als optimale Lösung für dich erachten.[/QUOTE]
 
:what:

sicher? weil wenn man sehr viele Werte immer und immer wieder abfragen muss, dann geht das mit dem ganzen if if if if doch auf die Rechenzeit
verwendet man elseif würde der Verglich bei einem true doch abgebrochen werden oder?

 

[Fragile Heart]

Optimierungen gehen halt einfach nicht pauschal, da muss man sich immer speziellen Fall ansehen was besser ist. Wenn dem nicht so wäre, würde sich die Frage stellen, warum die Compiler es nicht gleich so machen?

Nehmen wir doch mal ein Beispiel.
Du hast eine Menge von n Zuständen und ein Zustand kommt besondershäufig vor, dann würde sich eine kombination aus 3 und 1 anbieten. Mit Variante 3 prüfst du als erstes ob der häufige Zustand nicht zu trifft, und wenn nicht gehst du in eine normalen switch case Block.

Bei allen deinen Optimierungsüberlegungen muss dir ommer klar sein, dass moderne Compiler zum einen auch versuchen zu optimieren und du das was du da programmierst auch noch lesen/verstehen musst! Wenn du dann noch berücksichtigst, dass 98% des Codes den du schreibst nicht Zeitkritisch sein werden werden, dann verstehst du hoffentlich auch, dass zuviele Optimierungen gar nicht gut sind.

 

[bingo88]

Konstrukte der Art if if if solltest du nur verwenden, wenn der zu prüfende Wert mehrfache Auwirkungen haben soll. Beispiel:

int wert = ...; // nehmen wir mal 33 an

if (wert > 10)
    cout << "Der Wert ist größer 10." << endl;
if (wert > 20)
   cout << "Der Wert ist größer 20." << endl;

In diesem Beispiel wird der Wert durch jedes if gejagt, was natürlich sehr kostspielig werden kann. Ansonsten else if.


Ich habe es jetzt nicht getestet, aber der Assemblercode zu einem switch sieht mir schneller aus.
Ich habe zum Testen eine Kette aus 10 if/else if Anweisungen und einem switch mit denselben 10 Abfragen erstellt. Der generierte Code zum if/else if hat für jede Abfrage ein cmp (compare / Vergleich), ist also relativ teuer. Das switch-Konstrukt hingegen benötigt nur einen Sprung und zwar direkt zum Einstieg der Funktion. Dabei wird der zu prüfende Wert (bei mir ein int) auf die Basisadresse der Funktion hinzuaddiert und somit das entsprechende Sprungziel bestimmt.

test2:
003710B0  jmp         dword ptr [eax*4+0037114Ch]  ; hier wird das Sprungziel bestimmt
$LN10:
003710B7  push        3720F4h  
003710BC  call        dword ptr ds:[003720A0h]  
003710C2  add         esp,4  
003710C5  ret  
$LN9:
003710C6  push        3720F8h  
003710CB  call        dword ptr ds:[003720A0h]  
003710D1  add         esp,4  
003710D4  ret  
$LN8:
003710D5  push        3720FCh  
003710DA  call        dword ptr ds:[003720A0h]  
003710E0  add         esp,4  
003710E3  ret  
$LN7:
003710E4  push        372100h  
003710E9  call        dword ptr ds:[003720A0h]  
003710EF  add         esp,4  
003710F2  ret  
$LN6:
003710F3  push        372104h  
003710F8  call        dword ptr ds:[003720A0h]  
003710FE  add         esp,4  
00371101  ret  
$LN5:
00371102  push        372108h  
00371107  call        dword ptr ds:[003720A0h]  
0037110D  add         esp,4  
00371110  ret  
$LN4:
00371111  push        37210Ch  
00371116  call        dword ptr ds:[003720A0h]  
0037111C  add         esp,4  
0037111F  ret  
$LN3:
00371120  push        372118h  
00371125  call        dword ptr ds:[003720A0h]  
0037112B  add         esp,4  
0037112E  ret  
$LN2:
0037112F  push        372110h  
00371134  call        dword ptr ds:[003720A0h]  
0037113A  add         esp,4  
0037113D  ret  
$LN1:
0037113E  push        372114h  
00371143  call        dword ptr ds:[003720A0h]  
00371149  pop         ecx  
0037114A  ret

 

[fadade]

Das switch-Konstrukt hingegen benötigt nur einen Sprung und zwar direkt zum Einstieg der Funktion. Dabei wird der zu prüfende Wert (bei mir ein int) auf die Basisadresse der Funktion hinzuaddiert und somit das entsprechende Sprungziel bestimmt.

/sign

so hab ich es auch gelesen, dass switch schon mehrere Optimierungen enthält.
Wenn die Auswahl relativ gleichberechtig sein soll, dann würde ich auch mit switch arbeiten (aber tu das "break;" am ende nicht vergessen )
Dann könnte man noch wie Fragile Hearte schrieb, kombinieren. Also

switch (var)
case 1:
 if ....
 else if
 ....
 break;
case 2:

 

[Fragile Heart]

Nur der Vollständigkeit halber, diese Art der switch optimierung funktioniert nicht in allen Fällen.

Edit:
Und vielleicht wäre es gut, wenn man bei solchen Sachen mal mit angibt welcher Compiler verwendet wurde.

 

[bingo88]

Nur der Vollständigkeit halber, diese Art der switch optimierung funktioniert nicht in allen Fällen.

Edit:
Und vielleicht wäre es gut, wenn man bei solchen Sachen mal mit angibt welcher Compiler verwendet wurde.

Stimmt

Compiler: MS VC 2010 (default release build settings)

 

[Bauer87]

Hallo Schalte doch bei deinen Compiler mal die ASM Codeausgabe an, dann siehst was der Compiler daraus macht.

Das ist eine sehr entscheidende Frage. Im besten Fall ist sogar egal, was man macht, weil der Compiler gut optimiert.

Zur Frage selber, es ist nicht immer eindeutig zu beantworten was besser ist. Es hängt in diesen Fall immer vom jeweiligen Fall ab. Allerdings sollte man sich mit solchen Sachen immer erst dann beschäftigen, wenn es notwendig ist (nach Messungen am Projekt)

Um mal ein einfaches Beispiel zu geben, wie viel schon Kleinigkeiten ausmachen können:

zahl = rand()%100;
if (zahl > 95 ){
    foo();
} else if (zahl > 90) {
    bar();
}

gegen

zahl = rand()%100;
if (zahl > 90 ){
    if (zahl > 95) {
        foo();
    } else {
        bar();
    }
}

Da in 90% der Fälle gar nichts gemacht werden soll, halte ich es in diesem Beispiel für sinnvoll, erst mal diese 90% auszusortieren. Wenn man das erste Codebeispiel verwendet, wird fast jedes Mal sinnlos sowohl mit 90 als auch mit 95 verglichen. Man sollte also einfach den Kopf nicht ausschalten. (Die Suche nach pauschalen Lösungen deutet für mich irgendwo an, dass man das vor hat…)

 

[Skysnake]

Da in 90% der Fälle gar nichts gemacht werden soll, halte ich es in diesem Beispiel für sinnvoll, erst mal diese 90% auszusortieren. Wenn man das erste Codebeispiel verwendet, wird fast jedes Mal sinnlos sowohl mit 90 als auch mit 95 verglichen. Man sollte also einfach den Kopf nicht ausschalten. (Die Suche nach pauschalen Lösungen deutet für mich irgendwo an, dass man das vor hat…)

Absolut sign!

Programmieren hat verdammt viel damit zu tun, sich vorzustellen, was der PC da eigentlich macht. Manchmal ist es besser, einen Wert neu zu berechnen, das andere mal ist es besser einen Wert in einer Variablen zu speichern. Kommt halt immer ganz speziell drauf an. Das Problem heute ist nur, dass der Compiler so verdammt viel optimiert, das man gar nicht mehr sieht, was alles gemacht wird.

Nehmen wir doch mal den GCC Compiler mit -O0 oder -O3 bzw. -O2. Die unoptimierte Version ist eigentlich immer SEHR viel langsamer, als die optimierten. Da bekommt man öfters mal einen Faktor 2 raus.

Was aber auch sehr verblüffend und überhaupt nicht intuitiv ist, ist dass manchmal das Programm schneller ist, welches möglichst klein sein soll, und nicht das, dass möglichst schnell sein soll (O2 oder O3, frag mich grad nicht welches welches war ).

Der Compiler macht die Sache im Normalfall schnell, wenn es so schnell geht. Von Hand ran gehen, ist meist nicht die tollste Idee. Man muss ja erst mal besser werden als der Compiler, und das ist gar nicht einfach... Man sollte sich also eher mal über das Konzept gedanken machen, UND!!!! ob das überhaupt an dieser Stelle wichtig ist. Wenn das Programm nur zu 1% der Zeit in der Funktion rumrennt, dann kann die auch zur Not mal langsam sein. Die Laufzeit wird durch andere Dinge bestimmt, um die man sich eher kümmern sollte...

Was ich mich allerdings Frage ist, warum von euch noch keiner eine Hash-Table oder mehrfach verkettete Liste in den Raum geworfen hat. Kann auch schneller sein.

Man sollte aber mal wirklich klären, was gemacht werden soll, denn so ist das ziemlich sinnfrei...

 

[bingo88]

Ich hab mal wo gelesen, es gibt sogar Compiler die bei (sehr) großen switch-Blöcken ne binäre Suche implementieren. Ist aber schon ne Weile her, hab also die Quelle nicht mehr...

 

[joffal]

tz tz ohne Quellenangabe ist alles Quatsch

ney, okay, alles klar, dann werde ich mich für eine verkettete Abfrage entscheiden. Mal sehen, was so draus wird, thx to u

Ujnd ob es seltener vorkommene Auswahlen gibt, hängt mehr oder weniger ganz vom User ab

 

[AMD]

sicher? weil wenn man sehr viele Werte immer und immer wieder abfragen muss, dann geht das mit dem ganzen if if if if doch auf die Rechenzeit
verwendet man elseif würde der Verglich bei einem true doch abgebrochen werden oder?

Ich behaupte einfach mal, dass du nur kleine Codes schreibst und da ist es sche*** egal ob es if if if oder if else if ... ist!
Mit der nötigen Erfahrung wirst du später auch sehen, welche Variante für dich am besten geeignet ist...