Řazení a odstraňování duplicit v seznamu bez překvapení

Řazení a odstraňování duplicit vypadají jako dvě nejjednodušší věci, které se seznamem můžete udělat, a právě proto jsou výsledky tak často tiše špatné. Obojí stojí na porovnání a na to, co dělá dva řádky si rovnými nebo co staví jeden řádek na první místo, neexistuje jediná odpověď.

Lexikografické pořadí není číselné pořadí

Výchozí porovnání textu prochází dva řetězce znak po znaku, porovnává kódové body a zastaví se u prvního rozdílu. Nic v něm neví, co je to číslo.

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

img10.png skončí na druhém místě, protože na čtvrtém znaku je 1 (U+0031) nižší než 2 (U+0032) a porovnání tam končí. Totéž pravidlo staví verzi 1.10 před 1.9 a vypíše složku se snímky obrazovky v jiném pořadí, než v jakém vznikly.

Číselné porovnání opravuje i záporná čísla: lexikograficky padne -10 mezi -1 a -2, protože znaménko minus je jen další znak s kódovým bodem.

Velká písmena před malými a další překvapení kódových bodů

V ASCII zabírají velká písmena pozice 65 až 90 a malá 97 až 122, takže se každé velké písmeno řadí před každé malé.

Číslice leží pod všemi písmeny, mezera (32) pod každým tisknutelným znakem a prázdný řádek ještě pod ní, takže vzestupné řazení nasbírá prázdné řádky a řádky začínající mezerou úplně nahoře a sestupné řazení je nasbírá dole.

Bílé znaky na konci jsou neviditelnou verzí téhož problému: apple a apple se seřadí vedle sebe a vypadají jako duplicita, která se odmítá odstranit. Horší je nezlomitelná mezera (U+00A0), vykreslená stejně jako běžná mezera, ale řadící se nad každé písmeno, a stejně tak návrat vozíku, který zůstane, když se soubor z Windows rozdělí jen podle znaků nového řádku. Pokud dva řádky vypadají totožně a přesto se nesloučí, hledejte skryté znaky.

Týž seznam se ve dvou zemích seřadí jinak

Pořadí podle kódových bodů také staví každý znak s diakritikou za každý znak bez ní. Zürich se řadí za Zzz a Ärger za zebra. Žádný jazyk si vlastní abecedu takhle neřadí. Řazení podle lokalizace místo toho porovnává podle jazykových pravidel a ta pravidla se navzájem neshodují.

V JavaScriptu to obstarává 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

Tentýž objekt pokrývá i dřívější problémy. { numeric: true } porovnává série číslic jako čísla, což je přirozené pořadí, a sensitivity určuje, co se počítá jako rozdíl: "base" ignoruje velikost písmen i diakritiku, "accent" ignoruje jen velikost písmen, "case" ignoruje jen diakritiku. Vynechání lokalizace použije to, co je nastavené na stroji, a právě tak tentýž kód vrátí na dvou noteboocích dvě různá pořadí. Když se výstup musí shodovat všude, lokalizaci uveďte.

Které duplicity se počítají jako duplicity

Odstraňování duplicit je definované jen tak dobře, jak dobře je definován test rovnosti za ním. Vezměte pět řádků, které se všechny vykreslí jako slovo cafe s čárkou nad e:

Čtyři rozumná pravidla dají čtyři různé odpovědi:

Ani jedno není špatně; odpovídají na různé otázky. Normalizace hraje větší roli, než se zdá, protože text z názvů souborů na macOS přichází většinou rozložený (NFD) a text z Windows a z webových formulářů složený (NFC), takže seznam vložený ze dvou zdrojů nasbírá neviditelná dvojčata. NFKC jde dál a slučuje kompatibilní znaky, jako je ligatura fi, na jejich prosté ekvivalenty.

Konvencí vyhrává první výskyt, takže pokud byla jako první vložená ta neupravená kopie, přežije právě ona. A odstranit duplicity je jiný požadavek než najít unikátní položky: Remove Duplicate Lines nechá z každé jednu, zatímco unikátní množina v List Frequency je menší skupina položek, které se objevují přesně jednou.

Stabilita a řazení podle dvou klíčů

Stabilní řazení zaručuje, že položky, které komparátor označí za rovné, si zachovají pořadí ze vstupu. Právě díky tomu funguje řazení podle více klíčů opakovanými průchody: nejdřív seřaďte podle nejméně důležitého klíče, pak podle nejdůležitějšího. Řazení podle jména a pak podle oddělení dá oddělení v pořadí a v každém z nich seřazená jména. Nestabilní řazení první průchod během druhého zruší a výsledek vypadá skoro správně, což je horší, než kdyby vypadal špatně.

Stejný háček nese obracení, protože překlopení seřazeného seznamu obrátí i každou skupinu shodných položek. Reverse List použijte tehdy, když chcete otočit celé pořadí, ne jako zkratku k sestupnému řazení.

Implementace se liší. Array.prototype.sort v JavaScriptu musí být stabilní teprve od ES2019; předtím V8 nad určitou malou velikostí pole používal nestabilní quicksort, takže se tentýž kód choval jinak u deseti položek a u deseti tisíc. sorted v Pythonu stabilní je a GNU sort není, dokud mu nedáte -s.

Zamíchání není druh řazení

Jednořádkové zamíchání list.sort(() => Math.random() - 0.5) je zkreslené. Řazení předpokládá, že jeho komparátor popisuje konzistentní pořadí, a ptá se jen na tu podmnožinu dvojic, kterou jeho algoritmus potřebuje. Komparátor, který při každém volání hodí nové číslo, tento předpoklad porušuje, takže výsledek závisí na algoritmu a na délce pole: položky mají sklon zůstávat blízko místa, kde začínaly, a některé permutace se objevují mnohem častěji než jiné.

Správné zamíchání používá Fisherův-Yatesův algoritmus, který jde od konce a každou položku prohodí s rovnoměrně vybranou položkou na její pozici nebo před ní:

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]];
}

Běžná rozbitá varianta používá uvnitř smyčky Math.random() * list.length a losuje pokaždé z celého pole. To dá n na n stejně pravděpodobných posloupností losů, což se beze zbytku nedělí n faktoriálem uspořádání, takže některá uspořádání vycházejí častěji.

Náhodu a řazení lze zkombinovat správně tak, že každé položce hned na začátku přiřadíte jeden náhodný klíč a podle něj seřadíte, protože komparátor pak zůstane konzistentní. Chyba je házet kostkou uvnitř porovnání.

Pořadí, ve kterém kroky jdou

Většina problémů se seznamy pochází z toho, že se správné operace dělají ve špatném pořadí.

1. Nejdřív rozbalte. Seznam zkopírovaný z kódu dorazí jako "apple",; uvozovky a čárka jsou součástí řetězce, takže se nikdy neshodne s apple. Unwrap List Items je odstraní.
2. Ořežte okraje a normalizujte, aby rovnost znamenala to, co si myslíte, že znamená.
3. Odstraňte duplicity, přičemž pravidlo shody zvolte záměrně, ne že vezmete výchozí.
4. Seřaďte. Sort Lines pokrývá textové, číselné, délkové i náhodné pořadí; u dat s diakritikou přidejte lokalizaci.
5. Tvar upravte až nakonec. Group List Items rozseká výsledek na dávky pevné velikosti kvůli limitu na jeden požadavek a Rotate List všechno posune, aniž by změnil vnitřní pořadí.

Odstraňování duplicit před ořezáním okrajů nechá téměř duplicity na místě a řazení před odstraněním duplicit jen seřadí řádky, které se za chvíli zahodí.