Pradžia RIKIAVIMAS PRO

Teksto eilučių rikiavimas pagal abėcėlę (A–Ž / Ž–A)

Rikiuokite sąrašus ir žurnalus pagal abėcėlę (A–Ž arba Ž–A) su žmogui įprasta skaičių tvarka („Skyrius 2“ prieš „Skyrius 10“), pagal eilučių ilgį, el. pašto domenus, bibliografinį artikelių ignoravimą bei CSPRNG maišymą.

⚡ Pasirinkite rikiavimo algoritmą ir kriterijų (8 režimai):
Įvestis ➔ Surikiuota
7 ➔ 7
266 chars total
Pašalinta (dublikatai/tuščios)
0 removed
Dublikatai ir tuščios eilutės
Eilučių ilgio intervalas
23 – 50 chars
Trumpiausia ir ilgiausia eilutė
Rikiavimo variklis ir trukmė
Timsort < 1 ms
Intl.Collator (numeric: true)
A → Z (Natural Sort)

ASCII kodų rikiavimo ir Intl.Collator natūralaus alfanumerinio rikiavimo palyginimo matrica

Tiesioginis palyginimas, parodantis, kuo primityvus baitų rikiavimas skiriasi nuo Unicode rikiavimo algoritmo (UTS #10) natūralios tvarkos:

Duomenų rinkinio iššūkis Primityvus ASCII .sort() rezultatas Intl.Collator natūralus rezultatas Algoritminis mechanizmas
Numbered Files
file2, file10, file1, file100
file1, file10, file100, file2 ❌ file1, file2, file10, file100 ✅ numeric: true multi-digit token integer comparison
Mixed Case Words
apple, Zebra, banana, Apricot
Apricot, Zebra, apple, banana ❌ apple, Apricot, banana, Zebra ✅ Case-folding primary weight comparison before tertiary case
European Diacritics
Ąžuolas, Burė, Čiobrelis, Briedis
Burė, Briedis, Ąžuolas, Čiobrelis ❌ Ąžuolas, Briedis, Burė, Čiobrelis ✅ Unicode CLDR locale tailoring (lt, es, tr)
Bibliographic Titles
The Matrix, Avatar, A Bug's Life
A Bug's Life, Avatar, The Matrix Avatar, A Bug's Life, The Matrix ✅ Leading article stripping key (/^(the|a|an)\s+/i)

Natūralus alfanumerinis ir daugiakriterinis teksto eilučių rikiuoklis – tai pramoninio lygio leksinio rikiavimo variklis, sukurtas programuotojams, bibliotekininkams, duomenų analitikams ir sistemų administratoriams. Kol paprasti naršyklės skriptai remiasi primityviu ASCII baitų palyginimu (pastatydami „Skyrius 10“ prieš „Skyrius 2“, o lietuvišką „Ąžuolą“ nustumdami į sąrašo galą po „Z“), mūsų darbo stotis naudoja ECMAScript Intl.Collator API (Unicode standartą UTS #10) kartu su V8 variklio O(n log n) Timsort algoritmu, bibliografiniu artikelių filtravimu, el. pašto domenų grupavimu bei kriptografiškai saugiu Fisher–Yates maišymu.

Kaip veikia Intl.Collator natūralaus rikiavimo variklis

Rikiuojant realius failų pavadinimų sąrašus, literatūros šaltinius, klientų el. pašto adresus ar serverio konfigūracijos eilutes, nepakanka lyginti plikus simbolių kodus. Mūsų variklis vykdo penkių etapų Švarco transformacijos (angl. Schwarzian Transform: Decorate–Sort–Undecorate) konvejerį tiesiogiai jūsų naršyklės RAM atmintyje:

  • 1 etapas – Pirminė higiena ir $O(n)$ deduplikavimas: Pasirinktinis valymas pašalina nematomus tarpus eilutės pradžioje ir gale bei išmeta tuščias eilutes. Įjungus dublikatų šalinimą, atminties `Set` struktūra akimirksniu pašalina pasikartojančius įrašus dar prieš pradedant rikiavimą.
  • 2 etapas – Palyginimo raktų dekoravimas: Kiekvienai eilutei priskiriamas lengvas palyginimo raktas. Jei pažymėtas filtras Ignoruoti pradžios „A / An / The“, artikeliai pašalinami tik iš palyginimo rakto, o pačioje eilutėje išlieka nepakeisti. El. pašto / Domeno režime raktas sukeičia `vartotojas@domenas` į `domenas vartotojas`.
  • 3 etapas – Daugiapakopis Unicode lyginimas (`UTS #10`): Variklis sukuria `new Intl.Collator(locale, { numeric: true, sensitivity })` objektą, kuris lygina eilutes pagal pirminius abėcėlės svorius, antrinius diakritinius ženklus ir pilnus skaitmenų blokus.
  • 4 etapas – Stabilus O(n log n) Timsort vykdymas: Dekoruotas masyvas surikiuojamas stabiliu hibridiniu algoritmu, kuris išsaugo pradinę vienodą raktą turinčių eilučių tvarką.
  • 5 etapas – Projekcija ir eilučių numeravimas: Išgautos eilutės grąžinamos į išvesties langą ir pasirinktinai sunumeruojamos `1. 2. 3.` prefiksais.

Kodėl primityvus ASCII Array.prototype.sort() klysta su skaičiais ir lietuviškomis raidėmis

JavaScript kalboje iškvietus `array.sort()` be specialaus lygintuvo, elementai lyginami pagal UTF-16 kodo vienetus iš kairės į dešinę. Tai sukelia tris rimtas duomenų apdorojimo klaidas:

  1. Leksikografinė skaičių klaida (`„10“ < „2“`): Lyginant `„Failas 10“` ir `„Failas 2“`, paprastas ASCII rikiuoklis po vienodos pradžios palygina simbolį `'1'` (kodas `49`) su simboliu `'2'` (kodas `50`). Kadangi $49 < 50$, `„Failas 10“` ir `„Failas 100“` pastatomi prieš `„Failas 2“`. Mūsų Natūralus rikiavimas (`numeric: true`) skaitmenų seką traktuoja kaip sveikąjį skaičių ($2 < 10 < 100$).
  2. Didžiųjų ir mažųjų raidžių atskirtis (`„Z“ < „a“`): 1963 m. ASCII lentelėje visos didžiosios raidės (`A–Z`, kodai `65–90`) eina prieš mažąsias (`a–z`, kodai `97–122`), todėl `„Zebras“` atsiduria prieš `„abrikosą“`.
  3. Diakritinių raidžių ištrėmimas (`„Ą“ > „Z“`): Lietuviškos raidės `Ą, Č, Ę, Ė, Į, Š, Ų, Ū, Ž` turi Unicode kodus virš `256`, todėl primityvus rikiuoklis žodį `„Ąžuolas“` numeta į patį sąrašo dugną po `Z`. Pasirinkus lietuvių (`lt`) lokalę, `Ą` rikiuojama iškart prie `A`, `Č` – po `C`, o `Ž` – po `Z`.

Timsort (O(n log n)) ir Unicode rikiavimo algoritmas (UCA UTS #10)

2002 m. Timo Peterso sukurtas Timsort algoritmas šiandien yra standartinis V8 (Chrome / Node.js) ir SpiderMonkey (Firefox) rikiavimo variklis. Skirtingai nuo kvadratinio O(n2) laiko „Bubble Sort“, Timsort atpažįsta jau iš dalies surikiuotas sekas ir apjungia jas per: LaikasGeriausias(n) = Ω(n),    LaikasVidutinis / Blogiausias(n) = O(n log2 n) Rikiuojant 50 000 eilučių sąrašą, atliekama tik ~780 000 palyginimų, todėl operacija trunka mažiau nei 35 milisekundes. O pasirinkus **CSPRNG atsitiktinio išmaišymo** režimą, naudojamas kriptografiškai nešališkas **Durstenfeld / Fisher–Yates $O(n)$ algoritmas** su `window.crypto.getRandomValues` aparatine entropija.

Bibliografinis artikelių ignoravimas ir el. pašto domenų grupavimas

Du specializuoti režimai ypač praverčia leidėjams bei IT inžinieriams:

  • Bibliografinis katalogavimas (`Ignoruoti „A / An / The“`): Rikiuojant angliškų knygų, filmų ar straipsnių pavadinimus, šis filtras palyginimo metu praleidžia pradžios artikelius, todėl „The Architecture of UNIX“ rikiuojamas pagal raidę **A**, tačiau galutiniame sąraše išlieka su pilnu pavadinimu.
  • El. pašto ir DNS domenų grupavimas (`@/\.`): Analizuojant prenumeratorių sąrašus ar serverių žurnalus, šis režimas pirmiausia rikiuoja pagal domeno vardą po `@` ženklo, todėl visi tos pačios įmonės ar el. pašto tiekėjo adresai sugrupuojami vienas šalia kito.

Dažniausiai užduodami klausimai (DUK)

Kodėl paprasti rikiavimo įrankiai „Item 10“ ir „Item 100“ pastato prieš „Item 2“?

Paprasti įrankiai lygina tekstą po vieną simbolį pagal ASCII kodų lentelę. Kadangi simbolis "1" (ASCII 49) yra mažesnis už "2" (ASCII 50), "Item 10" atsiduria prieš "Item 2". Mūsų variklis naudoja ECMAScript Intl.Collator su parametru { numeric: true }, kuris skaitmenų sekas atpažįsta kaip pilnus skaičius, todėl "Item 2" visada rikiuojamas prieš "Item 10".

Kaip veikia bibliografinis filtras „Ignoruoti pradžios A / An / The“?

Bibliotekininkystėje, knygų rodyklėse ir filmų kataloguose rikiuojant pavadinimus su artikeliais tūkstančiai įrašų susigrūda po raidėmis „T“ („The...“) arba „A“. Įjungus šį filtrą, palyginimo raktas laikinai atmeta pradžios artikelį, bet galutiniame sąraše išsaugo pilną pavadinimą – todėl „The Godfather“ rikiuojamas prie raidės G.

Kodėl rikiuojant pagal abėcėlę svarbu pasirinkti kalbos lokalę (EN, LT, ES, TR)?

Standartinis ASCII rikiavimas visas didžiąsias raides (A–Z, kodai 65–90) pastato prieš mažąsias (a–z, kodai 97–122), o diakritines raides (lietuviškas ą, č, ę, ė, į, š, ų, ū, ž, ispanišką ñ ar turkiškas ç, ğ, ö, ş, ü) nustumia į patį sąrašo galą po Z. Pasirinkus kalbos lokalę, taikomas Unicode rikiavimo algoritmas (UTS #10), užtikrinantis tikslią žodyno tvarką.

Ką daro „El. pašto / Domeno galūnės“ rikiavimo režimas?

Rikiuojant el. pašto sąrašus įprastu A–Ž būdu, adresai grupuojami pagal vartotojo vardą prieš "@" ženklą. Mūsų Domeno režimas išskiria ir pirmiausia lygina domeno dalį po "@" (arba apverčia subdomenų hierarchiją), todėl visi vienos įmonės ar serverio adresai sugrupuojami kartu.

Kaip greitai šis įrankis gali surikiuoti 50 000+ teksto eilučių?

Modernūs JavaScript varikliai (V8, SpiderMonkey, JavaScriptCore) naudoja Timsort – hibridinį stabilų rikiavimo algoritmą, sujungiantį „Merge Sort“ ir „Insertion Sort“ su O(n log n) laiko sudėtingumu. Kartu su iš anksto apskaičiuotais Švarco transformacijos raktais mūsų įrankis 50 000 eilučių naršyklės RAM atmintyje surikiuoja greičiau nei per 40 milisekundžių.