014
22.04.2006, 18:02 Uhr
~MartinF
Gast
|
Im folgenden Vergleiche ich den applikativen, rekusiven und imerativen Ansatzt miteinander und mit der Metaprogrammierung. Als Beispiel dient eine Fkt. zum Berechnen der Summe aller Zahlen von na bis nb. Bsp.:
f(3, 5) = 3+4+5 = 12
Hier die unterschiedlichen Deklarationen und Implementierungen der Funktion. Man beachte alle Fkt. führen zu dem gleichen Ergebnis.
| C++: |
// sum.h
#ifndef SUM_H
#define SUM_H
namespace applikativ {
double sum(double na, double nb)
{
double a = na <? nb;
double b = na >? nb;
return (a-a*a+b+b*b)/2;
}
double sum_recursiv(double na, double nb)
{
if (na==nb) return nb;
return na+applikativ::sum_recursiv(na>nb?na-1:na+1, nb);
}
};
namespace imperativ {
double sum(double na, double nb)
{
double a = na <? nb;
double b = na >? nb;
double r = a;
while (a!=b)
r += ++a;
return r;
}
};
namespace meta {
template<int a, int b>
struct min { static const int value; };
template<int a, int b>
const int min<a, b>::value=a<?b;
template<int a, int b>
struct max { static const int value; };
template<int a, int b>
const int max<a, b>::value=a>?b;
template<int na, int nb>
class sum {
private:
enum { min=min<na, nb>::value,
max=max<na, nb>::value };
public:
static const int value;
};
template<int na, int nb>
const int sum<na, nb>::value=(min-min*min+max+max*max)/2;
template<int a, int b>
struct sum_recursiv { static const int value; };
template<int a, int b>
const int sum_recursiv<a,b>::value=
(a==b ? b : (a +sum_recursiv<(a<b ? a+1 : a-1), b>::value));
};
#endif
|
... und der Quelltext der Testapplikation ...
| C++: |
#include "sum.h"
#include <iostream>
using namespace std;
int main()
{
const double v=15;
const double b=-12;
cout << applikativ::sum(v, b) << endl;
cout << applikativ::sum_recursiv(v, b) << endl;
cout << imperativ::sum(v, b) << endl;
cout << meta::sum<15, -12>::value << endl;
cout << meta::sum_recursiv<15, -12>::value << endl;
}
|
Das Programm liefert 5 mal die Zahl 42. Jede der Funktionen gibt wie schon gesagt das richtige Ergebnis zurück. Betrachten wir nun die Performance der jeweiligen Funktionen. Die folgende Abb. liefert einen Überblick über die Funktionen:
Auf der rechten Seite sieht man die Funktionen applikativ::sum, applikativ::sum_recursiv und imperativ::sum. In der Mitte unter main lassen sich zwei Aufrufe der Streamoperatoren erkennen. Der rechte Aufruf repräsentiert den Operator im Zusammenhang mit den oben genannten Funktionen. Der linke Aufruf steht für den Aufruf mit den Metafunktionen. Die Metafunktionen (0,33%) sind also um einiges schneller als die übrigen Fkt. (2,08%), da die Metafunktionen komplett wegoptimiert wurden (genauer gesagt zur Compilierzeit expandiert wurden).
Betrachten wir nun die Funktionen getrennt. Die folgende Abb zeigt die Fkt applikativ::sum
Hierzu lässt sich nicht viel sagen. Die Funktion ermittelt auf direktem Weg das Ergebnis und gibt dieses zurück. Die Fkt. benötigt 0,01% der Laufzeit.
Die Fkt. applikativ::sum_recursiv hingegen benötigt deutlich mehr Laufzeit (0,15%), wie die folgende Grafik zeigt.
Die Funktion ruft sich selbst rekursiv auf. In unserem Beispiel geschieht das 26 mal. Das Overhead der Fkt ist der Grund für den Performanceunterschied.
... und der imperative Ansatz (0,03%) ...
Die Metafunktionen wurden komplett wegoptimiert, wie die folgende Abb zeigt. Es bleibt nur der Streamoperator übrig.
Wir halten also fest ...
1. Metaprogrammierung
2. applikativ
3. imperativ
4. rekursiv
Ich finde das sehr interessant wie man doch Laufzeit einsparen kann.  Beschäftige mich intensiver mit Metaprogrammierung - ein sehr iteressantes Thema. Die hier vorgestellte Metafunktion ist nur ein kleines Bsp. für die Metaprogrammierung. Man kann noch viel mehr Sachen und auch deutlich komplexere Dinge machen; da wären z.B. die Verwendung der type_traits (auch im Zusammenhang mit der Boost-Lib) uvm.
Dieser Post wurde am 22.04.2006 um 18:13 Uhr von MartinF editiert. |
. Bei dem Teil mit der Metafunktion bleibt also nur noch der Aufruf der Streamoperatoren.
.