Ordinare e deduplicare un elenco senza sorprese

Ordinare e deduplicare sembrano le due cose più semplici che si possano fare a un elenco, ed è per questo che i risultati sono così spesso sbagliati in silenzio. Entrambe poggiano su un confronto, e non esiste una risposta unica a che cosa renda uguali due righe o faccia venire prima una di esse.

L'ordine lessicografico non è l'ordine numerico

Il confronto predefinito per il testo percorre due stringhe un carattere alla volta, confronta i code point e si ferma alla prima differenza. In esso nulla sa che cosa sia un numero.

input:   img1.png, img2.png, img10.png
sorted:  img1.png, img10.png, img2.png

img10.png finisce al secondo posto perché al quarto carattere 1 (U+0031) è più basso di 2 (U+0032), e il confronto finisce lì. La stessa regola mette la versione 1.10 prima della 1.9, ed elenca una cartella di screenshot in un ordine diverso da quello in cui sono stati scattati.

Il confronto numerico sistema anche i negativi: lessicograficamente -10 cade fra -1 e -2, perché un segno meno è solo un altro carattere con il suo code point.

Maiuscole prima delle minuscole, e altre sorprese dei code point

In ASCII le maiuscole occupano le posizioni da 65 a 90 e le minuscole da 97 a 122, quindi ogni maiuscola viene prima di ogni minuscola.

Le cifre stanno sotto tutte le lettere, lo spazio (32) sotto ogni carattere stampabile, e una riga vuota ancora più sotto, quindi un ordinamento crescente raccoglie in cima le righe vuote e quelle che iniziano con uno spazio, mentre uno decrescente le raccoglie in fondo.

Gli spazi in coda sono la versione invisibile dello stesso problema: apple e apple si ordinano l'uno accanto all'altro e sembrano un duplicato che si rifiuta di essere rimosso. Lo spazio insecabile (U+00A0) è peggio, disegnato in modo identico a uno spazio normale ma ordinato sopra ogni lettera, e così pure il ritorno a capo che resta quando un file Windows viene diviso solo sui caratteri di nuova riga. Se due righe sembrano identiche e continuano a non fondersi, cerca i caratteri nascosti.

Lo stesso elenco si ordina diversamente in due paesi

L'ordine per code point mette anche ogni carattere accentato dopo ogni carattere senza accento. Zürich viene dopo Zzz, e Ärger dopo zebra. Nessuna lingua ordina il proprio alfabeto in quel modo. La collazione che tiene conto della locale confronta invece secondo le regole della lingua, e quelle regole sono in disaccordo fra loro.

In JavaScript tutto questo sta in Intl.Collator:

const words = ["Zebra", "Ärger", "Apfel"];

words.sort(new Intl.Collator("de").compare);
// Apfel, Ärger, Zebra

words.sort(new Intl.Collator("sv").compare);
// Apfel, Zebra, Ärger

Lo stesso oggetto copre anche i problemi precedenti. { numeric: true } confronta le sequenze di cifre come numeri, cioè l'ordine naturale, e sensitivity stabilisce che cosa conta come differenza: "base" ignora maiuscole e accenti, "accent" ignora solo le maiuscole, "case" ignora solo gli accenti. Omettere la locale usa quella impostata sulla macchina, ed è così che lo stesso codice restituisce due ordini diversi su due portatili. Indica la locale quando il risultato deve coincidere ovunque.

Quali duplicati contano come duplicati

La deduplicazione è definita bene tanto quanto lo è il test di uguaglianza che le sta dietro. Prendi cinque righe che si mostrano tutte come la parola cafe con l'accento acuto:

Quattro regole ragionevoli danno quattro risposte diverse:

Nessuna di esse è sbagliata; rispondono a domande diverse. La normalizzazione conta più di quanto sembri, perché il testo che arriva dai nomi di file di macOS tende ad arrivare decomposto (NFD) e quello che arriva da Windows e dai form web composto (NFC), quindi un elenco incollato da due fonti si porta dietro dei gemelli invisibili. NFKC va oltre, riducendo i caratteri di compatibilità come la legatura fi ai loro equivalenti semplici.

