QSort / Benchmark

Pascal, Basic und andere nicht aufgelistete
Antworten
Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8499
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

QSort / Benchmark

Beitrag von Xin » Mi Mär 08, 2017 11:21 am

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.
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.

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8499
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: QSort / Benchmark

Beitrag von Xin » Mi Mär 08, 2017 11:23 am

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.

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8499
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: QSort / Benchmark

Beitrag von Xin » Di Mär 14, 2017 9:24 pm

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? :D
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.

mfro
Beiträge: 311
Registriert: Mi Jan 16, 2013 4:58 pm

Re: QSort / Benchmark

Beitrag von mfro » Do Mär 16, 2017 10:06 pm

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;
It's as simple as that. And remember, Beethoven wrote his first symphony in C.

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8499
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: QSort / Benchmark

Beitrag von Xin » Fr Mär 17, 2017 11:51 am

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.
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.

mfro
Beiträge: 311
Registriert: Mi Jan 16, 2013 4:58 pm

Re: QSort / Benchmark

Beitrag von mfro » Fr Mär 17, 2017 12:54 pm

Die kürzeste (und wahrscheinlich beste) Version in Ada wär' wohl

Code: Alles auswählen

Ada.Containers.Generic_Array_Sort (arr);
Aber die willst Du wahrscheinlich nicht, oder? ;)
It's as simple as that. And remember, Beethoven wrote his first symphony in C.

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8499
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: QSort / Benchmark

Beitrag von Xin » Fr Mär 17, 2017 1:20 pm

Nein... ^^

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.

Antworten