Ordinare il testo non è una sola operazione: quattro ordini che si dicono tutti alfabetici

Quattro cose chiamate alfabetico

Un pulsante di ordinamento offre un'opzione e lascia intendere che esista una risposta. Ne esistono almeno quattro, e non sono raffinamenti l'una dell'altra: sono ordini diversi che restituiscono liste diverse dallo stesso input. L'ordine per unità di codice confronta i valori numerici delle unità UTF-16 di cui è fatta la stringa. L'ordine naturale legge le sequenze di cifre come numeri. La collazione per locale applica le regole proprie di una lingua su quali lettere contano come la stessa lettera. Le varianti di collazione dividono poi una stessa lingua in più ordini difendibili, perché i dizionari tedeschi e gli elenchi telefonici tedeschi non sono mai andati d'accordo.

Tutto ciò che segue è stato eseguito, non ricordato. Ogni lista è stampata esattamente come l'ha restituita Node 26.3, e gli script sono abbastanza corti da riscrivere: un array, un sort, un console.log.

Ordine per unità di codice: cosa fa davvero .sort()

Chiamato senza comparatore, Array.prototype.sort converte ogni elemento in stringa e confronta quelle stringhe per unità di codice UTF-16. È una regola documentata, non un incidente, e produce due sintomi visibili. Le maiuscole occupano l'intervallo 0x41–0x5A e le minuscole 0x61–0x7A, quindi ogni maiuscola precede ogni minuscola. E le cifre sono confrontate come caratteri: ["capitolo10","capitolo9","capitolo2"] restituisce capitolo10, capitolo2, capitolo9, perché «1» è 0x31 e «9» è 0x39, e il confronto si ferma alla prima differenza.

Il terzo sintomo è quello che arriva al lettore. Ogni lettera con segno diacritico vive sopra 0x7A, quindi l'ordine per unità di codice spinge l'intero alfabeto accentato dopo la z. ["Àncora","ancora","zucchero","elite"] restituisce ancora, elite, zucchero, Àncora. ["Öl","Ohr","Zebra","Ähre"] restituisce Ohr, Zebra, Ähre, Öl. ["ñu","nube","niño","zorro"] restituisce niño, nube, zorro, ñu. ["ação","acordo","água","avô"] restituisce acordo, avô, ação, água. Quattro lingue, quattro risposte sbagliate, una riga di codice.

L'ordine per unità di codice non è inutile. È totale, trasparente, veloce — 20 000 parole ordinate in 6 ms nel banco di prova qui sotto — e identico in ogni runtime e ogni locale, il che lo rende la scelta giusta per tutto ciò che legge una macchina: chiavi di indice, secchi di deduplicazione, identificatori di cache, serializzazioni canoniche. È sbagliato solo quando l'output è destinato a una persona.

Ordine naturale: leggere le cifre come numeri

L'ordine naturale — quello di un gestore di file — tratta una sequenza di cifre dentro una stringa come un solo numero anziché come una sequenza di caratteri. In JavaScript è un'opzione: new Intl.Collator("it", { numeric: true }). Su ["capitolo10","capitolo9","capitolo2"] restituisce capitolo2, capitolo9, capitolo10, e su una lista più lunga ["item2","item9","item10","item100","item20"] restituisce item2, item9, item10, item20, item100, mentre il .sort() predefinito restituisce item10, item100, item2, item20, item9.

Due limiti vanno conosciuti prima di attivarla ovunque. La collazione numerica è una comodità di presentazione, non aritmetica: confronta sequenze di cifre, quindi ha opinioni su «v1.10» contro «v1.9» che un analizzatore di versioni semantiche non condividerebbe, e non dice nulla di utile su segni, separatori decimali o separatori delle migliaia. E cambia la risposta per chiavi che contengono cifre solo per caso, come codici prodotto in cui 0090 e 90 sono articoli diversi. Attivala per le liste che una persona scorre, lasciala spenta per gli identificatori.

Collazione per locale: il tedesco contro lo svedese

La collazione per locale è il caso classico, e il tedesco contro lo svedese è la coppia classica. Prendi ["Öl","Ohr","Zebra","Ähre"]. Sotto new Intl.Collator("de") esce Ähre, Ohr, Öl, Zebra: ä è una variante di a, ö una variante di o, e il segno diacritico decide solo i pareggi. Sotto new Intl.Collator("sv") le stesse quattro stringhe escono Ohr, Zebra, Ähre, Öl: in svedese å, ä e ö sono le ultime tre lettere dell'alfabeto, dopo la z. Nessuno dei due è un bug. Sono due lingue con due alfabeti, e la lista deve sceglierne uno.

