Funktion schöner gestallten?

Hi,

ich habe mir folgende Funktion geschrieben um den nächstgrößten "power of two" wert zu bekommen.

unsigned int my_power_of_two_floor (unsigned int value)
{
    unsigned int result = 0;
    for (unsigned int i = 0; result <= value; result = 1 << ++i);

    return (result);
}

Jedoch irgendwie bin ich mit der nicht so richtig zufrieden. Dazu such ich noch nach einem Ansatz wegen einer ceil Funktion.

Hat jemand da ein paar Ideen?

Xin

meiong schrieb:

Hat jemand da ein paar Ideen?

Mach eine binäre Suche nach dem ersten gesetzten Bit.
Damit hast Du konstant 5 Abfragen.

Deine Methode benötigt weniger Durchläufe, wenn Du kleinere Zahlen als 32 als Parameter übergibst.
Im Worst Case braucht Du 32 Durchläufe.

Konrad Rudolph

Ich würd's natürlich wie immer rekursiv machen; diese Variante hat nur den Nachteil, dass der Fall 'value == 0' in einer Endlosschleife landet bzw. (wenn man die erste Bedingung lockert) ein falsches Resultat (1 statt 0) liefert.

unsigned int pow_2_floor(unsigned int value, unsigned int accu = 1)
{
    if (value == 1) return accu;
    return pow_2_floor(value >> 1, accu << 1);
}

Was die Binärsuche anbelangt: Gute Idee, wahrscheinlich aber trotzdem langsamer.

Xin

Konrad Rudolph schrieb:

Ich würd's natürlich wie immer rekursiv machen; diese Variante hat nur den Nachteil, dass der Fall 'value == 0' in einer Endlosschleife landet bzw. (wenn man die erste Bedingung lockert) ein falsches Resultat (1 statt 0) liefert.
unsigned int pow_2_floor(unsigned int value, unsigned int accu = 1)
{
    if (value == 1) return accu;
    return pow_2_floor(value >> 1, accu << 1);
}
Was die Binärsuche anbelangt: Gute Idee, wahrscheinlich aber trotzdem langsamer.

5 Abfragen langsamer als im Schnitt 16 mal eine Funktion rufen (Stack aufbauen, füllen, springen, abfragen, zurückspringen, Stack abbauen)?

Rekursiv zu programmieren ist elegant. Eine billige Schleife ist vielleicht nicht so elegant, aber fast immer schneller.

Da es sich um konstant 5 Abfrage Hirachien handelt, würde ich mir die Schleife auch sparen und die 32 Abfragen komplett schreiben, das spart zusätzlich den Zustand der Funktion in Variablen zu speichern und geht damit noch ein wenig schneller.

Konrad Rudolph

Xin schrieb:

Rekursiv zu programmieren ist elegant. Eine billige Schleife ist vielleicht nicht so elegant, aber fast immer schneller.

Ich verlasse mich auf die Tail recursion optimization. Im Idealfall müsste der Compiler für beide Varianten identischen Code erzeugen. Macht er leider nicht aber mit /O2 in Visual Studio 2005 kompiliert, ergibt sich kein erkennbarer Unterschied – mal ist die eine Variante schneller, mal die andere.

5 Abfragen langsamer als im Schnitt 16 mal eine Funktion rufen?

Ich wäre ja sehr an dem Code interesiert. Zeig den doch mal. Von der asymptotischen Laufzeit her hast Du sicherlich recht.

Da es sich um konstant 5 Abfrage Hirachien handelt, würde ich mir die Schleife auch sparen und die 32 Abfragen komplett schreiben, das spart zusätzlich den Zustand der Funktion in Variablen zu speichern und geht damit noch ein wenig schneller.

Da hast Du recht aber da kommt man langsam in den Bereich, wo man eine komplette Tabelle anlegen kann (gut, für nen int32 sicherlich nicht, aber für ein Byte z.B. schon). Da hat man dann einen einzigen Zugriff.

Xin

Konrad Rudolph schrieb:

Xin schrieb:

Rekursiv zu programmieren ist elegant. Eine billige Schleife ist vielleicht nicht so elegant, aber fast immer schneller.

Ich verlasse mich auf die Tail recursion optimization. Im Idealfall müsste der Compiler für beide Varianten identischen Code erzeugen.

Höre niemals auf Aussagen, die "müsste" enthalten, denn...

Konrad Rudolph schrieb:

Macht er leider nicht [...]

Ich mache mich ungern vom Compiler abhängig.

Konrad Rudolph schrieb:

5 Abfragen langsamer als im Schnitt 16 mal eine Funktion rufen?

Ich wäre ja sehr an dem Code interesiert. Zeig den doch mal. Von der asymptotischen Laufzeit her hast Du sicherlich recht.

