/blog/perl


substr() in Perl
[127001 mal gelesen]
foreach in Perl
[116149 mal gelesen]
Arrays in Perl - Besonderheiten
[109128 mal gelesen]
open() - Dateien öffnen in Perl
[97739 mal gelesen]
split() in Perl - Zeichenketten teilen
[88645 mal gelesen]
chomp() in Perl
[84410 mal gelesen]
grep - Listen durchsuchen in Perl
[81727 mal gelesen]
push in Perl
[78538 mal gelesen]
sleep in Perl - Das aktuelle Script warten lassen
[61110 mal gelesen]
print in Perl
[49723 mal gelesen]


Arrays
Dateien
HTPC
Hashes
Leistungsoptimiert
PHP
Perl
RegEx
Schleifen
Script
Skalare
Sonstiges
System
Webserver
Zur Startseite


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



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 7327 mal gelesen.

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

Kommentar schreiben  Druckansicht  Seitenanfang 
Beurteilen 






 Zufällige Beiträge im /blog/perl

Mathematische Funktionen in Perl - atan2(), cos(), exp(), sin(), log(), sqrt()

Gruppenbildung in Perl

Wie vermeide ich Fehler in Perl - strict

Doppelte Elemente aus Array entfernen - Und die Reihenfolge beibehalten!

Kuriose Reguläre Ausdrücke

Doppelte Einträge aus Array entfernen in Perl

Uhrzeit und Datum bestimmen in Perl

Transform a website to unicode

close - Datei schließen in Perl

Ein PHPBB-Foum auf einen anderen Server umziehen



0.0323460102081299 sec. to build



...Blogsoftware in pure Perl - Powered by a lot of Coffee...


SSD-Festplatte - Wassn das???
Die Transliteration - Nur ein Zeichen in einem Skalar ersetzen
Select - Case in Perl
Windows 7 XP Mode – Wo finde ich den XP-Modus unter Windows 7?
Mac-Adresse beim Apple Macintosh herausfinden
SGN-Funktion für Perl
truncate - Dateigröße verändern in Perl
Eigene IP herausfinden mit Perl
Epoche live in Datum umwandeln
Firefox 3 - Exe-Files downloaden


Von: Fabian
Kommentar:
Hallo zusammen,
ich suche schon etwas im Internet und bin bisher nicht fündig geworden.
Zum Beitrag


Von: Schorschel eastcoast
Kommentar:
Danke. Das hat mir weitergeholfen.
Zum Beitrag


Von: Jessica
Kommentar:
Kann man auch zwei Datein parallel einlesen?

Zum Beitrag


Von: Xtravaganz
Kommentar:
Für

Zum Beitrag


Von: Xtravaganz
Kommentar:
Für

Zum Beitrag



Gesamtverzeichnis
Februar 2010
Dezember 2009
Oktober 2009
Januar 2009
Dezember 2008
November 2008
September 2008
August 2008
Juli 2008
Juni 2008
Mai 2008
April 2008
Januar 2008
Dezember 2007
November 2007
Oktober 2007
September 2007
August 2007
Juni 2007
Mai 2007
April 2007
März 2007
Februar 2007
Januar 2007
Dezember 2006


Mister Wong

RSS-Feed

Heute ist der
22.7.2018

Es ist
8:38:29 Uhr

Ihre IP:
54.198.77.35

Blog-Einträge: 186

Die letzten 24 Stunden im Überblick


Gelesene Beiträge insgesamt:
3687058


Webseiten vergleichen
Kalender mit Feiertagen - 2028
Links finden und testen
Menschliche Datumsangaben
IP zu Domain herausfinden
Time live in Datum umwandeln
Perl für Windows



Mo Di Mi Do Fr Sa So
1
2345678
9101112131415
16171819202122
23242526272829
3031

Impressum