3. [Anfänger] Abbruchbedingung für Schleife

[Anfänger] Abbruchbedingung für Schleife

  • G

    Hallo,

    Folgendes Problem: ich habe zwei Variablen b1,b2 vom Typ bool, die in einer Schleife neu berechnet werden. Die Schleife soll genau dann beendet werden, wenn die Werte für b1 und b2 (als Paar betrachtet) bereits einmal vorgekommen sind.

    bool b1=initB1();
bool b2=initB2();

while (Paar [b1,b2] noch nicht vorgekommen) {
	unterprogramm(b1, b2);
	b1 = berechneB1();
	b2 = berechneB2();
}

    Zur Illustration zwei mögliche Abläufe:

    b1      b2         b1      b2
false   false      true    false
false   true       true    false
true    true		
false   true

    Ich suche eine möglichst elegante (und schnelle) Implementierung für die Abbruchbedingung.
    Eine mögliche nicht elegante Lösung ist: 4 zusätzliche bool Variablen definieren (bool falsefalse, falsetrue, truefalse, truetrue), innerhalb der Schleife abhängig von b1, b2 auf true setzen, und dann im while-Ausdruck prüfen, ob eine davon bereits true ist.

    Danke für eure Hilfe.

    0
  • N

    Du könntest eine Funktion schreiben, die der Kombination ein Integer zuweist - nach folgender Art:

    short Kombination(bool a, bool b)
{
    return a + 2*b;
}

    Diese gibt für jede Möglichkeit einen anderen Wert (zwischen 0 und 3) heraus.
    Du könntest (wegen der Geschwindigkeit) mit Flags abprüfen, ob die Kombination bereits vorgekommen ist. Ansonsten kannst du ein bool-Array mit 4 Elementen machen, die zu Beginn alle false sind und beim Vorkommen der bestimmten Kombination auf true gesetzt werden.

    0
  • D

    Wie ich das sehe kommst du nicht umhin das irgendwie in einer Variablen zu speichern. Ob du das jetzt in 4 bool's machst, oder in einem int spielt ja nicht so eine Rolle.

    0
  • N

    glis schrieb:

    Eine mögliche nicht elegante Lösung ist: 4 zusätzliche bool Variablen definieren (bool falsefalse, falsetrue, truefalse, truetrue), innerhalb der Schleife abhängig von b1, b2 auf true setzen, und dann im while-Ausdruck prüfen, ob eine davon bereits true ist.

    Ich denke jedoch, meine Lösung ist immer noch besser als die nicht-elegante von ihm 😉
    Aber du hast schon Recht, speichern muss man die bereits vorgekommenen Kombinationen so oder so. Wenn man allerdings direkt auf einen Array-Index zugreifen kann oder sogar auf einen Flag-Integer, ist das wohl schneller als alle vier zu überprüfen. Und was die Speicherung anbelangt: eine Funktion ist wohl auch schneller als 4 If-Abfragen.

    0
  • D

    Nexus schrieb:

    glis schrieb:

    Eine mögliche nicht elegante Lösung ist: 4 zusätzliche bool Variablen definieren (bool falsefalse, falsetrue, truefalse, truetrue), innerhalb der Schleife abhängig von b1, b2 auf true setzen, und dann im while-Ausdruck prüfen, ob eine davon bereits true ist.

    Ich denke jedoch, meine Lösung ist immer noch besser als die nicht-elegante von ihm 😉
    Aber du hast schon Recht, speichern muss man die bereits vorgekommenen Kombinationen so oder so. Wenn man allerdings direkt auf einen Array-Index zugreifen kann oder sogar auf einen Flag-Integer, ist das wohl schneller als alle vier zu überprüfen. Und was die Speicherung anbelangt: eine Funktion ist wohl auch schneller als 4 If-Abfragen.

    Ich glaube du wolltest mich zitieren. 😉

    Recht hast du schon,ich habe ja nicht gesagt, wie er es machen muss. Mann kann natürlich auch mit Bit Manipulation arbeiten, aber ich denke mal, dass das in dem Fall so, oder so nichts/viel bringt. 4 ist so eine schöne Zahl, da kann man soo viele Lösungen dazu finden das elegant/schnell zu implementieren. 🙂

    0
  • N

    Nein, ich wollte Stellung nehmen zum Anspruch des Threaderstellers auf Eleganz 😉
    Man muss ja nicht immer seinen Vorposter zitieren, wenn man ihm antwortet...

    Also, ich hab mal die beiden Varianten auf Geschwindigkeit getestet 😃
    Benötigte Zeit für 100 Millionen Aufrufe, wobei die 2 Bool-Variabeln zufällig erzeugt werden:
    * 4 Bool-Variabeln, if-Abfragen: ~30s
    * Funktionen, Flag-Integer: ~8.5s

    Achja, sind folgende Funktionen eigentlich performant? Ich hab das Gefühl, eher nicht; ich kenn mich fast kaum mit Flags aus... Würde es sich lohnen, sie inline zu machen? Ich hab keinen Zeitunterschied erkannt. Und Übergabe der Parameter als konstante Referenzen scheint auch keinen wirklichen Einfluss zu haben...

    bool GetFlag(short Bin, short Flag)
{
	return (Bin & (1 << Flag)) >> Flag; // das geht doch sicher einfacher, oder?
}

