Diskussion:C++-Programmierung/ Brüche/ Die Methoden

Aus dem Artikel:

Beachten Sie, das diese Funktion rekursiv funktioniert. Die Implementierung als einfache Schleife, wäre ebenfalls möglich gewesen, aber sie ist erstens länger und zweitens langsamer.

Das wage ich zu bezweifeln: Rekursive Funktionen sind in der Regel langsamer und verbrauchen mehr Ressourcen. Das bestätigt auch ein Test:

• ggT-iterativ.cc: Testprogramm mit konventioneller Schleife:

unsigned int ggT(unsigned int a, unsigned int b){
  while(b != 0)
  {
    int c = a%b;
    a = b;
    b = c;
  }
  return a;
}

volatile int k;

int main()
{
  for (int i = 1; i < 10000; ++i)
    for (int j = 1; j < 10000; ++j)
      k = ggT(i, j);
}

• ggT-rekursiv.cc: Testprogramm mit der ggT-Routine aus dem Artikel.
• Compiler: gcc-Version 4.1.2 20061115 (prerelease) (SUSE Linux)

Test ohne Optimierung (kein -O):

> time ./ggT-iterativ 

real    0m13.860s
user    0m13.809s
sys     0m0.052s

> time ./ggT-rekursiv 

real    0m15.078s
user    0m15.025s
sys     0m0.052s

Das sind beides typische Durchläufe (die Zeiten schwanken um Bruchteile von Sekunden). Man sieht, die Rekursion ist klar langsamer. Allerdings ändert sich das Bild mit Optimierung: Test mit Optimierung (-O3):

> time ./ggT-iterativ 

real    0m11.347s
user    0m11.349s
sys     0m0.000s

> time ./ggT-rekursiv 

real    0m11.477s
user    0m11.473s
sys     0m0.000s

Immer noch hat die Iterative Version nur noch einen vernachlässigbar kleinen Vorteil. Ein Blick in den erzeugten Assemblercode bringt Klarheit: Der Compiler hat bei der rekursiven Definition die Rekursion in eine Iteration optimiert; der optimierte Code ist also iterativ. Der geringe Geschwindigkeitsvorteil der iterativen Version beruht darauf, dass der Compiler den iterativen Code in die main-Funktion geinlined hat, was er beim rekursiven Code nicht macht. Rekursive Funktionen können nicht geinlined werden, und offenbar hat der Inliner seine Entscheidung schon getroffen, bevor die Rekursion wegoptimiert wurde.

Angesichts des beim optimierten Code vernachlässigbaren Geschwindigkeitsvorteils kann man die Verwendung der rekursiven Variante hier durchaus vertreten (bekanntlich ist voreilige Optimierung ja die Quelle allen Übels :-)), nur sollte man nicht behaupten, die iterative Variante sei langsamer.

Zudem: Den Ausdruck in der kgV-Funktion würde ich umschreiben in

return a/ggT(a,b) * b;

Das vermeidet einen Overflow in Fällen, in denen zwar das Produkt, nicht aber der kgV zu groß wird. Die Umstellung ist in diesem Fall problemlos möglich, da ja der ggT(a,b) per definitionem Teiler von a ist. --Ce 20:59, 3. Sep. 2007 (CEST)

Hab es geändert. Hab bei mir übrigens auch mal die Zeiten getestet, bei -O3 ist die Rekursivvariante interessanterweise etwas schneller (GCC 4.1.3 auf Debian testing). Den Assemblercode hab ich mir jetzt allerdings nicht erst angesehen, der Zeitunterschied liegt auch nur bei etwa 150ms. Ich will jetzt nicht darüber diskutieren, ob Rekursion schneller als Schleifen ist (Schleifen sind letztenendes definitiv schneller), ich möchte lediglich darauf hinweisen das die Compileroptimierung da offenbar sehr gute Ergebnisse liefern kann. --Prog 23:49, 3. Sep. 2007 (CEST)

Die im Kapitel gezeigte Version ist eine besondere Form der Rekursion, eine sogenannte "Endrekursive Funktion". Diese kann der Compiler in der Tat so optimieren, dass sie genauso schnell (im Rahmen der Messgenauigkeit) wie eine iterative Funktion ist. Außerdem hat diese Optimierung den Vorteil, dass sie mit dem relativ knappen Stack-Speicher schonend umgeht, da die rekursiven Funktionsaufrufe alle den gleichen Stackframe benutzen können (und dies beim gcc ab -O2 auch tun :-)). Bei großem Nenner wäre nämlich die Schachtelungstiefe so groß, dass es auf manchen Systemen zum Stacküberlauf kommen kann. --RokerHRO 12:13, 3. Jan. 2008 (CET)

unsigned/signed, mal wieder

Die Klasse Bruch benutzt vorzeichenbehaftete Zähler. Diese werden dann recht brutal in einen (meist großen) unsigned-Wert gecastet, wenns ans ggT-Berechnen geht. Das kann zu bösen Überraschungen führen. --RokerHRO 12:13, 3. Jan. 2008 (CET)