Türme von Hanoi

Eydeet · Jun 22, 2011

OT:
Zu dem Rekursions-Ding möchte ich auch noch etwas beitragen.
Wenn man die Fibonacci-Folge wie CDW implementiert, dann können moderne Compiler die Rekursion wegoptimieren (-> Tail Recursion). Damit sollte sich auch das Problem mit überlaufenden Stacks erledigt haben.
Ich habe mal ein kleines Testprogramm geschrieben, das CDWs Implementation mit dieser iterativen vergleicht:

Code:

long fibi(long a)
{
    long fib0 = 0, fib1 = 1, fib2, i;
    for (i = 2; i < a; i++) {
        fib2 = fib0 + fib1;
        fib0 = fib1;
        fib1 = fib2;
    }
    return fib2;
}

Die Ergebnisse sind folgende, für die Berechnung von 10000 Fibonacci-Zahlen (1..9999) (GCC 4.2.1):

Code:

O0:
rek clocks: 422393
itr clocks: 223544

O2:
rek clocks: 50335
itr clocks: 51078

Os:
rek clocks: 24751
itr clocks: 57327

rek ist das rekursive, itr, das iterative Programm.

Damit wird deutlich, dass der Compiler rekursive Programme in zumindest machen Fällen besser optimieren kann als iterative. Eine Verteufelung dieser ist damit meiner Meinung nach nicht gerechtfertigt.

Die schnellste Implementation sollte übrigens diese sein:

Code:

long fib(long a)
{
    const double phi = 1.6180339887498949;
    const double sq5 = 2.2360679774997898;
    return (long)(0.5 + pow(phi, a) / sq5);
}

// Edit
B2T:

Auch die beiden (bisher ähnlich schon aufgetauchten) Hanoi-Varianten, rekursiv und iterativ, möchte ich noch einmal gegeneinander stellen.

Code:

long dummy = 0, dummy2 = 0;

void hanoi_r(a, b, c, h)
{
    if (h > 1) {
        hanoi_r(a, c, b, h-1);
        hanoi_r(a, b, c, 1);
        hanoi_r(b, a, c, h-1);
    } else {
        dummy += a - c;
        //printf("Lege Scheibe von %d nach %d\n", a, c);
    }
}

void hanoi_i(h)
{
    int x;
    for (x = 1; x < (1 << h); x++) {
        int a = (x & x-1) % 3;
        int c = ((x | x - 1) + 1) % 3;
        dummy2 += a - c;
        //printf("Lege Scheibe von %d nach %d\n", a, c);
    }
}

Die Dummy-Counter haben nur den Zweck, dass der Compiler mir die Schleifen nicht komplett wegoptimiert. Die Ausgabe ist natürlich auskommentiert, da hier der größte Teil der Rechenzeit verbraucht wird.
Eine Performance-Messung für eine Höhe von 28 ergibt bei mir folgende Ergebnisse:

Code:

unoptimiert (GCC 4.2.1):
hanoi_r clocks: 3243513
hanoi_i clocks: 3290201

O3-optimiert (GCC 4.2.1):
hanoi_r clocks: 1358059
hanoi_i clocks: 1584307

O3-optimiert (LLVM-GCC 4.2):
hanoi_r clocks: 1085470
hanoi_i clocks: 1908822

Dass auch hier die rekursive Variante wieder besser abschneidet wundert auch mich, aber es zeigt, dass Rekursion, wie CDW schon gesagt hat, einen viel zu schlechten Ruf hat. Ich vermute mal, dass sich die rekursive Version besser optimieren lässt, da rekursiv aufgeschriebene Algorithmen oft mathematisch besser handhabbar sind.

Türme von Hanoi

Eydeet

0