Ich brauche die Funktion jetzt nicht, ergo schreibe ich sie auch nicht.
Der Aufbau wäre etwa so:

unsigned int my_power_of_two_floor (unsigned int value) 
{ 
  return ( ((short*)&value)[0] )
         ? ( (char*)&value)[0] )
           ? (char*)&value)[0] & 0xF0
             ? (char*)&value)[0] & 0xC0
               ? (char*)&value)[0] & 0x80
                 ? 0                              // 0x80000000 Überlauf
                 : 1 << 31                        // 0x40000000
               : (char*)&value)[0] & 0x20
                 ? 1 << 30                        // 0x20000000
                 : 1 << 29                        // 0x10000000
             ? (char*)&value)[0] & 0x0F
               ? (char*)&value)[0] & 0x08
                 ? 1 << 28                        // 0x08000000 
                 : 1 << 27                        // 0x04000000
               : (char*)&value)[0] & 0x02
                 ? 1 << 26                        // 0x02000000
                 : 1 << 25                        // 0x01000000
            : usw...
}

Vielleicht nicht elegant, aber dafür konstante und schnelle Laufzeit.
Der Code oben sollte noch durch eine Kontrolle der Prozessorarchitektur erweitert werden, die beim Compilieren die Funktion auf die jeweilige Architektur anpasst.

Wenn Du es eleganter brauchst, nehme er eine inline template Funktion.

Konrad Rudolph schrieb:

Da es sich um konstant 5 Abfrage Hirachien handelt, würde ich mir die Schleife auch sparen und die 32 Abfragen komplett schreiben, das spart zusätzlich den Zustand der Funktion in Variablen zu speichern und geht damit noch ein wenig schneller.

Da hast Du recht aber da kommt man langsam in den Bereich, wo man eine komplette Tabelle anlegen kann (gut, für nen int32 sicherlich nicht, aber für ein Byte z.B. schon). Da hat man dann einen einzigen Zugriff.

Das erkläre mir mal, wie man den Bereich eines Bytes - also 256 Möglichkeiten - mit einem einzigen Zugriff abdeckt, ich lerne gerne dazu.

Konrad Rudolph

Xin schrieb:

Das erkläre mir mal, wie man den Bereich eines Bytes - also 256 Möglichkeiten - mit einem einzigen Zugriff abdeckt, ich lerne gerne dazu.

unsigned int const POW_2_FLOOR_TABLE[] = {
    0, 1, 2, 2, 4, 4, 4, 4, 8, 8, 8, 8, 8, 8, 8, 8,
    16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16,
    32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32,
    32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32,
    64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64,
    64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64,
    64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64,
    64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64,
    // …
};

unsigned int pow_2_floor(unsigned int value)
{
    return POW_2_FLOOR_TABLE[value];
}

Konrad Rudolph

Xin schrieb:

Ich mache mich ungern vom Compiler abhängig.

Sicher, das ist verständlich.

Auf der anderen Seite gibt es einfach gewisse Mindestanforderungen, die man an einen modernen Compiler stellen kann und auch stellen *sollte*. IMHO gehören einige billige Optimierungstechniken dazu; die von mir verwendete Form der Endrekursion ist absolut trivial optimierbar. Daher setze ich sie voraus.

Xin

Konrad Rudolph schrieb:

Xin schrieb:

Das erkläre mir mal, wie man den Bereich eines Bytes - also 256 Möglichkeiten - mit einem einzigen Zugriff abdeckt, ich lerne gerne dazu.

unsigned int const POW_2_FLOOR_TABLE[] = {
    0, 1, 2, 2, 4, 4, 4, 4, 8, 8, 8, 8, 8, 8, 8, 8,
    16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16,
    32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32,
    32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32,
    64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64,
    64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64,
    64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64,
    64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64,
    // …
};

unsigned int pow_2_floor(unsigned int value)
{
    return POW_2_FLOOR_TABLE[value];
}

*lach* Okay, Du gewinnst.

Ich war fest von einem Algorithmus ausgangen und dachte, Du wolltest auf Switch hinaus.
Manchmal sieht man den Wald vor lauter Bäumen nicht. ^^

In Kombination mit der binären Suche - welches Byte an die Tabelle übergeben - kommt man so auf 3 konstante Abfragen runter. Ziemlich gut.

Konrad Rudolph schrieb:

Xin schrieb:

Ich mache mich ungern vom Compiler abhängig.

Sicher, das ist verständlich.

Auf der anderen Seite gibt es einfach gewisse Mindestanforderungen, die man an einen modernen Compiler stellen kann und auch stellen *sollte*. IMHO gehören einige billige Optimierungstechniken dazu; die von mir verwendete Form der Endrekursion ist absolut trivial optimierbar. Daher setze ich sie voraus.

Es gibt auch gewisse Mindestanforderungen, die man an den Programmierer setzen darf.