Sortowanie i usuwanie duplikatów z listy bez niespodzianek

Sortowanie i usuwanie duplikatów wyglądają na dwie najprostsze rzeczy, jakie można zrobić z listą, i właśnie dlatego wyniki tak często bywają po cichu błędne. Jedno i drugie opiera się na porównaniu, a nie ma jednej odpowiedzi na pytanie, co sprawia, że dwa wiersze są równe albo że jeden wiersz idzie pierwszy.

Porządek leksykograficzny to nie porządek liczbowy

Domyślne porównanie tekstu przechodzi przez dwa ciągi znak po znaku, porównuje punkty kodowe i zatrzymuje się na pierwszej różnicy. Nic w nim nie wie, czym jest liczba.

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

img10.png ląduje na drugim miejscu, ponieważ na czwartym znaku 1 (U+0031) jest niższe niż 2 (U+0032) i porównanie tam się kończy. Ta sama reguła stawia wersję 1.10 przed 1.9 i wypisuje folder ze zrzutami ekranu w kolejności innej niż ta, w jakiej powstały.

Porównanie liczbowe naprawia również liczby ujemne: leksykograficznie -10 wypada pomiędzy -1 a -2, ponieważ znak minus jest po prostu kolejnym znakiem z punktem kodowym.

Wielkie litery przed małymi i inne niespodzianki punktów kodowych

W ASCII wielkie litery zajmują pozycje od 65 do 90, a małe od 97 do 122, więc każda wielka litera sortuje się przed każdą małą.

Cyfry leżą poniżej wszystkich liter, spacja (32) poniżej każdego znaku drukowalnego, a pusty wiersz jeszcze niżej, więc sortowanie rosnące zbiera puste wiersze i wiersze zaczynające się od spacji na samej górze, a sortowanie malejące na samym dole.

Odstępy na końcu wiersza są niewidzialną wersją tego samego problemu: apple i apple sortują się obok siebie i wyglądają jak duplikat, który nie chce dać się usunąć. Spacja niełamliwa (U+00A0) jest jeszcze gorsza, bo rysuje się identycznie jak zwykła, a sortuje się powyżej każdej litery, podobnie jak powrót karetki pozostawiony po podzieleniu pliku windowsowego wyłącznie po znaku nowego wiersza. Jeśli dwa wiersze wyglądają identycznie i nadal nie chcą się zwinąć, poszukaj ukrytych znaków.

Ta sama lista w dwóch krajach sortuje się inaczej

Porządek punktów kodowych stawia też każdy znak z diakrytyką za każdym znakiem bez niej. Zürich sortuje się po Zzz, a Ärger po zebra. Żaden język nie porządkuje własnego alfabetu w ten sposób. Porównywanie świadome ustawień regionalnych stosuje zamiast tego reguły językowe, a te reguły są ze sobą niezgodne.

W JavaScript mieszka to w 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

Ten sam obiekt obejmuje wcześniejsze problemy. { numeric: true } porównuje ciągi cyfr jako liczby, co daje porządek naturalny, a sensitivity ustala, co liczy się jako różnica: "base" ignoruje wielkość liter i znaki diakrytyczne, "accent" ignoruje wyłącznie wielkość liter, "case" ignoruje wyłącznie znaki diakrytyczne. Pominięcie ustawień regionalnych powoduje użycie tych, na jakie ustawiona jest maszyna, i tak właśnie ten sam kod zwraca dwa różne porządki na dwóch laptopach. Kiedy wynik musi być wszędzie taki sam, wskaż ustawienia regionalne wprost.

Które duplikaty liczą się jako duplikaty

Usuwanie duplikatów jest zdefiniowane dokładnie tak dobrze jak test równości, który za nim stoi. Weź pięć wierszy, z których każdy wyświetla się jako słowo cafe z akcentem ostrym:

Cztery rozsądne reguły dają cztery różne odpowiedzi:

Żadna z nich nie jest błędna; odpowiadają na różne pytania. Normalizacja ma większe znaczenie, niż się wydaje, ponieważ tekst z nazw plików w macOS przychodzi zwykle w postaci rozłożonej (NFD), a tekst z Windows i z formularzy webowych w postaci złożonej (NFC), więc lista wklejona z dwóch źródeł zbiera niewidzialne bliźniaki. NFKC idzie dalej i składa znaki zgodnościowe, takie jak ligatura fi, do ich zwykłych odpowiedników.

