Montag, Dezember 24, 2007

Algorithmen - Teil 1: Quicksort

Neulich hab ich versucht, den Unterschied zwischen funktionalen und imperativen Programmiersprachen zu erklären und dabei festgestellt, dass man das am besten anhand von Beispielcode machen kann. Darum habe ich angefangen Quicksort in drei Programmiersprachen (C, Python, Haskell) zu implementieren. Da Perl und Ruby populäre Sprachen sind, die mich schon länger interessieren, sind die heute auch gleich dazugekommen - eine willkommene Gelegenheit für mich, diese beiden Sprachen näher kennenzulernen und gleichzeitig die Unterschiede und Gemeinsamkeiten der einzelnen Sprachen aufzuzeigen.

Bevor's losgeht noch ein paar kurze Bemerkungen:
Die Aufgabe ist mit Hilfe von Quicksort ein Integer-Array aufsteigend zu sortieren. Dabei habe ich nur in C eine In-Place Sortierung implementiert.
Als Pivot-Element wird das erste Element gewählt und mit 'p' bezeichnet. 'a' bezeichnet das Array und 'l' und 'r' stehen für den "linken" (kleineren) sowie den "rechten" (größeren) Teil des Arrays.
Die gezählten verwendeten Codezeilen beziehen sich nur auf die Funktion selber - zusätzliche Zeilen, die zur Ausführung benötigt werden (main()-Funktion, etc.) werden nicht gezählt.
Also, los gehts:

C

  • LOC: 16
  • Bemerkungen: In-Place Sortierung, längste Implementierung

#include <stdio.h>
void qsort(int a[], int len) {
if (len == 0) return;
int p = a[0];
int l = 0;
int r = len-1;
while (l < r) {
if (a[l] > a[r]) {
int tmp = a[l];
a[l] = a[r];
a[r] = tmp;
}
(a[l] == p) ? r-- : l++;
}
qsort(a, l);
qsort(&a[l+1], len-l-1);
}

int main(int argc, char** argv) {
int i = 0;
int test[10] = {6, 4, 9, 1, 2, 5, 3, 8, 7, 0};
qsort(test, 10);
printf("[");
for (i = 0; i < 9; i++) {
printf("%d, ", test[i]);
}
printf("%d]\n", test[9]);
}


Python

  • LOC: 9
  • Bemerkungen: Verständlicher Ternary-Operator

def qsort(a):
if (a == []):
return []
p = a.pop()
l = []
r = []
for e in a:
l.append(e) if (e < p) else r.append(e)
return qsort(l) + [p] + qsort(r)


Haskell

  • LOC: 3
  • Bemerkungen: Kürzeste Implementierung

qsort :: Ord a => [a] -> [a]
qsort [] = []
qsort (p:xs) = qsort([l | l <- xs, l < p]) \\
++ [p] ++ qsort([r | r <- xs, r > p])

(letzte Zeile zur Lesbarkeit umgebrochen)

Perl

  • LOC: 11
  • Bemerkungen: Abgefahrenste Syntax

#!/usr/bin/env perl
sub qsort {
my @l = ();
my @r = ();
my @a = @_;
return () if (@a == 0);
my $p = shift @a;
foreach (@a) {
($_ < $p) ? (@l[++$#l] = $_) : (@r[++$#r] = $_);
}
return (qsort(@l), $p, qsort(@r));
}

print qsort(1, 4, 3, 5, 2, 9, 8, 0, 6, 7);
print "\n"


Ruby

  • LOC: 13
  • Bemerkungen: Python nicht unähnlich

#!/usr/bin/env ruby
def qsort(a)
if !a.empty?
p = a.shift
l = Array.new
r = Array.new
a.each do |e|
e < p ? l.push(e) : r.push(e)
end
(qsort(l) << p) + qsort(r)
else
Array.new
end
end

puts qsort([4, 1, 6, 3, 8, 7, 2, 5, 9, 0])

Die Python- und Haskell-Module habe ich im jeweiligen Interpreter (Hugs bzw. die Python-Konsole) geladen.
Bemerkenswert: C hat die längste Implementierung, ist aber dafür In-Place. Haskell schießt dafür am entgegengesetzten Ende den Vogel ab, mit nur drei Zeilen (von denen die erste noch nicht einmal dringend nötig ist). Und das Perl-Statement
($_ < $p) ? (@l[++$#l] = $_) : (@r[++$#r] = $_);
finde ich dermaßen abgefahren, dass ich mir überlege das auszudrucken und an die Wand zu hängen. Ich habe selten dermaßen viele Sonderzeichen in einer Codezeile gesehen!
Wenn ich Zeit habe, werd ich auch noch Java-Code schreiben. Ansonsten überleg ich mir, was der nächste Algorithmus wird. Dijkstra vielleicht...

Kommentare:

Thomas hat gesagt…

Hab das Rubybeispiel mal kurz überarbeitet und ein wenig syntax-sugar genutzt und gleichzeitig auf Golftechniken verzichtet. Bin kein Fanboy, aber nur drei Zeilen weniger code als in der C Implementation konnte ich dann doch nicht stehen lassen ;)

Mfg, Thomas

def qsort(a)
return Array.new if a.empty?
pivot = a.shift
left,right = Array.new, Array.new
a.each { |ele| ele < pivot ? left.push(ele) : right.push(ele) }
return qsort(left).push( pivot ) + qsort(right)
end

p qsort([-5,3,6,123,6,4,5,6,8,0]) # => [-5, 0, 3, 4, 5, 6, 6, 6, 8, 123]

balanceofcowards hat gesagt…

Zugegeben - in Ruby bin ich leider (noch) nicht recht firm und das mit dem "if" ist bei dir tatsächlich eleganter. Was meinst du mit "Golftechniken"?

Mehrfachzuweisungen wie bei dir in Zeile 4 (left,right = Array.new, Array.new) hab ich absichtlich unterlassen. In Python kann ich das ja äquivalent machen:
(l, r) = ([], [])

Aber dann kann ich andererseits auch den ganzen C Code in eine einzige Zeile quetschen.

Fazit: LOC sagen nur das, was man selber reininterpretieren will :)
Abgesehen davon sind diese Beispiele sowieso eigentlich zu kurz um echte Aussagekraft zu haben.

Ernsthaft - ich will hier keine Programmiersprache schlecht reden. Ich hätt hier ja auch noch die Performance messen können... aber ich halt mich lieber an das Credo des Debian-Programmiersprachenvergleichs:
Man möge versuchen, die Parameter so zu wählen, dass der eigene Favorit am besten da steht :)

Thomas hat gesagt…

Programmiergolf: Mit möglichst wenig Zeilen zum Ziel kommen. Die Doppelzuweisung fällt wohl doch drunter, erwischt :)

es ging mir eher darum ein paar kleine kniffe zu zeigen, denn die sind es die Ruby so schön machen, z.B. den If modifikator in der 2. Zeile. Ein anderes Beispiel wäre die Unterstützung zweier Rückgabewerte:

left,right = a.partition{|e| e < pivot}

Was den Rest angeht hast du natürlich recht. Aber ich will eh nur ein bisschen Lust machen sich mal näher mit Ruby zu befassen - es lohnt sich :=)

Thomas hat gesagt…

Was ich ganz vergessen hatte: Bitte schreib die Serie weiter, der erste Teil war sehr aufschlussreich.

balanceofcowards hat gesagt…

Hab leider momentan wenig Zeit.
Ich hoffe, dass ich mich im April wieder vermehrt um das Blog kümmern kann.