HOWTO zur Sortierung in Perl (C) 2006 T.Birnthaler/H.Gottschalk OSTC GmbH, http://www.ostc.de Version 1.13 (20.03.2012) Dieses Dokument beschreibt, wie in Perl das Sortieren von Arrays und Hashes durchgeführt wird. ________________________________________________________________________________ Inhaltsverzeichnis 1) Array sortieren 2) Array absteigend und numerisch sortieren 3) Hash(-Schlüssel) sortieren 4) Hierarchisch sortieren 4.1) Array hierarchisch sortieren 4.2) Hierarchisch sortieren bgzl. mehrerer getrennter Kriterien 5) Schwartzsche Transformation 5.1) Beispiele zu Schwartzscher Transformation ________________________________________________________________________________ 1) Array sortieren ------------------ Die Perl-Funktion "sort" sortiert Arrays standardmäßig "alphabetisch aufsteigend" ("lexikografisch", etwa wie im Telefonbuch oder in einem Lexikon), indem sie die Ordnungsreihenfolge von jeweils 2 Elementen des Arrays mit Hilfe der String-Vergleichsoperation "cmp" (compare) ermittelt: @sorted = sort @array; Die Standard-Vergleichsfunktion "cmp" kann auch explizit als "anonyme Funktion" direkt nach "sort" angegeben werden, folgender Aufruf ist also völlig identisch zu obigem: @sorted = sort { $a cmp $b } @array; Alternativ kann die Sortierfunktion explizit definiert und ihr Name beim "sort"- Aufruf mitgegeben werden. Folgender Aufruf ist also wiederum völlig identisch: sub cmp_func { $a cmp $b } @sorted = sort cmp_func @array; 1.1) Wie arbeitet "sort" ------------------------ Die zwei von Perl fest per Name "$a" und "$b" verwendeten Variablen zeigen dabei automatisch auf die 2 Elemente des Arrays, die gerade miteinander verglichen werden sollen. Eigentlich sind es aus Performancegründen ALIASE für die Arraylemente (also weitere Namen). Eine Zuweisung an "$a" oder "$b" ändert also das entsprechende Element im Array --- keine gute Idee!). Die Funktion "sort" ruft auf geschickte Art und Weise (Quicksort-Verfahren) solange die Vergleichsfunktion mit je 2 Array-Elementen auf, bis ALLE Elemente gemäß der Vergleichsfunktion sortiert sind. Die Vergleichsfunktion muss folgende Werte für die 2 Element-Aliase "$a" und "$b" zurückliefern: 1 falls "$a" größer "$b" 0 falls "$a" gleich "$b" -1 falls "$a" kleiner "$b" Will man zusehen, welche Elemente die Perl-Funktion "sort" in welcher Reihenfolge vergleicht, kann man eine "print"-Anweisung in die Sortierfunktion einbauen. Man sieht dann pro Aufruf der Sortierfunktion durch "sort" die beiden gerade miteinander verglichenen Elemente (man sieht auch, dass viele Elemente mehrfach an die Sortierfunktion übergeben werden). sub cmp_func { print "cmp_func: '$a' cmp '$b' -> ", ($a cmp $b), "\n"; $a cmp $b; } 2) Array absteigend und numerisch sortieren ------------------------------------------- Standardmäßig sortiert "sort" wie gesagt aufsteigend alphabetisch. Vertauscht man "$a" und "$b", so wird "umgekehrt" (d.h. normalerweise "alphabetisch absteigend") sortiert, d.h. man spart den Aufruf der Funktion "reverse" ein. @rev_sorted = sort { $b cmp $a } @array; # Umgekehrt sortieren @rev_sorted = reverse sort { $a cmp $b } @array; # Analog (langsamer?) Durch Austausch der Element-Vergleichfunktion "cmp" gegen "<=>" kann auch "numerisch aufsteigend" (oder "absteigend") sortiert werden: @sorted = sort { $a <=> $b } @array; # Numerisch aufsteigend @rev_sorted = sort { $b <=> $a } @array; # Numerisch absteigend 3) Hash(-Schlüssel) sortieren ------------------------------ Auch die Sortierung von Hash-Schlüsseln nach ihrem zugehörigen Hash-Wert ist möglich, um auf die Hash-Elemente in einer nach den Werten sortierten Reihenfolge zugreifen zu können: %hash = ("tom" => 17, "hans" => 35, "rick" => 5, "helmut" => 99); # Schlüssel numerisch sortieren @keys_sorted_by_value = sort { $hash{$a} <=> $hash{$b} } keys %hash; # Schlüssel alphabetisch sortieren @keys_sorted_by_value = sort { $hash{$a} cmp $hash{$b} } keys %hash; foreach (@keys_sorted_by_value) { print "$_ hat Wert $hash{$_}\n"; } Der Trick ist hier, die Vergleichsfunktion für 2 Schlüssel auf Basis der ihnen zugeordneten Werte zu definieren. D.h. bei jedem Vergleich zweier Schlüssel wird auf die Ihnen zugeordneten Werte zugegriffen. Also werden die Schlüssel gemäß den ihnen zugeordneten Werten sortiert. 4) Hierarchisch sortieren ------------------------- Sogar nach mehreren Kriterien kann "hierarchisch" sortiert werden (hier erst ohne Beachtung der GROSS/Kleinschreibung, wenn die Elemente dabei gleich sind, dann mit Beachtung der GROSS/Kleinschreibung): @sorted = sort { uc($a) cmp uc($b) or $a cmp $b } @array; # uc=uppercase @sorted = sort { "\L$a" cmp "\L$b") or $a cmp $b } @array; # \L=lowercase Liefert ein Kriterium keinen Unterschied (Ergebnis "0"), dann wird aufgrund der "or"-Verknüpfung nach dem nächsten Kriterium sortiert. Liefert ein Kriterium einen Unterschied, dann bricht die Auswertung aufgrund der "Shortcut/Short circuit"-Eigenschaft der Auswertung von Booleschen Ausdrücken an dieser Stelle mit dem Ergebnis dieses Vergleichs ("1" oder "-1") ab. Ergibt keines der Sortierkriterien einen Unterschied, dann wird "0" zurückgeliefert (d.h. die Werte sind nicht unterscheidbar und damit "gleich"). Man sollte in einer Vergleichsfunktion im letzten Vergleichs-Schritt immer die Elemente direkt vergleichen, damit eine "eindeutige" ("stabile") Sortierung entsteht, die bei wiederholter Sortierung reproduziert wird: sub cmp_2_levels { $alter{$a} <=> $alter{$b} or $a cmp $b; } sort cmp_2_levels keys %alter; 4.1) Array hierarchisch sortieren --------------------------------- Folgendes Array enthält drei Werte pro Element (Zahl + Großbuchstabe + Zeichen), die Sortierreihenfolge wird primär vom 1. Wert bestimmt. Bei gleichem 1. Wert vom 2. Wert. Und bei gleichem 1.+2. Wert vom 3. Wert (Trennzeichen der Werte ist "_"): @arr = qw/ 1_D_100 20_A_200 3_B_8 20_A_-3 20_A_33 -5_B_49 1000_C_-40 /; Zum Sortieren wird eine mehrstufige Sortierfunktion definiert: @sorted = { # print "VERGLEICH: $a <=> $b", ($a[0] <=> $b[0] or # $a[1] cmp $b[1] or # $a[2] <=> $b[2]), "\n"; my @a = split(/_/, $a); my @b = split(/_/, $b); $a[0] <=> $b[0] or $a[1] cmp $b[1] or $a[2] <=> $b[2]; } @arr; Mit der "print"-Anweisung kann der Sortiervorgang beobachtet werden. Ausgegeben werden jeweils zwei Elemente, die miteinander verglichen werden und das Ergebnis -1 ($a kleiner $b), 0 ($a gleich $b) oder 1 ($a größer $b). Unschön an dieser Lösung ist die mehrfache Zerlegung der Arrayelemente in die Einzelwerte, falls das gleiche Arrayelemente mehrfach verglichen wird. Dies wird durch die "Schwartzsche Transformation" weiter unten verbessert. 4.2) Hierarchisch sortieren bgzl. mehrerer getrennter Kriterien --------------------------------------------------------------- In folgendem Beispiel sind Benutzer-IDs einer Bibliothek sind gemäß einiger Sortierkriterien zu sortieren. Ist bzgl. eines Kriteriums kein Unterschied vorhanden, wird das nächste betrachtet. Zuletzt sollten die Benutzer-IDs direkt verglichen werden, die auf jeden Fall unterschiedlich sind, damit eine "stabile Sortierung" entsteht. Die Kriterien sind: 1) Gezahlte Gebühr (Funktionsaufruf "&gebuehr" mit Benutzer-ID) 2) Anzahl geliehener Bücher (Hash "%buecher") 3) Nachname (Hash "%name") 4) Vorname (Hash "%vorname") 5) Benutzer-ID @benutzer_ids = sort { &gebuehr($a) <=> &gebuehr($b) or $buecher{$a} <=> $buecher{$b} or $name{$a} cmp $name{$b} or $vorname{$a} cmp $vorname{$b} or $a <=> $b } @benutzer_ids In der Vergleichsfunktion wird also eine Funktion "&gebuehr" aufgerufen und auf drei Hashes "%buecher", "%name" und "%vorname" zugegriffen, die jeweils die Benutzer-ID als Argument übergeben bekommen. 5) Schwartzsche Transformation ------------------------------ Ein vom Perl-Guru Randal L. Schwartz erfundener Trick (bzw. inzwischen ein sogenanntes "Perl Idiom"), um eine Liste von "Dingen" gemäß einem Kriterium zu sortieren, das eine recht "teure" Funktion des "Dings" ist (d.h. das pro "Ding" aufwendig zu berechnen ist). Beispielsweise ist die Sortierung einer Liste von Dateien nach ihrem Alter (-M = modification time) teuer, da pro Vergleich zwei Dateisystemzugriffe erfolgen: @sortiert = sort { -M $a <=> -M $b } @dateien; Grund: Gemäß dem weiter oben beschriebenen Verfahren, wie "sort" arbeitet, wird jedes Elemente eines Arrays mehrfach an die Sortierfunktion übergeben, die Berechung des Sortierkriteriums erfolgt also "mehrfach pro Ding". Diesen Aufwand kann man auf den minimal notwendigen Aufwand reduzieren, indem man das Sortierkriterium pro "Ding" genau 1x berechnet, zusammen mit dem "Ding" zwischenspeichert und die Sortierung der "Dinge" auf Basis dieser Zwischenwerte durchführt. Man opfert also Speicherplatz, um Laufzeit zu sparen. Dazu wandelt man das ursprüngliche 1-dimensionale Array "@dateien" in ein 2-dimensionales Array um, das aus einer Liste von (anonymen) Array-Referenzen auf die Paare ("Ding", Sortierkriterium) besteht. Pro "Ding" wird dabei 1x das Sortierkriterium berechnet (hier das Dateialter): @refliste = map { [ $_, -M ] } @dateien; Danach sortiert man diese Referenzen nach dem darin als 2. Element gespeicherten Sortierkriterium: @refsortiert = sort { $a->[1] <=> $b->[1] } @refliste; Und am Schluss wirft man das Sortierkriterium wieder weg und behält nur die ursprünglichen "Dinge" wieder übrig: @sortiert = map { $_->[0] } @refsortiert; Diese 3 Schritte führt man normalerweise ohne die obigen Zwischenvariablen @refliste und @refsortiert "auf einen Schlag" durch und nennt das Ganze dann nach ihrem Erfinder "Schwartzsche Transformation": @sortiert = map { $_->[0] } sort { $a->[1] <=> $b->[1] } map { [ $_, -M ] } @dateien; 5.1) Beispiele zu Schwartzscher Transformation ---------------------------------------------- Hier die Sortierung des obigen Arrays mit drei Werten pro Element per Schwartzscher Transformation. In diesem Fall werden Arrayreferenzen auf 4-elementige Arrays mit Originalwert + seine drei Teilwerte sortiert: @arr = qw/ 1_D_100 20_A_200 3_B_8 20_A_-3 20_A_33 -5_B_49 1000_C_-40 /; @sorted = map { $_->[0] } sort { $a->[1] <=> $b->[1] or $a->[2] cmp $b->[2] or $a->[3] <=> $b->[3] } map { my @a = split(/_/, $_); [ $_, $a[0], $a[1], $a[2] ] } @arr; Und hier die Sortierung des obigen Arrays mit Benutzer-IDs per Schwartzscher Transformation. In diesem Fall werden Arrayreferenzen auf 5-elementige Arrays mit Originalwert + vier Sortierkriterien sortiert: @sorted = map { $_->[0] } sort { $a->[1] <=> $b->[1] or $a->[2] <=> $b->[2] or $a->[3] cmp $b->[3] or $a->[4] cmp $b->[4] or $a->[0] <=> $b->[0] } map { [ $_, &gebuehr($_), $buecher{$_}, $name{$_}, $vorname{$_} ] } @benutzer_ids;