Perl Language
Sortierung

Einführung

Syntax

• SUBNAME LIST sortieren
• BLOCKLISTE sortieren
• Sortierliste

Grundlegende lexikalische Sortierung

@sorted = sort @list;

@sorted = sort { $a cmp $b } @list;

sub compare { $a cmp $b }
@sorted = sort compare @list;

Die drei obigen Beispiele machen genau dasselbe. Wenn Sie keine Komparatorfunktion oder keinen Komparator angeben, geht die sort davon aus, dass Sie die Liste rechts von ihrer Liste lexikalisch sort möchten. Dies ist in der Regel die Form, die Sie möchten, wenn Sie Ihre Daten nur in einer vorhersagbaren Reihenfolge benötigen und sich nicht um sprachliche Korrektheit kümmern.

sort übergibt @list in @list an die Vergleicherfunktion, die sort @list , welches Element größer ist. Der cmp Operator führt dies für Zeichenfolgen aus, während <=> das gleiche für Zahlen tut. Der Komparator wird ziemlich oft aufgerufen, im Durchschnitt n * log ( n ) mal, wobei n die Anzahl der zu sortierenden Elemente ist. Daher ist es wichtig, dass er schnell ist. Deshalb verwendet sort vordefinierte globale Paketvariablen ( $a und $b ), um die zu vergleichenden Elemente mit dem Block oder der Funktion zu übergeben, anstatt die richtigen Funktionsparameter zu verwenden.

Wenn Sie use locale , cmp die locale-spezifische Sortierreihenfolge, z. B. sortiert Å nach A unter einem dänischen Locale, nach Z unter einem englischen oder deutschen. Es berücksichtigt jedoch nicht die komplexeren Unicode-Sortierregeln und bietet auch keine Kontrolle über die Reihenfolge. Beispielsweise werden Telefonbücher oft anders als Wörterbücher sortiert. In diesen Fällen werden die Module Unicode::Collate und insbesondere Unicode::Collate::Locale empfohlen.

Numerische Sortierung

@sorted = sort { $a <=> $b } @list;

Beim Vergleich von $a und $b mit dem Operator <=> wird sichergestellt, dass sie standardmäßig numerisch und nicht textlich verglichen werden.

Sortierung umkehren

@sorted = sort { $b <=> $a } @list;
@sorted = reverse sort { $a <=> $b } @list;

Das Sortieren der Elemente in absteigender Reihenfolge kann einfach durch Vertauschen von $a und $b im Vergleicherblock erreicht werden. Manche Menschen bevorzugen jedoch die Klarheit einer separaten reverse auch wenn sie etwas langsamer ist.

Die schwartzianische Transformation

Dies ist wahrscheinlich das bekannteste Beispiel für eine Sortieroptimierung, bei der die funktionalen Programmierfunktionen von Perl zum Einsatz kommen, wenn die Sortierreihenfolge der Artikel von einer teuren Funktion abhängt.

# What you would usually do
@sorted = sort { slow($a) <=> slow($b) } @list;

# What you do to make it faster
@sorted =
map { $_->[0] }
sort { $a->[1] <=> $b->[1] }
map { [ $_, slow($_) ] }
@list;

Das Problem beim ersten Beispiel ist, dass der Komparator sehr oft aufgerufen wird und die Werte immer wieder mit einer langsamen Funktion neu berechnet. Ein typisches Beispiel wäre das Sortieren der Dateinamen nach ihrer Dateigröße:

use File::stat;
@sorted = sort { stat($a)->size <=> stat($b)->size } glob "*";

Dies funktioniert, aber im besten Fall sind zwei Systemaufrufe pro Vergleich erforderlich. Im schlimmsten Fall muss der Datenträger zweimal für jeden einzelnen Vergleich aufgerufen werden, und dieser Datenträger befindet sich möglicherweise in einem überlasteten Dateiserver auf der anderen Seite des Planet.

Tritt in Randall Schwartz 'Trick ein.

Die Schwartzian-Transformation durchläuft @list list @list durch drei Funktionen von unten nach oben. Die erste map wandelt jeden Eintrag in eine Liste mit zwei Elementen des ursprünglichen Elements und das Ergebnis der langsamen Funktion als Sortierschlüssel um. Am Ende haben wir slow() genau einmal für jedes Element aufgerufen. Die folgende sort kann dann einfach auf den Sortierschlüssel zugreifen, indem Sie in der Liste nachschauen. Als wir über die Sortierschlüssel nicht kümmern , sondern brauchen nur die ursprünglichen Elemente in sortierter Reihenfolge, die letzte map wirft die Zweielementlisten aus der bereits sortierten Liste aus erhält weg @sort und gibt eine Liste von nur ihren ersten Mitgliedern .

Groß- und Kleinschreibung

Die traditionelle Methode, um die sort ignorieren zu lassen, besteht uc zum Vergleich Strings an lc oder uc zu übergeben:

@sorted = sort { lc($a) cmp lc($b) } @list;

Dies funktioniert auf allen Versionen von Perl 5 und ist für Englisch völlig ausreichend. Es spielt keine Rolle, ob Sie uc oder lc . Es ist jedoch ein Problem für Sprachen wie Griechisch oder Türkisch, wo es keine 1: 1-Entsprechung zwischen Groß- und Kleinbuchstaben gibt. Je nach Verwendung von uc oder lc Sie unterschiedliche Ergebnisse. Daher haben Perl 5.16 und höher eine Case-Folding- Funktion namens fc , mit der dieses Problem vermieden wird. Moderne mehrsprachige Sortierungen sollten daher Folgendes verwenden:

@sorted = sort { fc($a) cmp fc($b) } @list;