Ora la parte scomoda: per questa lista il .sort() predefinito restituisce Ohr, Zebra, Ähre, Öl — carattere per carattere la risposta svedese. Un programma che ha saltato il locale non ha prodotto «nessun ordine in particolare». Ha prodotto in silenzio un ordine straniero preciso, e continuerà a produrlo per ogni lista tedesca, spagnola, portoghese e italiana che tocca.

Le altre locale di questo articolo si comportano allo stesso modo. Lo spagnolo fa di ñ una lettera a sé dopo la n: ["ñu","nube","niño","zorro"] dà niño, nube, ñu, zorro sotto es, mentre l'ordine per unità di codice esilia ñu dopo zorro. Il portoghese tratta gli accenti come spareggi: ["ação","acordo","água","avô"] esce in ordine di dizionario sotto pt e scombinato sotto .sort(). Il tedesco e lo svedese si dividono sugli umlaut come sopra. E il francese ha un ordine davvero regionale: su ["cote","coté","côte","côté"], fr restituisce cote, coté, côte, côté, mentre fr-CA restituisce cote, côte, coté, côté, perché il francese canadese confronta gli accenti a partire dalla fine della parola.

Una lingua, più ordini: le varianti di collazione

Anche dentro una sola lingua c'è più di una risposta corretta, e il CLDR di Unicode le distribuisce come varianti con nome, scelte tramite la stringa di locale. Il tedesco ne ha due di uso quotidiano. La collazione da dizionario, de, ordina ["Göbel","Goethe","Godel","Gözde","Gott"] come Göbel, Godel, Goethe, Gott, Gözde: ö è una variante di o. La collazione da elenco telefonico, de-u-co-phonebk, ordina le stesse cinque come Godel, Göbel, Goethe, Gözde, Gott, perché ö viene espanso in oe — il che mette Göbel fra Godel e Goethe, esattamente dove cercherebbe chi cerca «Goebel».

Accanto alla variante stanno due manopole che cambiano la risposta quanto lei. sensitivity decide quali differenze contano: su «cote» contro «côte» e «cote» contro «Cote», la sensibilità «base» dichiara uguali entrambe le coppie, «accent» separa l'accento ma non il maiuscolo, «case» separa il maiuscolo ma non l'accento, e «variant» — il valore predefinito — separa entrambi. caseFirst decide chi vince un pareggio: su ["apple","Apple","APPLE"] il predefinito restituisce apple, Apple, APPLE, e caseFirst: "upper" restituisce APPLE, Apple, apple. Nessuna delle due manopole è cosmetica. sensitivity è anche ciò che rende un collatore uno strumento di ricerca: con «base», compare restituisce 0 per stringhe che un lettore chiamerebbe la stessa parola.

Stabilità: cosa succede ai pareggi

Un ordinamento è stabile quando gli elementi che risultano uguali mantengono l'ordine relativo che avevano in ingresso. Conta nel momento in cui si ordina su una chiave parziale — un'iniziale, una categoria, una data senza ora — perché i pareggi non sono rari casi limite: sono la maggior parte della lista. Ordinando dieci nomi solo per iniziale, gli elementi con iniziale a sono usciti nelle posizioni d'ingresso 1, 2, 4, 6, 8 e quelli con iniziale b nelle posizioni 0, 3, 5, 7, 9: ogni gruppo conservato, in ordine.

La specifica richiede che Array.prototype.sort sia stabile dallo ES2019. Prima, i motori potevano usare un algoritmo instabile oltre una certa lunghezza dell'array, e diversi lo facevano: per questo i consigli più vecchi suggeriscono un comparatore composito o di portarsi dietro l'indice. Il requisito vale a qualunque dimensione: un array di mille elementi ordinato su una chiave con soli tre valori distinti è tornato con ogni gruppo in ordine d'ingresso. Puoi quindi costruire un ordinamento a più chiavi ordinando più volte, dalla chiave meno significativa alla più significativa — prima il nome, poi il cognome — e contare sulla sopravvivenza dei passaggi precedenti.

Quanto costa, e la regola che ne segue

