Schwartz'sche Transformation

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.

Sortieren

Beispiele:

#!/usr/local/bin/perl -w

@liste = ( 41, 37, 10, 30, 127, 512, 111 );

print "@liste\n\n";

@sort_1 = sort @liste;
print "1) @sort_1\n";

@sort_2 = sort { $a cmp $b } @liste;
print "2) @sort_2\n";

@sort_3 = sort { $a <=> $b } @liste;
print "3) @sort_3\n";

@sort_4 = sort { $b <=> $a } @liste;
print "4) @sort_4\n";

@sort_5 = sort { substr($a,1,1) <=> substr($b,1,1) } @liste;
print "5) @sort_5\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).

Effektive Sortierung

Als Beispiel soll nun eine Datei dienen, aus deren Zeilen jeweils ein Zahl extrahiert werden muß, die dann als Suchkriterium dient. Eine solche 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 solche Daten mit diesem Programm:

#!/usr/local/bin/perl -w

srand;

sub zufall {
    my $zeilen = shift;
    my $s;
    my @liste = ();

    for( $i=0; $i<$zeilen; $i++ ) {
        $s = '';
        for( $j=0; $j<rand(15); $j++ ) { $s .= chr(rand(26)+97) }
        $s .= '<'.int(rand(1000)).'>';
        for( $j=0; $j<rand(15); $j++ ) { $s .= chr(rand(26)+97) }
        push(@liste,$s);
    }
    return(@liste);
}

@liste = zufall(5);

Ein Ansatz zum Sortieren dieser Daten könnte so aussehen:

#!/usr/local/bin/perl -w

srand;
@liste = zufall(5);   # 'zufall()': siehe oben

sub by_number {
    my($x,$y);

    ($x) = ( $a =~ /<(\d+)>/ );
    ($y) = ( $b =~ /<(\d+)>/ );

    $x <=> $y;
}

@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

srand;
@liste = zufall(5);   # 'zufall()': siehe oben

foreach $elem (@liste) {
    push(@temp_1,[ $elem, ( $elem =~ /<(\d+)>/ )[0] ]);
}

@temp_2 = sort { $a->[1] <=> $b->[1] } @temp_1;

foreach $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.

Die Transformation

Damit reduziert sich das letzte Programmbeispiel auf diesen Code:

#!/usr/local/bin/perl -w

srand;
@liste = zufall(5);   # 'zufall()': siehe oben

@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.

Ein Geschwindigkeitsvergleich

#!/usr/local/bin/perl

use Benchmark;

$z = 1000;        # Länge der zu sortierenden Liste
$c = 10;          # Anzahl der Durchläufe

srand;
@liste = zufall($z);   # 'zufall()': siehe oben

### Einfache Sortierung

sub by_number {
    my($x,$y);

    ($x) = ( $a =~ /<(\d+)>/ );
    ($y) = ( $b =~ /<(\d+)>/ );

    $x <=> $y;
}

$t = timeit($c,
  '@sorted = sort by_number @liste'
);

print "1.) Einfache Sortierung:\n      ".timestr($t)."\n\n";

### Schwartz'sche Transformation

$t = timeit($c,
  '@sorted = map { $_->[0] } 
             sort { $a->[1] <=> $b->[1] } 
             map { [$_, ( /<(\d+)>/ )[0] ]} @liste'
);

print "2.) Schwartz'sche Transformation:\n      ".timestr($t)."\n\n";

print "($c Sortierungen von $z-elementigen Listen)\n";

1.) Einfache Sortierung:
      30 secs (29.40 usr  0.00 sys = 29.40 cpu)
2.) Schwartz'sche Transformation:
       6 secs ( 6.43 usr  0.00 sys =  6.43 cpu)

(10 Sortierungen von 1000-elementigen Listen)

Wie man sieht, benötigt die Schwartz'sche Transformation nur gut ein Fünftel der Rechenzeit im Vergleich zum einfachen "sort by_number".