Perl Language
Sortering

Introduktion

Syntax

• sortera SUBNAME LIST
• sortera BLOCK LIST
• sortera LIST

Grundläggande Lexical Sort

@sorted = sort @list;

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

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

De tre exemplen ovan gör exakt samma sak. Om du inte tillhandahåller någon komparatorfunktion eller -block, förutsätter sort du vill att listan till höger sorteras lexiskt. Detta är vanligtvis det formulär du vill ha om du bara behöver dina data i någon förutsägbar ordning och inte bryr dig om språklig korrekthet.

sort överför par av objekt i @list till komparatorfunktionen, som säger sort vilket objekt som är större. cmp operatören gör detta för strängar medan <=> gör samma sak för siffror. Jämföraren kallas ganska ofta, i genomsnitt n * log ( n ) gånger, där n är antalet element som ska sorteras, så det är viktigt att det är snabbt. Detta är anledningen till att sort använder fördefinierade globala paketvariabler ( $a och $b ) för att skicka elementen som ska jämföras med blocket eller funktionen, istället för korrekta funktionsparametrar.

Om du use locale , tar cmp hänsyn till landets specifika sorteringsordning, t.ex. kommer den att sortera Å som A under en dansk språk men efter Z under en engelsk eller tysk. Det tar dock inte hänsyn till de mer komplexa reglerna för sortering av Unicode och erbjuder inte heller någon kontroll över ordningen - till exempel sorteras telefonböcker ofta annorlunda än ordböcker. I dessa fall Unicode::Collate och särskilt Unicode::Collate::Locale .

Numerisk sortering

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

Att jämföra $a och $b med operatören <=> säkerställer att de jämförs numeriskt och inte textmässigt som standard.

Omvänd sortering

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

Sortering av objekt i fallande ordning kan helt enkelt uppnås genom att byta $a och $b i komparatorblocket. Vissa människor föredrar dock tydligheten i ett separat reverse även om det är något långsammare.

Schwartzian-omvandlingen

Detta är förmodligen det mest kända exemplet på en sorteringsoptimering som använder Perls funktionella programmeringsanläggningar, som kan användas där sorteringsordning för objekt beror på en dyr funktion.

# 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;

Problemet med det första exemplet är att komparatorn kallas väldigt ofta och håller omberäknar värden med en långsam funktion om och om igen. Ett typiskt exempel skulle vara att sortera filnamn efter deras filstorlek:

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

Detta fungerar, men i bästa fall medför det omkostnaden för två systemsamtal per jämförelse, i värsta fall måste den gå till disken, två gånger, för varje enskild jämförelse, och den disken kan vara i en överbelastad filserver på andra sidan av planet.

Gå in i Randall Schwartz's trick.

Schwartzian Transform skjuter i @list och botten @ @list genom tre funktioner, från topp till topp. Den första map förvandlar varje post till en lista med två element över det ursprungliga objektet och resultatet av den långsamma funktionen som en sorteringsknapp, så i slutet av detta har vi kallat slow() exakt en gång för varje element. Följande sort kan sedan helt enkelt komma åt sorteringsknappen genom att titta i listan. Eftersom vi inte bryr oss om sorteringstangenterna men bara behöver de ursprungliga elementen i sorterad ordning, kastar den sista map bort två-elementslistorna från den redan sorterade listan den får från @sort och returnerar en lista med bara deras första medlemmar .

Fall okänslig sortering

Den traditionella tekniken för att göra sort ignorera fall är att överföra strängar till lc eller uc för jämförelse:

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

Detta fungerar på alla versioner av Perl 5 och är helt tillräckligt för engelska; det spelar ingen roll om du använder uc eller lc . Men det utgör ett problem för språk som grekiska eller turkiska där det inte finns en korrespondens 1: 1 mellan stora och små bokstäver så att du får olika resultat beroende på om du använder uc eller lc . Därför har Perl 5.16 och högre en fallviktsfunktion som kallas fc som undviker detta problem, så modern flerspråkig sortering bör använda detta:

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