Artikel im Internet unter http://www.hidemail.de/blog/die-schwartzsche-transformation---arrays-sortieren-nach-mehreren-kriterien.shtml.
Mittwoch, 5.12.2007, 15:01:45 Uhr

Die Schwartzsche Transformation - Arrays sortieren nach mehreren Kriterien


Oftmals hat man das Problem, daß man Arrayinhalte sortieren will.

Hat man nur einzelne Werte, wie zum Beispiel Nachnamen, kann dies bequem per sort() erledigt werden.

Etwas komplizierter wird es, wenn man nach mehreren Kriterien sortieren möchte, zum Beispiel nach Nachnamen und Vornamen.
Hier kommt man mit sort() relativ schnell an die Grenzen bzw. der Code wird uneffektiv und verballert eine Menge Ressourcen.

Ein schlauer Mann namens Randall Schwartz hat sich für solche Problemstellungen eine Sortiermethode einfallen lassen, die solche Probleme schnell und effektiv löst: Die Schwartzsche Transformation.

Im Folgenden ist ein Beispiel, das aus einigen Datensätzen vorrangig nach dem Nachnamen, dann nach dem Vornamen sortiert.

@data=<DATA>;
print join("\n",sortieren(@data));

sub sortieren{

my @zeilen=@_;
my @sortiert = map { $_->[0] }
sort { $a->[1] cmp $b->[1] || $a->[2] cmp $b->[2] }
map { [$_,(split (/\; /,$_))[1,0]] } @zeilen ;

return @sortiert;

}

__DATA__
Peter; Bauer; Hohenufer 17; 31151
Hans; Meiser; Doffenweg 1; 30989
Urs; Müller; Schnellweg 8; 30166
Urs; Brüller; Ladenstrasse 4; 30166
Urs; Aamann; Münzgasse 56; 80782
Urs; Amann; Holzweg 17; 40555



So, wenn man das das erste Mal sieht versteht man im allgemeinen nur Bahnhof.

Das Kernstück ist natürlich die Funktion sortieren.
In

my @sortiert = map { $_->[0] }
sort { $a->[1] cmp $b->[1] || $a->[2] cmp $b->[2] }
map { [$_,(split (/\; /,$_))[1,0]] } @zeilen ;


findet das komplette Sortieren statt, allerdings in einer ziemlich kompakten Form. Wichtig ist dabei, daß man begreift, daß diese drei Zeilen eigentlich als eine Zeile gelesen werden müssen und daß die Abarbeitung von hinten nach vorne funktioniert.

Also fangen wir mal an, das zu zerlegen:
map { [$_,(split (/\; /,$_))[1,0]] } @zeilen ;
Aus dem Array @zeilen wird eine anonymes (perlinternes) Array erzeugt, das folgende Werte enthält:
$_ (die komplette aktuelle Zeile), (split (/\; /,$_))[1,0], was folgendes bedeutet: das Split teilt eine Zeile in ein Array, das alle einzelnen Daten enthält, also Vorname, Nachname, Straße und Postleitzahl. Davon hätten wir gerne den Inhalt der Elemente 1 und 0, also Nachname und Vorname. Diese beiden Werte werden dem anonymen Array zugewiesen.

Das map{} erzeugt also ein anonymes Array mit folgenden Inhalten: Aktuelle Zeile, Nachname, Vorname. Das war schon der Sinn der dritten zeile. Also weiter zur zweiten Zeile:

sort { $a->[1] cmp $b->[1] || $a->[2] cmp $b->[2] }
Zuerst muß man sich klar sein, daß als Parameter das anonyme Array aus Zeile drei verwendet wird. (Das Array, das aus den einzelnen aktuellen Zeilen, Nachnamen und Vornamen besteht).
Das sort sortiert jetzt alle einzelnen Werte, und zwar nach der Reihenfolge 1 und 2 ($a->[1] cmp $b->[1] || $a->[2] cmp $b->[2]), was ja wieder den Nachnamen und Vornamen darstellt. Das war schon die Funktion der zweiten Zeile.

Die erste Zeile macht jetzt nichts weiteres, als die sortierten Werte zu nehmen, und den Wert des 0ten Elements (die komplette Zeile) dem Array @sortiert zuzuweisen.

Alles klar... oder?

Vielleicht als weiteres Beispiel das Beispiel von oben, das aber diesmal nach Postleitzahl und Nachnamen sortiert:

@data=<DATA>;
print join("\n",sortieren(@data));

sub sortieren{

my @zeilen=@_;
my @sortiert = map { $_->[0] }
sort { $a->[1] cmp $b->[1] || $a->[2] cmp $b->[2] }
map { [$_,(split (/\; /,$_))[3,1]] } @zeilen ;

return @sortiert;

}

__DATA__
Peter; Bauer; Hohenufer 17; 31151
Hans; Meiser; Doffenweg 1; 30989
Urs; Müller; Schnellweg 8; 30166
Urs; Brüller; Ladenstrasse 4; 30166
Urs; Aamann; Münzgasse 56; 80782
Urs; Amann; Holzweg 17; 40555


Es werden in der dritten Zeile der Schwartzschen Transformation die Werte 3 und 1 extrahiert, die ja die Postleitzahl und den Nachnamen darstellen. Danach wird dann sortiert.

Zugegeben, man muß sich da erst etwas reindenken, aber wenn man es erst einmal kapiert hat, hat man eine sehr schnelle und ressourcensparende Möglichkeit, Listen zu sortieren.


Die Schwartzsche Transformation ist aber nicht auf den Vergleich verschiedener Kriterien beschränkt, auch bei einzelnen Werten ist sie oft wesentlich schneller als das herkömmliche sort.
Will man zum Beispiel nur nach den Nachnamen sortieren könnte man folgenden Code verwenden:

@data=<DATA>;
print join("\n",sortieren(@data));

sub sortieren{

my @zeilen=@_;
my @sortiert = map { $_->[0] }
sort { $a->[1] cmp $b->[1] }
map { [$_,(split (/\; /,$_))[1]] } @zeilen ;

return @sortiert;

}

__DATA__
Peter; Bauer; Hohenufer 17; 31151
Hans; Meiser; Doffenweg 1; 30989
Urs; Müller; Schnellweg 8; 30166
Urs; Brüller; Ladenstrasse 4; 30166
Urs; Aamann; Münzgasse 56; 80782
Urs; Amann; Holzweg 17; 40555






Links zur Schwartzschen Transformation
http://www.ostc.de/howtos/perl-sorting-HOWTO.txt
http://ad.informatik.uni-freiburg.de/bibliothek/tutorials/perl-g/perl_schw.html
http://de.wikipedia.org/wiki/Randal_L._Schwartz
http://www.perlunity.de/perl/forum/thread_015954.shtml

Artikel im Internet unter http://www.hidemail.de/blog/die-schwartzsche-transformation---arrays-sortieren-nach-mehreren-kriterien.shtml.