En inbyggd .sort()-metod, hur svårt kan det vara att få den rätt? Tar vi JavaScript som vår måttstock så är det tydligen riktigt svårt. Läs om två större fallgropar som alla som tänker sortera strayer i JavaScript bör känna till.
JavaScript har en .sort -metod, men denna metod har ett antal vassa hörn. Den här artikeln förklarar hur man kan lära sig att leva med sortering i JavaScript.
Den uråldriga konsten att arrangera element
Här är .sort -metoden:
> ["banana", "coconut", "apple"].sort()
["apple", "banana", "coconut"]Lätt som en plätt! Som du ser ovan så returnerar .sort() det sorterade resultatet.
Men, som en TV-shop-snubbe skulle säga, det är inte allt! Istället för att ge dig en ny array med elementen sorterade så är JavaScripts sorteringsmetod "in-place" — det använder arrayen som du skickade in för att arrangera om elementen.
> let fruits = ["banana", "coconut", "apple"]
> fruits.sort()
> // the array `fruits` is now sorted: `["apple", "banana", "coconut"]`Du läste rätt. JavaScripts .sort() både modifierar arrayen, och returnerar den.
På grund av detta så är det lite dålig stil att tilldela resultatet av sorteringen tillbaka till originalarrayen:
> fruits = fruits.sort(); // gör inte detta!Det är inte fel som sådant, det är bara redundant, lite som att laga sin middag en extra gång när den redan är färdiglagad. Mitt råd är att aldrig tilldela i samband med .sort() . (Att kedja sorteringar är OK, eftersom vi har att göra med samma array-referens hela tiden. Men det är fel på grund av bristen på stabilitet; se senare i artikeln.)
Det är också viktigt i kontexter som kräver oföränderlighet ("immutability") att komma ihåg at .sort() pajar den ursprungliga arrayen; om det inte är acceptabelt så kan man klona arrayen innan man sorterar:
> let sortedFruits = [...fruits].sort();Matte är svårt, låt oss gå och shoppa
Eftersom vi hade en så enastående framgång med frukter så fortsätter vi genast till tal:
> [1, 2, 17, 24, 123, 1024].sort()
[1, 1024, 123, 17, 2, 24]Åh nej! JavaScripts svar ränner upp mot våra fasta övertygelser om ordningen hos talen på tallinjen!
Vad är det som händer här? Anledningen till att frukterna kom ut i rätt ordning men att talen inte gjorde det är att JavaScripts sortering är lexikografisk om inget annat anges. Den jämför allt som strängar — och mycket riktigt, "1024" skulle uppträda någonstans mellan "1" och "123" i en (i sanning enorm) ordbok av tal.
(Nu rustar en legion av upprörda läsare upp för att maila mig om det omöjliga i att ställa alla reella tal i ordning i en ordbok. Kära hypotetiska ilskna läsare, var lugna. Vi pratar endast om att placera alla IEEE 754-dubbelprecisionsflyttal i en ordbok. Det är fortfarande väldigt dumt, men definitivt görbart.)
Innan vi tittar på hur man ska fixa numerisk sortering kan vi fråga oss varför defaulten är lexikografisk ordning. Jag tror att det finns två relaterade skäl:
JavaScript, i egenskap av "löst typat" språk, ser inte "array av strängar" eller "array av tal"; det ser bara "array". I någon mening så måste det bestämma sig för en default-sorteringsordning utan att veta någonting om typen på arrayens element.
Om vi behövde besluta oss för en sorteringsordning som funkar på allt, inklusive heterogena arrayer som innehåller en mix av olika typer, då är lexikografisk ordning svaret. Detta baseras på den djupa teorin om "allting kan konverteras till en sträng, hur illa resultatet än må bli".
Att fixa numerisk sortering
Som MDN-sidan för Array.prototype.sort påpekar så accepterar .sort() -metoden en frivillig compareFunction -parameter. Det är så här vi ger oss in i spelet med att ange ordningen, till exempel numerisk ordning.
function compareNumerically(a, b) {
if (Number(a) < Number(b)) {
return -1;
} else if (Number(a) > Number(b)) {
return +1;
} else {
return 0;
}
}En jämförelsefunktion som den ovan lovar att hålla sig till ett protokoll, nämligen att returnera -1, 0, eller +1 beroende på den relativa ordningen mellan sina två parametrar. (Det är tillåtet att returnera vilka positiva eller negativa tal som helst, men det behöver man sällan göra.) -1 betyder " a är mindre än b ", 0 betyder " a och b sorteras lika", +1 betyder " a är större än b ".
Men det slutar inte där. .sort() -metoden förväntar sig att jämförelsefunktionen ska vara konsistent, och returnera samma output givet samma inputs. Det förväntar sig också att jämförelsefunktionen anger en linjärordning, alla element kan placeras i samma ordning på en linje i stil med tallinjen. (Det är OK för värden att betraktas som lika av jämförelsefunktionen även när de inte är identiska. Mer om detta nedan.)
Om du frågar mig så tycker jag att värdena -1, 0, +1 är en smula magiska och oförklarade. De tillhör en svunnen tid när sådana protokoll ansågs gulliga och att känna till dem var en del av att höra till en ingrupp av kamp-ärrade programmerare. Vi kan bättre genom att namnge konstanterna för vad de representerar:
const LESS = -1, EQUAL = 0, GREATER = +1;
function compareNumerically(a, b) {
if (Number(a) < Number(b)) {
return LESS;
} else if (Number(a) > Number(b)) {
return GREATER;
} else {
return EQUAL;
}
}Nu fungerar den numeriska sorteringen:
> [1, 2, 17, 24, 123, 1024].sort(compareNumerically)
[1, 2, 17, 24, 123, 1024]En snabb sidogrej: eftersom vi får lov att returnera vilka positiva eller negativa tal som helst från jämförelsefunktionen, så skulle den här kortare versionen också fungera:
function compareNumerically(a, b) { return a - b }Men som vi kommer att se nedan så får vi fler fördelar i den här artikeln genom att hålla oss kvar vid den längre, mer explicita implementationen.
Att jämföra på en property
Låt oss säga, helt hypotetiskt, att jag har så många datorspel hemma att jag behöver hålla reda på dem i en liten databas och visa dem i en tabell på en webbsida. Ett spel representeras av följande klass:
class Game {
constructor(title, publisher, year) {
this.title = title;
this.publisher = publisher;
this.year = year;
}
}Kom ihåg, det här handlar om hundratals spel. Helt hypotetiskt. Om vi har en array av spel, hur kan vi sortera dem på ett vettigt sätt?
Uppmuntrade av vår framgång med talen definierar vi en sorteringsfunktion för var och en av properties på Game -objekt:
function compareByTitle(a, b) {
if (a.title < b.title) {
return LESS;
} else if (a.title > b.title) {
return GREATER;
} else {
return EQUAL;
}
}
function compareByPublisher(a, b) {
if (a.publisher < b.publisher) {
return LESS;
} else if (a.publisher > b.publisher) {
return GREATER;
} else {
return EQUAL;
}
}
function compareByYear(a, b) {
if (a.year < b.year) {
return LESS;
} else if (a.year > b.year) {
return GREATER;
} else {
return EQUAL;
}
}Uj! Det var mycket kod. Inte bara det, det var mycket repetitiv kod. Det är typ den värsta sorten.
Om vi kisar lite på de tre funktionerna så ser vi att de alla gör samma sak, men med olika properties. Det vill säga, vi kan faktorisera ut "jämför på property"-delen från den delen som anger en specifik property. Här, låt oss göra en funktion som returnerar en skräddarsydd jämförelsefunktion:
function compareByProperty(p) {
return (a, b) => {
if (a[p] < b[p]) {
return LESS;
} else if (a[p] > b[p]) {
return GREATER;
} else {
return EQUAL;
}
};
}Nu kan då våra tre jämförelsefunktioner definieras superlätt; den sköna belöningen för att hålla saker torra ("DRY", "Don't Repeat Yourself"):
let compareByTitle = compareByProperty("title");
let compareByPublisher = compareByProperty("publisher");
let compareByYear = compareByProperty("year");Det är najs, men vi kan gå ett steg längre. Vi kan faktorisera ut "jämför på"-delen från "property"-delen! Skåda:
function compareBy(fn) {
return (a, b) => {
if (fn(a) < fn(b)) {
return LESS;
} else if (fn(a) > fn(b)) {
return GREATER;
} else {
return EQUAL;
}
};
}
function property(p) {
return (e) => e[p];
}Våra propertyjämförelsefunktioner ser nu ut så här:
let compareByTitle = compareBy(property("title"));
let compareByPublisher = compareBy(property("publisher"));
let compareByYear = compareBy(property("year"));Vad tjänade vi på denna sista faktorisering? compareBy -funktionen är mer generell, och kan svälja compareNumerically -funktionen som vi med möda definierade ovan:
let compareNumerically = compareBy(Number);Det är fint när saker blir enklare! Och det "läser" fint också. "Compare by Number"; "Jämför på tal".
Att göra samma sak med andra wrapper-typer skulle också fungera: compareBy(Boolean) , och compareBy(String) . Återigen, den sistnämnda är defaulten, så vi behöver inte ange den om vi inte vill vara explicita.
Om vi tar ett steg tillbaka, det här är trevligt eftersom det bättre stämmer överens av vår intuition om sortering. Konventionen med en jämförelsefunktion med -1, 0, och +1 är flexibel men inte intuitiv. Ofta är tanken vi vill uttrycka "jämför baserat på någonting som vi kan beräkna från varje element". Detta är var compareBy gör. Java 8 lägger till en statisk metod Comparator.comparing som också gör precis detta.
Väldigt stabilt geni
Jag behöver visa mina spel i en bra förutsägbar ordning på sidan. Låt oss säga att jag vill ordna dem främst enligt publicist, men inom varje publicist vill jag sortera dem på titel. Så problemet är "sortera på publicist och sedan (om det finns spel med samma publicist) på titel".
Kan vi göra detta i JavaScript? Svaret är förstås ja, men JavaScript ger sig den på att göra det svårt för oss.
En hyggligt klipsk sak vi kan prova är att sortera två gånger:
games.sort(compareByTitle)
.sort(compareByPublisher); // note: DON'T DO THIS -- see explanation belowNotera det bakvända tänket här: eftersom vi vill ha spelen primärt sorterade på publicist så gör vi den sorteringen sist. Detta resonemang är märkligt men korrekt.
För att detta ska kunna funka, måste den andra sorteringen respektera och bibehålla den sorterade-på-titel-ordningen från den första sorteringen, i alla de fall då den jämför två spel av samma publicist. Det vill säga, om compareByPublisher säger att resultatet är EQUAL så måste .sort() säga "bra, så behåller jag ordningen som den redan är".
En sorteringsalgoritm som gör detta kallas stabil. Det är inte en tautologisk egenskap — en sorteringsalgoritm kan också vara instabil, i vilket fall den inte ger några garantier om den slutliga ordningen hos element som jämför EQUAL (och med största sannolikhet förstör den ordningen).
Så... frågan blir, är JavaScripts sortering garanterat stabil?
Och svaret, som du redan misstänkte illa till mods i maggropen, är nej. Det vore vansinnigt användbart för oss att kunna anta en stabil sortering. Men med JavaScripts inbyggda .sort() så kan man inte anta det. JavaScript är många saker, men det är inte din bästa vän.
Vi talar ofta om JavaScript, men i själva verket finns det många implementationer av JavaScript ute i världen. För närvarande finns dessa större implementationer:
v8 (Chrome, Node.js) — instabil sortering
JavaScriptCore (Safari) — stabil sortering
SpiderMonkey (Firefox) — stabil sortering
ChakraCore (Edge) — stabil sortering
I v8 är sortering instabil. I alla övriga stora browsers är sortering stabil. (I äldre versioner av Firefox och Opera så brukade sortering vara instabil.) Om vi vill att vår kod ska fundera samma tvärsöver alla browsers, gamla och nya, så kan vi inte förutsätta stabil sortering.
(Faktum är att situationen med v8 är mer detaljerad än så. Om ens array råkar innehålla 10 element eller färre, kommer sorteringen att vara stabil, eftersom v8 faller tillbaka på "insertion sort" av prestandaskäl, och insertion sort är stabil! Så man får en stabil sortering ibland, för den typen av korta listor man troligen använder i testfall.)
Ok, så glöm implementationer. Vad har ECMAScript-specifikationen att säga om sorteringars stabilitet? Kanske vi kan tvinga ned specifikationen i halsen på implementatörerna?
Elementen i denna array är sorterade. Sorteringen är inte nödvändigtvis stabil [...]
Tydligen inte. Tack för ingenting, ECMAScript-specifikationen!
Förresten så är JavaScript i ganska gott sällskap här. Vissa språk (Java, Python) har en inbyggd biblioteksfunktion för sortering som garanterar stabilitet, medan andra språk (Ruby, C#) har en som inte garanterar det. Det verkar vara kopplat till det faktum att historiskt sett så har det inte funnits ett bra sätt att få Quicksort både stabil och maximalt snabb. Stabilitet offrad för prestanda.
Att fixa stabil sortering
Hur kan man göra sorteringen stabil? Vad vi behöver är en "kedjad" jämförelsefunktion som gör vad stabil sortering borde ha gjort åt oss automatiskt: den jämför på publicist först, och om dessa jämför lika faller den tillbaka på att jämföra på titel:
function compareByPublisherThenTitle(a, b) {
if (a.publisher < b.publisher) {
return LESS;
} else if (a.publisher > b.publisher) {
return GREATER;
} else {
if (a.title < b.title) {
return LESS;
} else if (a.title > b.title) {
return GREATER;
} else {
return EQUAL;
}
}
}Visuellt ser den koden ut som en jämförelsefunktion upptryckt i en annan. Och ja, den fungerar:
> games.sort(compareByPublisherThenTitle);
Men vi kan helt klart göra bättre ifrån oss, i termer av att faktorisera ut gemensamma lösningar. Hur vore det om vi hade en "kedjad compare " som kan koordinera mellan två compare -funktioner, och faller tillbaka på den andra om den första returnerar EQUAL ?
function chained(fn1, fn2) {
return (a, b) => {
let v = fn1(a, b);
return v === EQUAL
? fn2(a, b)
: v;
};
}Nu kan vi använda denna kedjningsmekanism istället för att manuellt skriva en monstruös kombinerad jämförelsefunktion:
let compareByPublisherThenTitle = chained(compareByPublisher, compareByTitle);Eller, om vi vill:
let compareByPublisherThenTitle = chained(compareBy(property("publisher")), compareBy(property("title"))Stabil sortering på en existerande array
Ovanstående fungerar fint för de fall när vi inte bryr oss om den existerande ordningen på elementen. Men vi kan också föreställa oss scenarior när vi bryr oss om det.
Tänk till exempel på om spelen visas i en tabell på sidan, och tabellen har klickbara kolumnhuvuden "titel", "publicist", och "år". När man klickar på ett kolumnhuvud så kan man sortera spelen baserat på den propertyn.
Förstås önskar vi att den här sorteringen ska vara stabil också; det vill säga, vilken ordning som nu redan existerar bland tabellraderna bör bibehållas när det är möjligt. I det här fallet agerar JavaScripts instabila sortering maximalt mot oss, och vi måste vara kreativa.
För att bibehålla den existerande ordningen skulle vi vilja försätta oss i en situation där vi kan skriva compareBy(property("index")) , där index -propertyn innehåller array-indexet på elementet. Tyvärr finns ingen sådan index -property generellt... så vad nedanstående kod gör är att temporärt lägga till en sådan property innan sorteringen, och sedan plocka bort den efteråt.
let indexedGames = games.map((value, index) => ({ value, index }));
let compareByPropertyStable = (p) => chained(compareBy((e) => e.value[p]), compareBy(property("index")));
indexedGames.sort(compareByPropertyStable("year")); // for example
games = indexedGames.map((o) => o.value);Och voilà, stabil sortering i vår tabell. Återigen, det hela hade varit så mycket enklare om JavaScript bara hade stabil sortering inbyggd — men eftersom det inte har det, så är det här det enklaste vi kommer undan med.
Vi kan också skriva det hela som en enda kedha av map - sort - map :
games = games
.map((value, index) => ({ value, index }))
.sort(compareByPropertyStable("year"))
.map((o) => o.value);(Mönstret som används ovan kallas i Perlvärlden för en Schwartzisk transform.)
I den här fallet är tilldelningen nödvändig, eftersom map producerar fräscha arrayer.
Sammanfattning
Vi är i mål! Låt oss sammanfatta lite:
JavaScript förväntar sig jämförelsefunktioner när man önskar något annat än lexikografisk ordning.
Dessa skrivs på ett väldigt specifikt sätt.
Istället för att skriva dem för hand varje gång är det kortare, renare, säkrare, och mer njutbart att definiera (eller importera) en liten uppsättning hjälpfunktioner ( compareBy , property , chained ) så att vi funktionellt kan sätta samman den jämförelsefunktion vi är intresserade av.
JavaScripts specifikation och implementationer garanterar inte en stabil sortering i allmänhet.
Istället, om man vill ha en stabil sortering (vilket man ofta vill) måste man skriva sin jämförelsefunktion för att ta hänsyn till detta.
Även detta kan göras praktiskt och behagligt genom att sätta samman funktioner.
Addendum: ett sött domänspecifikt språk
När jag gjorde efterforskningar för den här artikeln slog det mig att någon redan kan ha adresserat samma problem redan i npm-ekosystemet. Och mycket riktigt så hittade jag comparators-modulen, som tar avstamp från Java 8:s API och låter oss sortera våra spel så här:
games.sort(Comparators.comparing("publisher").thenComparing("title"));I det här fallet skickar vi stängar till comparing -metoderna, men enligt API:t fungerar det även att skicka godtyckliga selektorfunktioner. Den hemliga såsen som får ovanstående att fungera — väldigt JavaScriptigt — är att jämförelsefunktionen som returneras från Comparators.comparing har utsmyckats med en .thenComparing -metod.
Addendum: ES2019
Från och med 2019 års utgåva av EcmaScript-standarden så är sortering garanterat stabil. Hurra!
Men var medveten om att detta inte ändrar det faktum att det i många år kommer att finnas äldre implementationer därute på folks datorer och enheter som inte sorterar stabilt. Så av bakåtkompatibilitetsskäl för överskådlig framtid så gäller råden i den här artikeln fortfarande.
Av Carl Mäsak
Comments