Die besten Lesereinsendungen des Programmierwettbewerbs

Das Echo auf den Sprachvergleich aus Linux-Magazin 10/2008 [1] kann sich sehen lassen: Über 60 Programme in 13 Sprachen gingen in der Redaktion ein. Die Zahlen sind zwar nicht repräsentativ, geben aber dennoch einen Hinweis auf die Beliebtheit der Sprachen. Die populären Skriptsprachen Python und Perl sind auch im Testfeld am häufigsten vertreten (16 und 15 Einsendungen). Danach folgen neun Vorschläge in C++ und sieben in Ruby. Einige C++-Lösungen nutzten den Parser-Generator Flex zum Erzeugen des eigentlichen Quellcodes.

Gleichviele Beiträge gingen in Awk und Java ein (je vier) - weiter können Sprachkonzepte kaum auseinanderliegen. Ebenfalls in der Schlussgruppe finden sich C, C# und Pascal unter den klassischen Compilersprachen, Tcl als versprengter Vertreter der Skriptsprachen und schließlich noch Groovy, Haskell und Ocaml als Exemplare eher experimenteller und exotischer Sprachen. Gerade letztere verbuchte jedoch einen faustdicken Überraschungserfolg, denn die Ocaml-Lösung landete auf dem ersten Platz bei der Laufzeitmessung.

Aufgrund der großen Anzahl von Vorschlägen präsentiert dieser Artikel nur eine Auswahl, die die Redaktion nach Laufzeit, Kompaktheit des Codes und stilistischen Merkmalen getroffen hat.

Abbildung 1: Sechzehn Finalisten haben die Sortieraufgabe auf sehr unterschiedliche Weise implementiert. Das Diagramm nennt die verwendete Sprache und zeigt die Laufzeit der jeweiligen Lösung in Sekunden sowie die Anzahl an Programmzeilen. Zu sortieren war eine 55 MByte große Datei mit rund einer Million Fußnoten.

Testumgebung

Die eingesendeten Lösungen inklusive einer kleinen Testumgebung, die alle Programme gegebenenfalls übersetzt und startet, stehen auf dem FTP-Server des Linux-Magazins zum Download bereit [2]. Bevor sie die diversen Programme in das Makefile für den Performancetest integrierte, untersuchte die Redaktion jedes Programm auf Funktionstüchtigkeit. Dazu ein kurzer Test-Input mit 8 MByte. Praktischerweise hatte Linux-Magazin-Leser Sebastian Mach einen Testgenerator geschrieben, der sich hierzu bestens eignete. Dieses Tool ist ebenfalls auf dem FTP-Server zu finden.

Um die Einsendungen zum Laufen zu bringen, musste die Redaktion gelegentlich minimale Änderungen vornehmen, etwa wenn ein Programm stur eine bestimmte Eingabedatei verwendete oder im Fußnoten-Trenner »@footnote:« ein Plural-S erwartete.

Wettkampfbedingungen

In der Endrunde musste jeder Vorschlag exakt den gleichen Input verarbeiten wie die Lösungen der Sprachgurus: Die Textdatei »sample5.txt« enthält rund eine Million Fußnoten in einer Datei von 55 MByte. Einige Einsender haben clevere Optimierungen vorgeschlagen und mitunter unterschiedliche Varianten der Sortierung implementiert.

Im Labor kamen jeweils die Voreinstellungen zum Einsatz. Eine Übersicht der 16 Finalisten zeigt Abbildung 1. Die Zeitachse (linker Balken) stellt die reale Laufzeit dar. Fast alle Lösungen benötigten rund 95 Prozent ihrer CPU-Zeit im Userland, um die Datenstrukturen zu verarbeiten, einzig die Varianten "Lukas" in C# und "Pascal" in C++ wichen von diesem Muster ab. Sie nutzen im Verhältnis mehr Kernelfunktionen.

Alle Programme erhielten praktisch einen eigenen Core für ihre Aufgabe auf einer Intel-L2400-CPU, die mit 1,66 GHz getaktet war und über 3,2 GByte Hauptspeicher verfügte. Der langsamste Vertreter beim letzten Test hatte rund 50 Sekunden für die Aufgabe benötigt, daher standen den Einsendungen zwei Minuten CPU-Zeit mittels »ulimit -t 120« zu. Nach 120 Sekunden brach der Kernel jedes Skript automatisch ab.

Die Länge des Programms - der zweite Balken in Abbildung 1 - maß das Makefile kurzerhand per »wc -l« und bezog dazu alle Code- und Header-Dateien inklusive aller Kommentare und Leerzeilen ein, schloss jedoch Hilfsdateien wie Makefiles oder Projektdefinitionen aus. Dieser Wert eignet sich somit nur bedingt für eine Wertung. Die folgenden manuellen Untersuchungen beziehen sich hingegen auf die reale Code-Menge.

Die Programme tragen den Vornamen ihrer Autoren, im Text ist jeweils eine Referenznummer angegeben, mit der sich die Lösungen auf dem FTP-Server lokalisieren lassen.

01 #!/usr/bin/perl
02 use strict;
03 
04 open(IN, @ARGV[0]) or
05   die "Cannot open file '@ARGV[0]': $!n";
06 undef $/; my $file = <IN>;
07 $file =~ /@footnote/g or
08   die 'Missing marker "@footnote".', "n";
10 (my $notecount, my @indexmap) = (0, ());
11 $indexmap[$1] = ++$notecount
12   while ($file =~ /[(d+)]/g);
13 
14 (pos($file), my $from) = (0, 0);
15 while ($file =~ /[(d+)]/g) {
16     print substr($file, $from, pos($file) - $from -        2 - length($1)) . '[' . $indexmap[$1] . ']';
17     $from = pos($file);
18 }
19 
20 print substr($file, $from);

01 #!/usr/bin/perl
02 
03 while ( <> ) {
04   $fn = 1 if /^@footnote:/;
05   if ( $fn ) {
06     (s/^[(d+)] (.*)//) &amp;&amp;
07     ($footer->{ $fn_hash->{ $1 } } =
08     sprintf "%s", $2) || print;
09   } else {
10     while ( s/^(.*?)[(d+)]//x ) {
11       printf "%s[%s]", $1, $fn_hash->{ $2 }
12         ||= ++$index;
13       }
14       print;
15    }
16 }
17 
18 foreach ( sort keys %$footer ) {
19    printf "[%s] %sn", $_, $footer->{ $_ };
20 }

01 #!/usr/bin/perl
02 while (my $line = <>) {
03   if($w) {
04     $line =~ /^[(d+)]s+(.*)$/;
05     $footnote[$index{$1}] = $2;
06   } else {
07     $w = 1 if $line =~ /^@footnotes/;
08     @hits = $line =~ /[(d+)]/g;
09     foreach my $hit (@hits) {
10       if (not defined $index{$hit}) {
11         $index{$hit} = ++$i };
12       $line =~ s/[$hit]/[$index{$hit}]/g;
13     }
14     print $line;
15   }
16 }
17 for my $i (1..$#footnote+1) {
18   printf("[%d] %sn", $i, $footnote[$i] ?
19          $footnote[$i] : 'not defined')
20          if defined($footnote[$i]) or
21             defined($index{$i})
22 }