Performancevergleich einer Implementierung des Quicksort-Algorithmus in den Programmiersprachen C++ und Pascal.
#include <iostream> #include <ctime> using namespace std; const int n = 45; int reihung[n]; void swap(int& a, int& b) { int temp; temp = a; a = b; b = temp; } void ausgeben() { for(int i = 0; i < n; i++) cout << reihung[i] << " "; cout << endl; } int qsort(int i, int j) { int L, R; int pivot; if (i < j) { L = i; R = j; pivot = i; while(i < j) { while(reihung[i] < reihung[pivot]) i++; while(reihung[j] > reihung[pivot]) j--; if (i <= j) { swap(reihung[i], reihung[j]); i++; j--; } } /* while */ ausgeben(); qsort(L, j); qsort(i, R); } /* if */ } int main() { cout << "Quicksort" << endl << endl; srand ( time(NULL) ); /* Zufallsgenerator initialisieren */ for(int i = 0; i < n; i++) reihung[i] = rand()%100; ausgeben(); cout << endl; qsort(0, n-1); cout << endl; ausgeben(); return 0; }
Program qsort; USES Crt; CONST n = 45; VAR Reihung : ARRAY [1..n] OF INTEGER; i : INTEGER; Procedure swap(VAR a, b : INTEGER); VAR temp : INTEGER; Begin temp := a; a := b; b := temp; End; Procedure ausgeben; VAR i : INTEGER; Begin FOR i := 1 TO n DO Write(Reihung[i], ' '); WriteLn; End; Procedure Qsort(i, j : INTEGER); VAR pivo : INTEGER; R, L : INTEGER; Begin if (i < j) THEN Begin L := i; R := j; pivo := i; WHILE (i < j) DO Begin WHILE (Reihung[i] < Reihung[pivo]) DO { von links aus Element > Pivotelement suchen } i := i + 1; WHILE (Reihung[j] > Reihung[pivo]) DO { von rechts aus Element < Pivotelement suchen } j := j - 1; IF (i <= j) THEN { falls Elemente bei der Suche das Pivotelement } Begin { nicht übersprungen haben } swap(Reihung[i], Reihung[j]); { werden sie vertauscht } i := i + 1; { und Zeiger um 1 verschoben } j := j - 1; End; End; {while} { alles links von Pivotelement ist jetzt } ausgeben; { kleiner als alles rechts von ihm } Qsort(L, j); { -> linke Seite sortieren } Qsort(i, R); { -> rechte Seite sortieren } End; {if} End; Begin ClrScr; TEXTCOLOR(white); WriteLn('Quicksort'); WriteLn; randomize; { Zufallsgenerator initialisieren } FOR i := 1 TO n DO Reihung[i] := random(100); ausgeben; WriteLn; Qsort(1, n); WriteLn; ausgeben; End.
Anmerkung: Es wurde darauf geachtet, den Code bei beiden Programmiersprachen so ähnlich wie möglich zu gestalten. Darum wurde bei C++ bewusst auf OOP verzichtet.
C++ | Pascal | |
---|---|---|
Compileraufruf | g++ qsort.cpp -O2 -o qsort | fpc qsort.pas -O2 -oqsort |
Laufzeit | ~ 0.007s | ~ 0.060s |
Anmerkung: Die hier aufgeführten Geschwindigkeiten sind natürlich nur Näherungswerte.
Dies ist ein Beispiel einer möglichen Ausgabe. Anfangs wird ein 45-stelliges Feld durch einen Zufallsgenerator generiert und anschließend ausgegeben. Danach erfolgt das sortieren, wie man an den aufgeführten Zwischenschritten erkennen kann. Am Ende ist das fertig sortierte Feld sichtbar.
Quicksort 64 88 89 80 55 99 42 46 41 74 63 39 44 24 4 94 35 4 38 92 99 98 60 62 39 57 2 98 39 32 10 3 72 99 36 80 50 30 26 44 57 41 83 1 17 17 1 3 10 2 4 4 46 41 74 63 39 44 24 42 94 35 99 38 92 99 98 60 62 39 57 55 98 39 32 80 89 72 99 36 80 50 30 26 44 57 41 83 88 64 4 1 3 4 2 10 17 46 41 74 63 39 44 24 42 94 35 99 38 92 99 98 60 62 39 57 55 98 39 32 80 89 72 99 36 80 50 30 26 44 57 41 83 88 64 2 1 3 4 4 10 17 46 41 74 63 39 44 24 42 94 35 99 38 92 99 98 60 62 39 57 55 98 39 32 80 89 72 99 36 80 50 30 26 44 57 41 83 88 64 1 2 3 4 4 10 17 41 26 30 36 39 32 24 39 39 35 38 99 92 99 98 60 62 94 57 55 98 42 44 80 89 72 99 63 80 50 74 41 44 57 46 83 88 64 1 2 3 4 4 10 17 38 26 30 36 35 32 24 39 39 39 41 99 92 99 98 60 62 94 57 55 98 42 44 80 89 72 99 63 80 50 74 41 44 57 46 83 88 64 1 2 3 4 4 10 17 24 26 30 32 35 36 38 39 39 39 41 64 46 57 44 60 62 41 57 55 50 42 44 63 89 72 99 80 80 98 74 94 98 99 92 83 88 99 1 2 3 4 4 10 17 24 26 30 32 35 36 38 39 39 39 41 63 46 57 44 60 62 41 57 55 50 42 44 64 89 72 99 80 80 98 74 94 98 99 92 83 88 99 1 2 3 4 4 10 17 24 26 30 32 35 36 38 39 39 39 41 44 42 41 44 60 62 57 57 55 50 46 63 64 89 72 99 80 80 98 74 94 98 99 92 83 88 99 1 2 3 4 4 10 17 24 26 30 32 35 36 38 39 39 39 41 41 42 44 44 60 62 57 57 55 50 46 63 64 89 72 99 80 80 98 74 94 98 99 92 83 88 99 1 2 3 4 4 10 17 24 26 30 32 35 36 38 39 39 39 41 41 42 44 44 46 50 55 57 57 60 62 63 64 88 72 83 80 80 74 98 94 98 99 92 99 89 99 1 2 3 4 4 10 17 24 26 30 32 35 36 38 39 39 39 41 41 42 44 44 46 50 55 57 57 60 62 63 64 74 72 83 80 80 88 98 94 98 99 92 99 89 99 1 2 3 4 4 10 17 24 26 30 32 35 36 38 39 39 39 41 41 42 44 44 46 50 55 57 57 60 62 63 64 72 74 83 80 80 88 98 94 98 99 92 99 89 99 1 2 3 4 4 10 17 24 26 30 32 35 36 38 39 39 39 41 41 42 44 44 46 50 55 57 57 60 62 63 64 72 74 80 80 83 88 89 92 94 98 98 99 99 99 1 2 3 4 4 10 17 24 26 30 32 35 36 38 39 39 39 41 41 42 44 44 46 50 55 57 57 60 62 63 64 72 74 80 80 83 88 89 92 94 98 98 99 99 99
Anmerkung: Die Ausgabe wurde gekürzt, da es durch Rekursion zu einer mehrfachen Ausgabe des Feldes mit dem gleichen Inhalt kommt. Aus diesem Grund kann auch nicht jeder Einzelschritt ausgegeben werden.
Performancevergleich von Implementierungen einer verketteten Liste in den Programmiersprachen C++ und Pascal.
Es wird eine dynamische Datenstruktur (Liste) mit 30 000 Elementen angelegt, denen per Zufallsgenerator ein Wert zugewiesen wird. Dabei wird die Zeit gemessen, die zum Anlegen der Elemente und Zuweisen der Werte benötigt wird.
#include <iostream> #include <ctime> using namespace std; const int n = 30*1000; int main() { struct Zeiger { int Daten; Zeiger *next; }; cout << "verkettete Liste" << endl << endl; srand ( time(NULL) ); /* Zufallsgenerator initialisieren */ Zeiger *Element = new Zeiger; Zeiger *Anfang = new Zeiger; Anfang->next = NULL; Element = Anfang; for(int i = 0; i < n; i++) { Zeiger *Neu = new Zeiger; Element->next = Neu; Neu->next = NULL; Element = Neu; Neu->Daten = rand()%100; } /*Element = Anfang; while(Element->next != NULL) { Element = Element->next; cout << Element->Daten << endl; }*/ return 0; }
Program List; USES Crt; CONST n = 30*1000; TYPE Zeiger = ^Liste; Liste = RECORD Daten : INTEGER; Next : Zeiger; End; VAR Anfang, Element, Neu : Zeiger; i : INTEGER; Begin ClrScr; TEXTCOLOR(white); randomize; { Zufallsgenerator initialisieren } WriteLn('verkettete Liste'); WriteLn; NEW (Anfang); Anfang^.next := NIL; Element := Anfang; FOR i := 0 TO n DO Begin NEW (Neu); { neues Element erzeugen } Element^.next := Neu; { Nachfolger vom aktuellen Element wird das Neue } Neu^.next := NIL; { Nachfolger vom neuen Element wird NIL } Element := Neu; { neues Element ist nun aktuelles Element } Neu^.Daten := random(100); End; {Element := Anfang; WHILE (Element <> NIL) DO Begin WriteLn(Element^.Daten); Element := Element^.next; End;} End.
Anmerkung: Der Code zum Ausgeben der Listeninhalte wurde bewusst auskommentiert, da die Programmausgabe einen wesentlichen Teil der Gesamtzeit in Anspruch nimmt und das Ergebnis dadurch u.U. verfälschen kann.
Zusätzlich mussten die Elemente der Liste auf 30 000 begrenzt werden, da man in Pascal anscheinend keine größeren Konstanten definieren kann (geplant waren ursprünglich mehrere Millionen Elemente, was sich in C++ auch problemlos umsetzen ließ). Eine größere Anzahl an Elementen hätte zu einer genaueren Zeitmessung geführt, da sich die Ablaufdauer der Programme im Bereich von wenigen Millisekunden bewegen.
C++ | Pascal | |
---|---|---|
Compileraufruf | g++ list.cpp -O2 -o list | fpc list.pas -O2 -olist |
Laufzeit | ~ 0.009s | ~ 0.042s |
Anmerkung: Die hier aufgeführten Geschwindigkeiten sind natürlich nur Näherungswerte.
Performancevergleich von Implementierungen einer binären Suche in den Programmiersprachen C++ und Pascal.
#include <iostream> using namespace std; const int n = 32767; int Reihung[n]; void fill() { for(int i = 1; i <= n; i++) Reihung[i] = i; } bool bsearch(int L, int R, int Key) { if (L > R) { cout << "Der Suchschlüssel " << Key << " ist nicht enthalten." << endl; return false; } else { int center = (L + R) / 2; if (Key > Reihung[center]) bsearch(center+1, R, Key); else if (Key < Reihung[center]) bsearch(L, center-1, Key); else { cout << "Der Suchschlüssel " << Key << " ist an Stelle " << center << " zu finden." << endl; return true; } } } int main() { cout << "binäre Suche" << endl; fill(); bsearch(1, n, 1); return 0; }
Program bin_search; USES Crt; CONST n = 32767; VAR Reihung : ARRAY [1..n] OF INTEGER; Procedure fill; VAR i : INTEGER; Begin FOR i := 1 TO n DO Reihung[i] := i; End; Function bsearch(L, R, Key : INTEGER) : BOOLEAN; VAR center : INTEGER; Begin IF (L > R) THEN Begin bsearch := false; WriteLn('Der Suchschlüssel ', Key, ' ist nicht enthalten.'); End ELSE Begin center := (L+R) DIV 2; IF (Key > Reihung[center]) THEN bsearch := bsearch(center+1, R, Key) ELSE IF (Key < Reihung[center]) THEN bsearch := bsearch(L, center-1, Key) ELSE Begin bsearch := true; WriteLn('Der Suchschlüssel ', Key, ' ist an Stelle ', center, ' zu finden.'); End; End; End; Begin ClrScr; TEXTCOLOR(white); WriteLn('binäre Suche'); WriteLn; fill; bsearch(1, n, 1); End.
Anmerkung: Zur fairen Ermittlung der Ablaufdauer werden die Feldinhalte und Suchschlüssel nicht zufällig ermittelt, sondern sind bereits im Code definiert.
Zusätzlich mussten die Elemente der Felder auf 32 767 begrenzt werden, da man in Pascal anscheinend keine größeren Konstanten definieren kann (was in C++ problemlos möglich ist). Eine größere Anzahl an Elementen hätte zu einer genaueren Zeitmessung geführt, da sich die Ablaufdauer der Programme im Bereich von wenigen Millisekunden bewegen.
C++ | Pascal | |
---|---|---|
Compileraufruf | g++ bin_search.cpp -O2 -o bin_search | fpc bin_search.pas -O2 -obin_search |
Laufzeit | ~ 0.004s | ~ 0.035s |
Anmerkung: Die hier aufgeführten Geschwindigkeiten sind natürlich nur Näherungswerte.