Umownie wygrywa pierwsze wystąpienie, więc jeśli niechlujna kopia została wklejona pierwsza, to ona przetrwa. Usuwanie duplikatów jest też innym żądaniem niż znajdowanie elementów unikalnych: usuwanie zduplikowanych wierszy zostawia po jednym z każdego, natomiast zbiór unikalny w narzędziu do liczenia częstości jest mniejszą grupą elementów występujących dokładnie raz.

Stabilność i sortowanie po dwóch kluczach

Sortowanie stabilne gwarantuje, że wpisy, które komparator uzna za równe, zachowają kolejność, jaką miały na wejściu. To właśnie sprawia, że sortowanie po wielu kluczach kolejnymi przebiegami w ogóle działa: sortuj najpierw po kluczu najmniej istotnym, a potem po najważniejszym. Sortowanie po nazwisku, a potem po dziale, daje działy w kolejności, a nazwiska uporządkowane wewnątrz każdego z nich. Sortowanie niestabilne cofa pierwszy przebieg w trakcie drugiego, a wynik wygląda prawie dobrze, co jest gorsze niż wyglądanie źle.

Odwracanie niesie ten sam haczyk, ponieważ przewrócenie posortowanej listy odwraca też każdą grupę o równych kluczach. Odwracania listy używaj wtedy, gdy chcesz przewrócić cały porządek, a nie jako skrótu do sortowania malejącego.

Implementacje się różnią. Array.prototype.sort w JavaScript musi być stabilne dopiero od ES2019; wcześniej V8 stosowało niestabilne quicksort powyżej pewnego rozmiaru tablicy, więc ten sam kod zachowywał się inaczej przy dziesięciu i przy dziesięciu tysiącach elementów. sorted w Pythonie jest stabilne, a GNU sort nie jest, chyba że podasz -s.

Tasowanie nie jest rodzajem sortowania

Jednolinijkowe tasowanie, list.sort(() => Math.random() - 0.5), jest obciążone. Sortowanie zakłada, że komparator opisuje spójny porządek, i pyta tylko o ten podzbiór par, którego potrzebuje jego algorytm. Komparator, który przy każdym wywołaniu losuje nową liczbę, łamie to założenie, więc wynik zależy od algorytmu i od długości tablicy: elementy mają skłonność do pozostawania blisko miejsca, w którym startowały, a niektóre permutacje pojawiają się znacznie częściej niż inne.

Poprawne tasowanie korzysta z algorytmu Fishera i Yatesa, idąc od końca i zamieniając każdy element z elementem wylosowanym jednostajnie spośród tych na jego pozycji albo wcześniej:

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

Częsty zepsuty wariant używa wewnątrz pętli Math.random() * list.length, losując za każdym razem z całej tablicy. Daje to n do potęgi n jednakowo prawdopodobnych ciągów losowań, co nie dzieli się równo przez n silnia możliwych porządków, więc niektóre porządki wypadają częściej.

Losowość i sortowanie da się poprawnie połączyć, nadając każdemu elementowi z góry jeden losowy klucz i sortując po tym kluczu, ponieważ komparator pozostaje wtedy spójny. Błędem jest rzucanie kostką wewnątrz porównania.

Kolejność, w jakiej idą kroki

Większość problemów z listami bierze się z wykonywania właściwych operacji w niewłaściwej kolejności.

1. Najpierw rozpakuj. Lista skopiowana z kodu przychodzi jako "apple",; cudzysłowy i przecinek są częścią ciągu znaków, więc nigdy nie dopasuje się do apple. Rozpakowywanie elementów listy je usuwa.
2. Przytnij i znormalizuj, żeby równość znaczyła to, co ci się wydaje, że znaczy.
3. Usuń duplikaty, z regułą dopasowania wybraną świadomie, a nie przyjętą jako domyślna.
4. Posortuj. Sortowanie wierszy obejmuje porządek tekstowy, liczbowy, według długości i losowy; przy danych z diakrytyką dodaj ustawienia regionalne.
5. Przekształcaj kształt na końcu. Grupowanie elementów listy tnie wynik na paczki o stałym rozmiarze pod limit na żądanie, a obracanie listy przesuwa wszystko wzdłuż, nie zmieniając porządku wewnętrznego.

Usuwanie duplikatów przed przycięciem zostawia prawie duplikaty, a sortowanie przed usunięciem duplikatów sortuje jedynie wiersze, które i tak zaraz zostaną wyrzucone.