Ich möchte einen zweiten Benchmark machen und zwar diesmal mit einem Quicksort. Dafür bin ich wieder an kurzen Implementierungen des Quicksort in unterschiedlichen Sprachen interessieren, da es mir nicht nur um Ausführungsgeschwindigkeit, sondern auch um Quelltextlänge und Verständlichkeit des Quelltextes geht.
Der erste Quelltext im nachfolgenden Posting ist in GeCCo, was eine Mischung aus Großvater von Genesys darstellt und Experiment in Sachen Compilerbau.
GeCCo steht für Genesys-C-Compiler, damals sollte das eine Vorstufe darstellen, weil ich auf C++ aufbauen wollte. Dieser Quelltext wurde erfolgreich in Bytecode kompiliert und als Bytecode ausgeführt. Den Quelltext möchte ich nun nachbilden - so kurz wie möglich und dann auch wieder Geschwindigkeitstest laufen lassen. Das Programm würde ich nun gerne in Genesys sinnvoll umschreiben.
QSort dürfte gerade in funktionalen Sprachen hübscher wirken.
Im nächsten Posting sammle ich Implementationen und Laufzeiten.
QSort / Benchmark
- Xin
- nur zu Besuch hier
- Beiträge: 8862
- Registriert: Fr Jul 04, 2008 11:10 pm
- Wohnort: /home/xin
- Kontaktdaten:
QSort / Benchmark
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.
Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.
Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.
- Xin
- nur zu Besuch hier
- Beiträge: 8862
- Registriert: Fr Jul 04, 2008 11:10 pm
- Wohnort: /home/xin
- Kontaktdaten:
Re: QSort / Benchmark
GeCCo-Quelltext
Code: Alles auswählen
void myqsort(char * Array, long Low, long High, long e)
{
char ref, x;
long l, r;
x = (Low + High) >> 1;
ref = /*(char)*/Array[ x ];
l = Low; r = High;
if( Low < High )
{
while( l < r )
{
while( Array[l] < ref )
l=l+1;
while( Array[r] > ref )
r=r-1;
if(l <= r)
{
x = Array[l];
Array[l] = Array[r];
Array[r] = x;
l=l+1; r=r-1;
}
}
if(l < High) myqsort(Array, l, High, e+1);
if(Low < r) myqsort(Array, Low, r, e+1);
}
}
long strlen( char * Text )
{
long a;
a=0;
while( Text[a] != 0)
a=a+1;
return a;
}
void main(void)
{
char *Text;
char Array[11];
char a;
Array[ 0] = 'I';
Array[ 1] = 'N';
Array[ 2] = 'F';
Array[ 3] = 'O';
Array[ 4] = 'R';
Array[ 5] = 'M';
Array[ 6] = 'A';
Array[ 7] = 'T';
Array[ 8] = 'I';
Array[ 9] = 'K';
Array[10] = '\0';
print "Sortiere String \"", Array, "\" => \"";
myqsort(Array, 0, strlen( Array ) - 1, 1);
print Array, "\" L?nge: ", strlen( Array ), "\n";
Text = "zyxwvutsrqponmlkjihgfedcba0987654321ZYXWVUTSRQPONMLKJIHGFEDCBA";
print Text; print;
myqsort(Text, 0, strlen( Text ) - 1, 1);
print Text; print;
}
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.
Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.
Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.
- Xin
- nur zu Besuch hier
- Beiträge: 8862
- Registriert: Fr Jul 04, 2008 11:10 pm
- Wohnort: /home/xin
- Kontaktdaten:
Re: QSort / Benchmark
So... QSort läuft... nicht sonderlich schnell, aber immerhin. Ich habe dafür das Array "erfinden" dürfen und weil ich Buchstaben sortieren wollte, musste ich erstmal einen Datentyp 'char' erfinden und durfte weitere dutzende Baustellen beackern.
Aber nach gut einer Woche Arbeit läuft nun ein selbst geschriebener Quicksort, leider noch nicht benchmarkfähig, weil z.B. Operatoren wie "x++" noch fehlen. Aber er sortiert zumindest schonmal.
Diesem Benchmark kommen wir also schonmal bin ich also schonmal ein gutes Stück näher.
Mochte sich niemand mit dem Quicksort freiwillig auseinander setzen?![Very Happy :D](./images/smilies/icon_e_biggrin.gif)
Aber nach gut einer Woche Arbeit läuft nun ein selbst geschriebener Quicksort, leider noch nicht benchmarkfähig, weil z.B. Operatoren wie "x++" noch fehlen. Aber er sortiert zumindest schonmal.
Diesem Benchmark kommen wir also schonmal bin ich also schonmal ein gutes Stück näher.
Mochte sich niemand mit dem Quicksort freiwillig auseinander setzen?
![Very Happy :D](./images/smilies/icon_e_biggrin.gif)
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.
Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.
Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.
Re: QSort / Benchmark
Ich hätte Ada anzubieten.
Ich habe versucht, das möglichst 1:1 umzusetzen, kann man sicher wesentlich kürzer (und wesentlich schöner) schreiben.
Ich habe versucht, das möglichst 1:1 umzusetzen, kann man sicher wesentlich kürzer (und wesentlich schöner) schreiben.
Code: Alles auswählen
with Ada.Text_IO;
with Ada.Strings;
procedure Qsort is
procedure myqsort(arr : in out String; low : Integer; high : Integer; depth : Integer) is
x : Integer := (low + high) / 2 + 1;
c : Character := arr(x);
l : Integer;
r : Integer;
ref : Character;
begin
l := low;
r := high;
ref := arr(x);
if low < high then
iterate : while l < r loop
l1 : while arr(l) < ref loop
l := l + 1;
end loop l1;
l2 : while arr(r) > ref loop
r := r - 1;
end loop l2;
if l <= r then
c := arr(l);
arr(l) := arr(r);
arr(r) := c;
l := l + 1;
r := r - 1;
end if;
end loop iterate;
end if;
if l < high then
myqsort(arr, l, high, depth + 1);
end if;
if low < r then
myqsort(arr, low, r, depth + 1);
end if;
end myqsort;
Arr : String := "INFORMATIK";
begin
Ada.Text_IO.Put("Sortiere String " & Arr & " => ");
myqsort(Arr, arr'First, arr'Last, 1);
Ada.Text_IO.Put_Line(Arr);
end Qsort;
It's as simple as that. And remember, Beethoven wrote his first symphony in C.
- Xin
- nur zu Besuch hier
- Beiträge: 8862
- Registriert: Fr Jul 04, 2008 11:10 pm
- Wohnort: /home/xin
- Kontaktdaten:
Re: QSort / Benchmark
Ada hatte ich auch noch nicht, scheint aber geschwätziger zu sein... da muss ich erstmal rausfinden, wie man das kompiliert. ^^
Den Quellcode, den ich da veröffentlicht habe, soll auch nicht unbedingt das Non-Plus-Ultra darstellen. Er ist das, was mit dem damaligen Gecco-Compiler machbar war. Tatsächlich sieht der Genesys-Code derzeit noch sehr ählich aus, aber ich mache die Benchmarks nicht nur, um Speedtests zu machen, sondern auch um Programmlänge und Programmverständlichkeit zu vergleichen.
Eine schickere Version wäre also durchaus gewünscht, denn ich werde mich bemühen, auf dem gegenwärtigen Quelltext nicht sitzen zu bleiben: Das muss kürzer werden. ^^
Vor zwei Tagen zeigte mir jemand eine Haskell-Variante, die mir prinzipiell sehr gut gefällt, aber eben auch nicht direkt vergleichbar ist:
Zu finden auf der Haskell-Introduction-Seite
Dort findet sich auch eine der C-Version entsprechende Version:
Da nimmt das Vergnügen dann langsam schon wieder ab.
Den Quellcode, den ich da veröffentlicht habe, soll auch nicht unbedingt das Non-Plus-Ultra darstellen. Er ist das, was mit dem damaligen Gecco-Compiler machbar war. Tatsächlich sieht der Genesys-Code derzeit noch sehr ählich aus, aber ich mache die Benchmarks nicht nur, um Speedtests zu machen, sondern auch um Programmlänge und Programmverständlichkeit zu vergleichen.
Eine schickere Version wäre also durchaus gewünscht, denn ich werde mich bemühen, auf dem gegenwärtigen Quelltext nicht sitzen zu bleiben: Das muss kürzer werden. ^^
Vor zwei Tagen zeigte mir jemand eine Haskell-Variante, die mir prinzipiell sehr gut gefällt, aber eben auch nicht direkt vergleichbar ist:
Code: Alles auswählen
quicksort :: Ord a => [a] -> [a]
quicksort [] = []
quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)
where
lesser = filter (< p) xs
greater = filter (>= p) xs
Dort findet sich auch eine der C-Version entsprechende Version:
Code: Alles auswählen
import Data.Array.Base (unsafeRead, unsafeWrite)
import Data.Array.ST
import Control.Monad.ST
myqsort :: STUArray s Int Int -> Int -> Int -> ST s ()
myqsort a lo hi
| lo < hi = do
let lscan p h i
| i < h = do
v <- unsafeRead a i
if p < v then return i else lscan p h (i+1)
| otherwise = return i
rscan p l i
| l < i = do
v <- unsafeRead a i
if v < p then return i else rscan p l (i-1)
| otherwise = return i
swap i j = do
v <- unsafeRead a i
unsafeRead a j >>= unsafeWrite a i
unsafeWrite a j v
sloop p l h
| l < h = do
l1 <- lscan p h l
h1 <- rscan p l1 h
if (l1 < h1) then (swap l1 h1 >> sloop p l1 h1) else return l1
| otherwise = return l
piv <- unsafeRead a hi
i <- sloop piv lo hi
swap i hi
myqsort a lo (i-1)
myqsort a (i+1) hi
| otherwise = return ()
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.
Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.
Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.
Re: QSort / Benchmark
Die kürzeste (und wahrscheinlich beste) Version in Ada wär' wohl
Aber die willst Du wahrscheinlich nicht, oder? ![Wink ;)](./images/smilies/icon_e_wink.gif)
Code: Alles auswählen
Ada.Containers.Generic_Array_Sort (arr);
![Wink ;)](./images/smilies/icon_e_wink.gif)
It's as simple as that. And remember, Beethoven wrote his first symphony in C.
- Xin
- nur zu Besuch hier
- Beiträge: 8862
- Registriert: Fr Jul 04, 2008 11:10 pm
- Wohnort: /home/xin
- Kontaktdaten:
Re: QSort / Benchmark
Nein... ^^
Vielleicht die Implementierung davon...
Vielleicht die Implementierung davon...
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.
Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.
Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.