Tips und Tricks zu Perl

Einfache Sortierungen

Recht häufig müssen Datenstrukturen sortiert werden. Dabei kann man viel Arbeit bzw. Laufzeit verschenken, aber auch gewinnen.

Prinzipiell am schnellsten dürfte die Verwendung des Perl-Befehls sort sein. Er erwartet als Input eine Liste und liefert eine sortierte Liste zurück; in der Standardform ist diese Liste allerdings nach ascii-Werten (in irgendeinem Buch habe ich mal den Ausdruck "asciibetisch" gelesen; ich finde ihn recht passend).

my @sortedList = sort @unsortedList;

Der sort-Befehl ruft in etwa 1:1 den sort-Befehl der C-Bibliothek (quicksort, bei neueren Perl-Versionen mergesort) auf. Deswegen ist seine Verwendung im Allgemeinen recht performant.

Mit sort kann man auch nach Zahlen oder eigenen Sortierkriterien sortieren, indem man als Parameter eine Vergleichsoperation mitgibt (oder ein Unterprogramm).

my @sortedList = sort { $a <=> $b } @unsortedList;

Beim sort kann man also eine Operation mitgeben, mit der man bestimmen kann, was als größer, kleiner oder gleich groß betrachtet werden soll. Die beiden Variablen $a und $b sind Variablen, die von der sort-Funktion schon vordeklariert sind, wobei $a für den ersten Wert steht, und $b für den zweiten. Der Operator <=> (Spaceship-Operator) vergleicht zwei Zahlen und liefert je nachdem -1, 0 oder +1 zurück (genauer gesagt: irgendwas kleiner als 0, 0 oder irgendwas größer als 0). Bei Zeichenkettenvergleichen arbeitet der Operator cmp identisch. Das erste Beispiel hätten wir auch folgendermaßen schreiben können:

my @sortedList = sort { $a cmp $b } @unsortedList;

Falls man das so macht, nimmt man jedoch eine etwas langsamere Abarbeitung in Kauf, weil zwischen dem Script und dem C-mergesort noch Perl-Bibliotheken stehen.

Wenn man irgendwas rückwärts sortieren will, vertauscht man einfach $a und $b:

my $revSortedList = sort { $b cmp $a } @unsortedList;

Eventuell ist aber folgender Ansatz schneller, weil auf Perl-Standardfunktionen zurückgegriffen werden kann:

my $revSortedList = reverse sort @unsortedList;

(BTW: man kann auch eine Zeichenkette umkehren, indem man schreibt:

my $rString = reverse $string;

Sowas ist um einigemale schneller als z.B.:

my $rString = join("", reverse ( split(//, $string) ) );

Will man z.B. bei der Sortierung von Zeichenketten nicht zwischen Groß- und Kleinschreibung unterscheiden, könnte man folgenden Ansatz wählen:

my @sortedList = sort { lc($a) cmp lc($b) } @unsortedList;

Erweiterte Sortieralgorithmen

Mit Perl muß man häufig auch komplexere Datenstrukturen sortieren. Man kann die Datenstrukturen entweder zerlegen und einen der oben erklärten Algorithmen verwenden. Perl bietet allerdings auch mächtigere Mittel an, wie z.B. die Schwartzian Transform:

my @list = ( [0, 3, 2, 4],
             [1, 3, 1, 5],
             [2, 9, 5, 2],
           ); # zweidimensionales Array => Sortierung nach Spalte 4
1: my @sortedList =               # von unten nach oben lesen
2:   map  { $_->[1]             } # werfe 0. Spalte weg und gebe Originalliste zurueck
3:   sort { $a->[0] <=> $b->[0] } # sortiere neue Listenreferenz nach 0. Spalte
4:   map  { [ $_->[3], $_ ]     } # mache 2dim-Listenreferenz daraus: [ $_[3], [...] ]
5:   @list;                       # nehme Liste

Beschreibung:

Zeilen 5 + 4: Mache aus der Liste eine zweidimensionale Liste, deren erste Dimension das Feld ist, nach dem sortiert werden soll (In unserem Fall also das Element mit dem Index 3) und die zweite Dimension ist eine Referenz auf die Zeile (z.B. [0,3,2,4]).

@tempList = ( [4, [0, 3, 2, 4] ],
              [5, [1, 3, 1, 5] ],
              [2, [2, 9, 5, 2] ],
            ); 

Zeile 3: Sortiere diese temporäre Liste nach 0. Index

@tempList = ( [2, [2, 9, 5, 2] ],
              [4, [0, 3, 2, 4] ],
              [5, [1, 3, 1, 5] ],
             ); 

Zeile 2: Gebe die Spalte mit dem Index 1 der nun sortierten Liste zurück

@sortedList = ( [2, 9, 5, 2],
                [0, 3, 2, 4],
                [1, 3, 1, 5],
              );

In diesem Beispiel macht die Schwartzian Transform nur wenig Sinn; eine Menge an Geschwindigkeit kann man damit unter Umständen erziehlen, wenn die Ermittlung der Vergleichskriterien sehr lange dauert.

Wenn man alle Dateien eines Verzeichnisses nach der Dateigröße sortieren will und nur die Dateinamen hat, muß man für die Sortierung zusätzlich noch die Dateigröße ermitteln. Dies kann man mit folgendem Konstrukt:

my $filesize = -s $file;

Wenn man nun jedoch eine Liste von Dateien (=@fileList) so sortieren will, könnte man folgenden Ansatz wählen:

my @sortedList = sort { -s $a <=> -s $b } @fileList;

Bei diesem Ansatz würde jedoch für jede Vergleichsoperation die Dateigröße ermittelt, also unnötig oft. Da hier auf Betriebssystemfunktionalität zugegriffen wird, braucht das Ermitteln der Dateigröße recht viel Zeit. Deshalb könnte man die Schwartzian Transform wählen, für jede Datei die Dateigröße nur einmal ermitteln. Das könnte folgendermaßen aussehen:

my @sortedList = map  { $_->[1]             } # zweites Element zurueckgeben
                 sort { $a->[0] <=> $b->[0] } # sortieren nach erstem Element
                 map  { [ -s $_, $_ ]       } # anonyme Listenreferenz: [groesse, dateiname]
                @fileList;

Oder man verwendet das Orc'sche Maneuvre, wo die Größe ebenso nur einmal ermittelt wird, und dann in einem Hash mit einem OR-Cache (deshalb der Name) für zukünftige Vergleiche gespeichert wird:

my %cache = ();
my @sortedList = sort {
  ( $cache{$a} ||= -s $a) <=> ($cache{$b} ||= -s $b)
} @fileList;

Durch geschickte Verwendung von ||= wird der Hash %cache als Zwischenspeicher verwendet, sodaß die Dateigröße nur einmal ermittelt werden muß und dann für die nächsten Vergleiche in %cache zwischengespeichert wird.

Ob man in solchen Fällen die Schwartzian Transform oder das Orc'sche Maneuvre bevorzugt, ist wohl meistens Geschmackssache.

Letztes Update dieser Seite: Tuesday, 27-Jun-2006 20:37:00 CEST