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

Kommentare zum Beitrag "Die Schwartzsche Transformation - Arrays sortieren nach mehreren Kriterien"

Kommentar von Michael Arlt

Sehr guter Artikel!

Vielen Dank!!!

Kommentar von Smart

Hallo,

die Schwartzsche Transformation ist ja soweit bekannt und hier gut erklärt.

In Deinem praktischen Beispiel mit den Adressen kommen wir aber zu einem Problem bei der Sortiereung.
Wie würde eine Sortierung nach der Adresse aussehen?
Das Problem ist ja, dass die Straße alphanumerisch sortiert werden muss und die Hausnummer nummerisch ist.

Beispiel:
Hans; Albern; Lindenstrasse 2b; 12345
Hans; Albern; Lindenstrasse 8; 12345
Hans; Albern; Lindenstrasse 16; 12345

Dies würde nach der Strasse sortiert die 16 an 1. Stelle setzten.

Wer hat hierzu eine Lösung?

Gruß,
Smart

Kommentar von Tony

Seit gestern Abend, wo ich das erste mal von der Schwatzschen Transformation gehört habe, versuche ich meinen Kopf da herumzuwickeln. Bislang mit wenig Erfolg, aber dieser Artikel hat mich ein ganzes Stück weitergebracht.

Ich bin, sagen wir mal, fortgeschrittener Anfänger und will das ganze in JavaScript umsetzen (0 Plan von Pearl), aber eben nicht nur kopieren, sondern verstehen.

Thema: Perl Script Arrays Leistungsoptimiert

Der Beitrag "Die Schwartzsche Transformation - Arrays sortieren nach mehreren Kriterien" wurde 9514 mal gelesen.

Es wurde 8 x über diesen Beitrag abgestimmt.
Die durchschnittliche Beurteilung liegt bei
1.1 (1 = sehr gut - 6 = grottenschlecht).