Ordinare tenendo conto del locale costa più che ordinare per unità di codice, ma non quanto si teme, e l'errore costoso è un altro. Ordinando 20 000 parole in Node 26.3: il .sort() predefinito ha impiegato 6 ms, a.localeCompare(b, "de") 12 ms, un collatore costruito una volta e riusato 28 ms — e costruire un new Intl.Collator dentro il comparatore ha impiegato 1 771 ms, sessanta volte più lento del riuso. Il costo non è la collazione. Il costo è costruire il collatore centinaia di migliaia di volte.

Resta una regola abbastanza corta da applicare. Se l'output lo legge una macchina, ordina per unità di codice e mettilo per iscritto. Se lo legge una persona, nomina un locale — la lingua in cui è scritto il documento, non quella del browser che lo rende —, costruisci un solo Intl.Collator, decidi numeric e sensitivity di proposito, e riusalo. L'unica cosa mai difendibile è chiamare .sort() su testo destinato al lettore e chiamare alfabetico il risultato.

Domande frequenti

Perché «Zebra» viene ordinato prima di «apple»?

Perché .sort() senza comparatore confronta unità di codice UTF-16, e ogni maiuscola ASCII (0x41–0x5A) ha un valore minore di ogni minuscola ASCII (0x61–0x7A). Non ordina lettere, ordina numeri che rappresentano lettere. Qualsiasi collatore di locale lo sistema: new Intl.Collator("en").compare dà apple, Banana, zebra, Zebra in quest'ordine, con il maiuscolo come ultimo spareggio e non come primo criterio.

L'ordinamento di JavaScript è stabile?

Sì, ed è obbligatorio. ES2019 ha reso la stabilità un requisito della specifica per Array.prototype.sort, e Array.prototype.toSorted segue la stessa regola. Verificato qui su un array di mille elementi ordinato per una chiave con tre valori distinti: ogni gruppo è tornato in ordine d'ingresso. È quella garanzia a permettere di realizzare un ordinamento multicolonna come una sequenza di ordinamenti a colonna singola, partendo dalla colonna meno significativa.

Quale locale uso se non conosco quella del lettore?

Usa la lingua del contenuto, non quella del dispositivo del lettore. Una lista di nomi di prodotti tedeschi va in collazione tedesca chiunque la guardi, esattamente come un catalogo tedesco stampato. Ripiegare sul valore predefinito del runtime è l'opzione peggiore, perché è invisibile: new Intl.Collator() senza argomenti si è risolto in en-US sulla macchina su cui è stato scritto questo articolo, e si risolverebbe diversamente sulla successiva, così la stessa lista si ordinerebbe in modo diverso su due server senza cambiare una riga di codice.

Perché il mio gestore di file mette item2 prima di item10 e il mio codice no?

Il gestore di file usa l'ordine naturale: riconosce la sequenza di cifre come un numero. Il tuo codice confronta caratteri, quindi si ferma su «1» contro «9» e non legge mai il resto. Aggiungi { numeric: true } a un Intl.Collator, o passa la stessa opzione a localeCompare, e i due vanno d'accordo. Non provare a emularlo riempiendo di zeri le stringhe visualizzate: sistema l'ordinamento e rovina le etichette.

localeCompare è troppo lento per una lista lunga?

Di per sé no. Su 20 000 parole in Node 26.3, a.localeCompare(b, "de") ha impiegato 12 ms e un Intl.Collator riusato 28 ms, contro 6 ms del .sort() predefinito: una differenza che nessuno noterà. Davvero lento è costruire un collatore dentro il comparatore: così lo stesso ordinamento ha impiegato 1 771 ms, perché si fabbrica un collatore nuovo per ciascuno delle centinaia di migliaia di confronti. Costruiscilo una volta, fuori dall'ordinamento, e passa il suo .compare.

Come ordino nomi tedeschi come fa un elenco telefonico?

Chiedi la variante di collazione per nome: new Intl.Collator("de-u-co-phonebk"). La parte -u-co- di un identificatore di locale seleziona una collazione, e phonebk è l'adattamento dell'elenco telefonico tedesco, in cui ö si comporta come oe, ä come ae e ü come ue. Su ["Göbel","Goethe","Godel","Gözde","Gott"], il semplice de dà Göbel, Godel, Goethe, Gott, Gözde e de-u-co-phonebk dà Godel, Göbel, Goethe, Gözde, Gott. Altre lingue hanno le proprie varianti: una lista cinese può essere ordinata per pinyin o per numero di tratti allo stesso modo.