void SetFlag(short &Bin, short Flag)
{
	Bin |= 1 << Flag; // hier siehts wahrscheinlich besser aus
}
    0
  • K

    Nexus schrieb:

    bool GetFlag(short Bin, short Flag)
{
	return (Bin & (1 << Flag)) >> Flag; // das geht doch sicher einfacher, oder?
}

    bool GetFlag(short bin, short flag) {
    return bin & (1 << flag);
}
    0
  • N

    Vielen Dank, ich wusste es! 🙂
    Jetzt ist mein Algorithmus wieder 2% schneller 😃
    Eigentlich ist es ja klar, ein bool-Wert ist ja immer true wenn er nicht 0 ist...

    Was kann man gegen folgende Warnung tun? Ich meine jetzt nicht deaktivieren. static_cast<bool> bringt auch nichts...
    1>.\Main.cpp(9) : warning C4800: 'int': Variable wird auf booleschen Wert ('True' oder 'False') gesetzt (Auswirkungen auf Leistungsverhalten möglich)

    0
  • ?

    🙄

    0
  • G

    Nexus schrieb:

    Also, ich hab mal die beiden Varianten auf Geschwindigkeit getestet 😃
    Benötigte Zeit für 100 Millionen Aufrufe, wobei die 2 Bool-Variabeln zufällig erzeugt werden:
    * 4 Bool-Variabeln, if-Abfragen: ~30s
    * Funktionen, Flag-Integer: ~8.5s

    bool GetFlag(short Bin, short Flag)
{
	return (Bin & (1 << Flag)) >> Flag; // das geht doch sicher einfacher, oder?
}

void SetFlag(short &Bin, short Flag)
{
	Bin |= 1 << Flag; // hier siehts wahrscheinlich besser aus
}

    Genial. Danke Nexus!

    0
  • N

    Hier noch einmal der komplette Code, ich hab noch etwas abgeändert (z.B. Multiplikation mit 2 durch Shift-Operation ersetzt^^)

    // Rückgabe: Wert in [0,3] für eine der 4 möglichen Kombinationen
short Combination(bool a, bool b)
{ 
    return a + (b << 1); 
}

// Gibt das Bit an der Stelle 'Flag' des Integers 'Bin' zurück (erstes Bit hat Stelle 0)
bool GetFlag(short Bin, short Flag)
{
	return Bin & (1 << Flag);
}

// Setzt das Bit an der Stelle 'Flag' des Integers 'Bin' auf 1
void SetFlag(short &Bin, short Flag)
{
	Bin |= 1 << Flag;
}

int main()
{
	short FlagInt = 0;
    bool x, y; // deine beiden Bool-Werte, musst du noch initialisieren (in Schleife)
	while (true) // läuft, bis eine Kombination mehrfach vorkommt; maximal 4 Durchgänge
	{
		short k = Combination(x, y);
		if (GetFlag(FlagInt, k))
			break;
		SetFlag(FlagInt, k);
	}
	system("Pause");
}
    0
  • G

    Nexus schrieb:

    Hier noch einmal der komplette Code, ich hab noch etwas abgeändert (z.B. Multiplikation mit 2 durch Shift-Operation ersetzt^^)

    Genau das hab ich mir unter "elegant" vorgestellt. Nochmal vielen herzlichen Dank!

    0
  • K

    glis schrieb:

    Nexus schrieb:

    Hier noch einmal der komplette Code, ich hab noch etwas abgeändert (z.B. Multiplikation mit 2 durch Shift-Operation ersetzt^^)

    Genau das hab ich mir unter "elegant" vorgestellt. Nochmal vielen herzlichen Dank!

    Multiplikation mit zwei und Shift-Operationen sind für den Compiler dasselbe. Keins der beiden ist daher effizienter.

    0
Anmelden zum Antworten