QSort / Benchmark

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

[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;
  }

[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?

[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;

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

[mfro]

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?

[Xin]

Nein... ^^

Vielleicht die Implementierung davon...