Schwartz'sche Transformation
Einführung
Diese Seite behandelt ein äußerst elegantes Sortierverfahren:
die "Schwartz'sche Transformation" (nach
Randal L. Schwartz).
Obwohl zunächst recht aufwendig aussehend, offenbahrt
dieses Konstrukt ungeahnte Möglichkeiten, hat man es erst einmal
verstanden.
Im Grunde genommen handelt es sich nur um einen von vielen Wegen
Daten zu sortieren. Allerdings ist es was Flexibilität
und Effizienz angeht, wohl allen anderen Lösungen
überlegen.
Ein ähnliches Verfahren, das auf demselben Prinzip basiert,
ist unter der Bezeichnung "Decorate-Sort-Undecorate" (DSU) bekannt.
[Seitenanfang]
Sortieren
Zunächst ein paar Worte dazu, wie in Perl Daten sortiert
werden. Um den internen Algorithmus braucht man sich normalerweise
keine Gedanken machen. Für den Benutzer bzw. Programmierer
reduziert sich die Sortierung auf den Vergleich zweier
Datenelemente - ist nichts anderes angegeben, d.h., ruft
man einfach "sort @liste
" auf, so
erfolgt die Sortierung gemäß ASCII-Code in aufsteigender
Reihenfolge.
Durch Angabe einer eigenen Subroutine läßt
sich die Sortierung gezielt steuern. Die dort definierten Kommandos
werden während des Sortierens mehrfach aufgerufen, wobei jedesmal
zwei Elemente (dargestellt durch $a
und $b
)
miteinander verglichen werden. Ist der Rückgabewert gleich 1, so gilt
das erste Element ($a
) als "größer" im
Sinne der gewünschten Sortierung. Bei -1 geht Perl davon aus, daß
$b
"größer" ist, bei 0 wird "Gleichheit"
angenommen.
Beispiele:
#!/usr/local/bin/perl -w
use strict;
my @liste = ( 41, 37, 10, 30, 127, 512, 111 );
print "@liste\n\n";
my @sort_1 = sort @liste; print "1) @sort_1 (Standard)\n";
my @sort_2 = sort { $a cmp $b } @liste; print "2) @sort_2 (ASCII - aufsteigend)\n";
my @sort_3 = sort { $a <=> $b } @liste; print "3) @sort_3 (numerisch - aufsteigend)\n";
my @sort_4 = sort { $b <=> $a } @liste; print "4) @sort_4 (numerisch - absteigend)\n";
my @sort_5 = sort { substr($a,1,1) <=> substr($b,1,1) } @liste; print "5) @sort_5 (2.Ziffer - numer. - aufst.)\n";
|
|
41 37 10 30 127 512 111
1) 10 111 127 30 37 41 512 (Standard) 2) 10 111 127 30 37 41 512 (ASCII - aufsteigend) 3) 10 30 37 41 111 127 512 (numerisch - aufsteigend) 4) 512 127 111 41 37 30 10 (numerisch - absteigend) 5) 10 30 111 512 41 127 37 (2.Ziffer - numer. - aufst.)
|
|
Am letzten dieser Beispiele kann man schon ein Problem erkennen:
jedesmal, wenn zwei Daten miteinander verglichen werden, muß
die Funktion substr()
ausgeführt werden. Dies
kann bei großen Datensätzen dazu führen, daß
die meiste Rechenzeit in Operationen auf einzelne Elemente
verbraucht wird, denn jedes einzelne Datum wird i.a. während
der Sortierung mehr als einmal zu einem Vergleich herangezogen
(wer es genauer wissen will: bei n Daten im Mittel
nlogn-mal).
[Seitenanfang]
Effektive Sortierung
Eine Lösung des oben beschriebenen Problems besteht darin, in
einem ersten Schritt zunächst
für jedes Element des Datensatzes die entsprechende Operation
(hier: substr()
) durchzuführen, anschließend
eine Sortierung dieser temporären Daten vorzunehmen und
schließlich von diesen wieder zu den
ursprünglichen Daten zurückzukehren.
Als Beispiel soll nun eine Datei dienen, aus deren Zeilen jeweils
eine Zahl extrahiert werden muß, die dann als Suchkriterium dient.
Der Inhalt einer solchen Datei sähe beispielhaft etwa so aus:
oexkwch<37>jy yunq<100>zmwi ikbkwe<545>bcljvbry ojudnle<818>tgum gpmlxp<972>lud
|
Erzeugen kann man sich derartige Daten mit diesem Programm:
#!/usr/local/bin/perl -w
use strict;
srand;
sub zufall { my $zeilen = shift; my $s; my @liste = ();
for( my $i=0; $i<$zeilen; $i++ ) { $s = ''; for( my $j=0; $j<rand(15); $j++ ) { $s .= chr(rand(26)+97); } $s .= '<'.int(rand(1000)).'>'; for( my $j=0; $j<rand(15); $j++ ) { $s .= chr(rand(26)+97); } push(@liste,$s); } return(@liste); }
my @liste = zufall(5);
|
|
Ein Ansatz zum Sortieren dieser Daten könnte so aussehen:
#!/usr/local/bin/perl -w
use strict;
srand; my @liste = zufall(5); # 'sub zufall{...}': siehe oben
sub by_number { my($x,$y);
($x) = ( $a =~ /<(\d+)>/ ); ($y) = ( $b =~ /<(\d+)>/ );
$x <=> $y; }
my @ergebnis = sort by_number @liste;
|
|
Dabei wird allerdings viel Rechenzeit durch die vielfache Auswertung der
regulären Ausdrücke in by_number
verbraucht.
Schneller geht es, wenn man aus jedem Datum ein zweielementiges
(anonymes) Array konstruiert, dessen eines Element das Datum selbst und das
andere das Ergebnis des regulären Ausdruckes (hier: die Zahl)
ist.
#!/usr/local/bin/perl -w
use strict;
srand; my @liste = zufall(5); # 'sub zufall{...}': siehe oben
my @temp_1 = ();
foreach my $elem (@liste) { push(@temp_1,[ $elem, ( $elem =~ /<(\d+)>/ )[0] ]); }
my @temp_2 = sort { $a->[1] <=> $b->[1] } @temp_1;
my @ergebnis = ();
foreach my $t (@temp_2) { push(@ergebnis, $t->[0]); }
|
|
Im obigen Skript wird in der ersten foreach
-Schleife ein
Array namens @temp_1
aufgebaut, dessen Elemente
jeweils Referenzen auf zweielementige anonyme Arrays sind. Diese
zweielementigen Arrays enthalten unter dem Index 0 die ursprüngliche
Zeile und unter dem Index 1 die extrahierte Zahl.
Beim sort
sind nun die beiden zu vergleichenden Elemente
in den Variablen $a
und $b
die Referenzen
aus dem Array @temp_1
. Auf die für die Sortierung
benutzte Zahl (unter dem Index 1) wird dann durch $a->[1]
bzw. $b->[1]
zugegriffen. <=>
sorgt dann wie gewohnt für die (numerische) Sortierung der
beiden Zahlen.
Danach befindet sich in @temp_2
wiederum eine Liste
aus Referenzen auf zweielementige anonyme Arrays, allerdings nun
nach den jeweiligen Zahlen sortiert.
In der abschließenden foreach
-Schleife
wird nun aus @temp_2
jeweils das erste Element
dereferenziert und in das Array @ergebnis
gepackt.
Dieses Array enthält dann die ursprünglichen Datenzeilen,
nun aber gemäß der enthaltenen Zahlen sortiert.
[Seitenanfang]
Die Funktion map()
Mit Hilfe von map()
kann man auf einfache Art und Weise
eine Operation auf alle Elemente einer Liste anwenden. map()
erwartet entweder einen Ausdruck oder einen Programmblock, der dann
nacheinander für jedes Arrayelement, auf das über $_
zugegriffen wird, aufgerufen wird.
Beispiel:
#!/usr/local/bin/perl -w
use strict;
my @liste = ( 1, 2, 3 );
@liste = map { $_ * $_ } @liste; print join(",",@liste),"\n";
@liste = map sqrt($_), @liste; print join(",",@liste),"\n";
|
|
Zunächst wird jedes Element mit sich selbst multipliziert und
die Ergebnisliste wieder in @liste
gespeichert.
Anschließend wird mit Hilfe der Funktion sqrt()
jeweils die Quadratwurzel gezogen, wodurch sich wieder die
ursprünglichen Werte ergeben.
[Seitenanfang]
Die Transformation
Die Schwartz'sche Transformation nutzt die Möglichkeiten der
map
-Funktion aus, um die ganze Sortierung in
einer Befehlszeile unterzubringen und ohne explizit
temporäre Arrays zu verwenden.
Damit reduziert sich das letzte Sortierbeispiel auf diesen Code:
#!/usr/local/bin/perl -w
use strict;
srand; my @liste = zufall(5); # 'sub zufall{...}': siehe oben
my @ergebnis = map { $_->[0] } sort { $a->[1] <=> $b->[1] } map { [ $_, ( /<(\d+)>/ )[0] ] } @liste;
|
|
Man beachte dabei, daß die letzten drei Zeilen des Skriptes
nur ein Perl-Kommando darstellen,
das sozusagen von hinten
gelesen werden muß: zuerst wird aus @liste
ein
Array aus Referenzen auf zweielementige Arrays erstellt. Dieses
Array ist dann das Argument von sort
und aus dessen
Rückgabewert wiederum wird das jeweils erste Element (mit dem
Index 0) extrahiert. Das dabei entstehende Array wird schließlich
@ergebnis
zugewiesen.
[Seitenanfang]
Geschwindigkeitsvergleich
Wie schon weiter oben erwähnt war das Hauptziel der Schwartz'schen
Transformation eine Steigerung der Effizienz. Dies läßt sich
mit Hilfe des Benchmark-Moduls, das der Perl-Distribution
beiliegt, recht einfach überprüfen.
#!/usr/local/bin/perl -w
use strict; use Benchmark;
my $z = 1000; # Länge der zu sortierenden Liste my $c = 50; # Anzahl der Durchläufe
srand; my @liste = zufall($z); # 'sub zufall{...}': siehe oben
### Einfache Sortierung
sub by_number { my($x,$y);
($x) = ( $a =~ /<(\d+)>/ ); ($y) = ( $b =~ /<(\d+)>/ );
$x <=> $y; }
timethese($c, { "Einfache Sortierung" => sub { my @sorted = sort by_number @liste } });
### Schwartz'sche Transformation
timethese($c, { "Schwartz'sche Trafo" => sub { my @sorted = map { $_->[0] } sort { $a->[1] <=> $b->[1] } map { [$_, ( /<(\d+)>/ )[0] ]} @liste } });
print "($c Sortierungen von $z-elementigen Listen)\n";
|
|
Benchmark: timing 50 iterations of Einfache Sortierung... Einfache Sortierung: 15 wallclock secs (14.07 usr + 0.04 sys = 14.11 CPU) @ 3.54/s (n=50) Benchmark: timing 50 iterations of Schwartz'sche Trafo... Schwartz'sche Trafo: 3 wallclock secs ( 3.07 usr + 0.04 sys = 3.11 CPU) @ 16.08/s (n=50) (50 Sortierungen von 1000-elementigen Listen)
|
|
Wie man sieht, benötigt die Schwartz'sche Transformation in diesem
Falle nur etwa
ein Fünftel der Rechenzeit im Vergleich zum einfachen
"sort by_number
".
[Seitenanfang]