Seite 1 von 1
QSort / Benchmark
Verfasst: Mi Mär 08, 2017 11:21 am
von Xin
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.
Re: QSort / Benchmark
Verfasst: Mi Mär 08, 2017 11:23 am
von Xin
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;
}
Re: QSort / Benchmark
Verfasst: Di Mär 14, 2017 9:24 pm
von Xin
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?
Re: QSort / Benchmark
Verfasst: Do Mär 16, 2017 10:06 pm
von mfro
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.
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;
Re: QSort / Benchmark
Verfasst: Fr Mär 17, 2017 11:51 am
von Xin
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:
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
Zu finden auf der
Haskell-Introduction-Seite
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 ()
Da nimmt das Vergnügen dann langsam schon wieder ab.
Re: QSort / Benchmark
Verfasst: Fr Mär 17, 2017 12:54 pm
von mfro
Die kürzeste (und wahrscheinlich beste) Version in Ada wär' wohl
Aber die willst Du wahrscheinlich nicht, oder?
Re: QSort / Benchmark
Verfasst: Fr Mär 17, 2017 1:20 pm
von Xin
Nein... ^^
Vielleicht die Implementierung davon...