Per convenzione vince la prima occorrenza, quindi se la copia disordinata è stata incollata per prima, è quella a sopravvivere. E rimuovere i duplicati è una richiesta diversa dal trovare le voci uniche: Rimuovi righe duplicate lascia una copia di ciascuna, mentre l'insieme delle voci uniche in Frequenza elenco è il gruppo più piccolo delle voci che compaiono esattamente una volta.

Stabilità, e ordinare su due chiavi

Un ordinamento stabile garantisce che le voci che il comparatore considera uguali mantengano l'ordine che avevano in ingresso. È questo che fa funzionare l'ordinamento su più chiavi tramite passaggi ripetuti: ordina prima per la chiave meno importante, poi per la più importante. Ordinare per nome e poi per reparto dà i reparti in ordine, con i nomi ordinati dentro ciascuno. Un ordinamento instabile disfa il primo passaggio mentre esegue il secondo, e il risultato sembra quasi giusto, il che è peggio che sembrare sbagliato.

L'inversione porta con sé lo stesso tranello, perché ribaltare un elenco ordinato inverte anche ogni gruppo a pari merito. Usa Inverti elenco quando quello che vuoi è capovolgere l'intero ordine, non come scorciatoia per un ordinamento decrescente.

Le implementazioni sono diverse fra loro. Array.prototype.sort di JavaScript è tenuto a essere stabile solo da ES2019; prima V8 usava un quicksort instabile sopra una certa dimensione dell'array, quindi lo stesso codice si comportava diversamente su dieci voci e su diecimila. Il sorted di Python è stabile, e il sort di GNU non lo è a meno che non gli si passi -s.

Mescolare non è un tipo di ordinamento

Il mescolamento in una riga, list.sort(() => Math.random() - 0.5), è distorto. Un ordinamento presuppone che il suo comparatore descriva un ordine coerente, e interroga solo il sottoinsieme di coppie di cui il suo algoritmo ha bisogno. Un comparatore che tira un numero nuovo a ogni chiamata rompe quel presupposto, quindi il risultato dipende dall'algoritmo e dalla lunghezza dell'array: le voci tendono a restare vicine a dove sono partite, e alcune permutazioni escono molto più spesso di altre.

Un mescolamento corretto usa Fisher-Yates, che percorre l'elenco dalla fine e scambia ogni voce con una voce scelta in modo uniforme fra quella stessa posizione e quelle precedenti:

for (let i = list.length - 1; i > 0; i--) {
  const j = Math.floor(Math.random() * (i + 1));
  [list[i], list[j]] = [list[j], list[i]];
}

La variante sbagliata più diffusa usa Math.random() * list.length dentro il ciclo, pescando ogni volta dall'intero array. Questo dà n elevato alla n sequenze di estrazioni ugualmente probabili, che non si divide in modo esatto per gli n fattoriale ordinamenti possibili, quindi alcuni ordinamenti escono più spesso.

Casualità e ordinamento si possono combinare correttamente assegnando in anticipo a ogni voce una chiave casuale e ordinando per quella chiave, perché così il comparatore resta coerente. L'errore è tirare il dado dentro il confronto.

L'ordine in cui vanno i passi

La maggior parte dei problemi con gli elenchi nasce dall'eseguire le operazioni giuste nella sequenza sbagliata.

1. Prima spoglia le voci. Un elenco copiato da del codice arriva nella forma "apple",; le virgolette e la virgola fanno parte della stringa, quindi non corrisponderà mai ad apple. Spoglia le voci le elimina.
2. Taglia i bordi e normalizza, così che uguaglianza significhi quello che pensi significhi.
3. Deduplica, con la regola di confronto scelta di proposito invece che accettata come impostazione predefinita.
4. Ordina. Ordina righe copre l'ordine testuale, numerico, per lunghezza e casuale; aggiungi una locale per i dati con accenti.
5. Rimodella per ultimo. Raggruppa voci taglia il risultato in blocchi di dimensione fissa per rispettare un limite per richiesta, e Ruota elenco fa scorrere tutto senza cambiare l'ordine interno.

Deduplicare prima di tagliare i bordi lascia in giro dei quasi duplicati, e ordinare prima di deduplicare si limita a ordinare righe che stanno per essere buttate via.