Schwartz'sche Transformation

[ vorherige Seite ] [ Titelseite ] [ Inhalt ] [ Index ] [ nächste Seite ]

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";
1,4,9
1,2,3

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]

[ vorherige Seite ] [ Titelseite ] [ Inhalt ] [ Index ] [ nächste Seite ]
Autor: Eike Grote Version: 2.07 (27.10.2019)