Řazení polem (ArraySort)6.5.2025

Využívá vytvořenou vlastnost počítačové paměti a to že je RAM sérií již seřazených škatulek. Kdo je všelijak přesvědčen že roboti a vůbec veškerá umělá idiocie prý napodobuje či simuluje člověka, tak je v pořádném bludu, neboť lidská paměť ani při velkém úletu není očividně ničím na způsob seřazených očíslovaných stejně velikých škatulí.

Pro seřazení celých čísel je potřeba vytvořit pouze dostatečně dlouhé pole a číslo je poté indexem v onom poli.

Například by byla tato čísla pro řazení: 5, 1, 3, 6, 10, 6, 3, 1, 3, 1, 1, 6.

Je-li známé nejnižší a nejvyší číslo, pak pole předvyplněné nulami má index od nejnižšího do nejvyšího, v tomto případě tedy od jedničky do desítky.

Řazení, odstraňování duplikátů a filtrování unikátů pak probíhá jedním příkazem: pole[číslo]++.

Po naplnění je v každém indexu počet daných čísel a pole stačí projít od začátku do konce a vypsat potřebné hodnoty.

Seřazená čísla jsou ty v nenulových buňkách a je tam udán jejich počet, vyjde tedy: 1, 1, 1, 1, 3, 3, 3, 5, 6, 6, 6, 10

Seřazená bez duplikátů jsou buňky s nenulovou hodnotou čili: 1, 3, 5, 6, 10.

Unikáty jsou jen ty které jsou jen jednou což splňují indexy: 5, 10.

Množství RAM

Metoda je velmi jednoduchá a čísla seřadí/deduplikuje/zjistíUnikáty během jediného jejich přečtení. Potřebuje však inicializovat vynulované pole a zde se otevírá pár dilemat ohledně množství RAMky které má uživatel k dispozici.

Pokud budou řazena čísla typu neznaménkový 4bajtový longint, jde o celá čísla od 0 do 4 294 967 296 a tolik musí být indexů v poli. Otázkou je jak velká čísla zvolit jako čítač v jednotlivých buňkách, byť to se dá stanovit podle počtu čísel, takže nebude-li řazeno více jak 65536 čísel, stačí jako čítač použít 2bajtový integer, což ale znamená 8GB RAM. Pro řazení třeba miliónu čísel už to chce longinty čili alespoň 16GB RAM – to však platí pokud se to dělá v jazyce který umožňuje v podstatě přímou adresaci paměti, což se různých interpretovaných asi moc týkat nebude. A taky by to chtělo mít těch 16GB rezervované paměti jako jeden nepřerušovaný blok, což může být problém pro operační systém když třeba v rámci různých priorit a utajování přiděluje programům bloky RAM náhodně.

V rámci skrblení RAMky může být tedy výhodnější dát jeden průběh navíc pro zjištění minimálního a maximálního indexu. A třeba zvážit jestli je čísel skutečně tak moc, že se kvůli tomu vyplatí zkoušet vydolovat třeba 16GB souvislé RAMky, neboť má-li být seřazeno třeba jen pár desítek čísel, tak nějaký QuickSort je může seřadit rychleji než proběhne iniciování vynulovaného pole.

Ona ta inicializace třeba 16GB pole vůbec nebude pomalá, ale dejme tomu že zabere třeba půl vteřiny. A má-li v programu dojít na to, že bude řazeno pár desítek čísel třeba desetkrát, pak by ty inicializace zabraly celkem 5 vteřin, kdežto 10 QuickSortů pro tak málo čísel by stále bylo na nějakých mikrosekundách.

Avšak pokud je čísel hodně, třeba i pár miliard v longintovém rozsahu → pak je to seřaditelné setsakra rychle když bude k dispozici 16GB souvislé RAM. Ale pro řazení 2bajtových integerů se lze vejít do 256kB RAMky (2^16=64kB × třeba 4bajty pro počty)! A pokud by šlo o velikost čísel do cca 16 miliónů (2^24), pak může stačit třeba 64MB RAM – což by neměl být problém takový souvislý blok RAM v operačním systému zarezervovat. Ale různé interpretry tu v podstatě přímou správu paměti neumožní (byť zdaleka neznám všechny).

Je tedy na programátorovi, zda lze v daných případech zrealizovat či se vyplatí používat toto řazení.

Skrblení RAMky při odstraňování duplikátů či filtrování unikátů

Pro duplikáty lze v buňkách pole použít typ boolean, čili něco jako pole[číslo]=true.

Anebo natvrdo využít jednotlivé bity v RAMce (bajt RAM pro 8 čísel) a nastavovat jim hodnotu 1 → což sice může zpočátku vypadat jako jakési přežité asemblerování, jenže pak je to 4GB děleno 8 čili 512MB RAM. A zkuste si nějakým tradičním řazením seřadit a odstranit duplikáty třeba z miliardy longintů, to se do 512MB RAM vejdete třeba tak že byste nějaxi swapovali na disku, což by vedlo k dalšímu výraznému zpomalení :-).

Pro unikáty to chce tři stavy, čili třeba jednobajtový byte s podmínkou např.:
IF pole[číslo] < 2 THEN pole[číslo]++

Anebo využít dvoubity v RAMce kdy bajt RAMky by byl pro čtyři čísla a potřeba RAM pro 4bajtové longinty 1GB.

Ale mohla by se zkusit i možnost nejprve zjistit která čísla vlastně v rozsahu jsou, k čemuž by pro 4bajtové stačilo zmiňovaných 512MB RAM, případně 1GB aby nebyly do výsledného výčtu zahrnuty unikáty. A TreeSortem pak spočítat výskyty již jen existujících čísel. Kolik by to však sebralo RAMky se nedá předem odhadnout, samozřejmě ale že v případě víceciferných čísel více.

Každopádně třeba céčkařům by se to mohlo zamlouvat, a asemblerysti by mohli blahem snad i zalevitovat – kor když ví jestli je na jejich procesoru rychlejší třeba právě instrukce jeMenší než třeba nerovnáSe :-).

Příliš velká čísla

Jak ale seřadit třeba nějaká 8 či 10bajtová numera? 2^64 je asi 18,4 exabajtů (snad exa-), pro 2^80 tu řádovou předponu ani neznám. Nicméně nad terabajty RAM se nedostávají snad ani dnešní superkeply. Tudíž by to chtělo nějak zlinearizovat, což by teoreticky šlo, ale v praxi jsem nic takového nepotřeboval a tudíž ani nezkoušel testovat. Takže skutečně jen teorie :-).

Ale šlo by třeba rozdělit ten 8bajtový numer na horních 16bitů, prostředních 16bitů a dolních 32bitů. A vytvořit 65536 adresářů pro horních 16 bitů, v každém z nich 65536 podadresářů pro prostředních 16 bitů a v každém z nich soubor s výsledným počtem čísel :-). Použitelné či třeba jen tupě nadšené? SSD jsou již v terabajtech, takže takto zlinearizované by to přeci mělo být utáhnutelné na jednom SSD, nebo snad ne? Ale na jakém FileSystému, že :-)? Je vůbec nějaký který by povolil všechny 16bitové znaky pro pojmenovávání souborů? Byť nějaké rychlé substituce do povolených znaků by byly řešitelné TreeSortem a kdyby se to bralo pouze po 12 či dokonce 8 bitech, RAMka pro TreeSort by šla značně dolů. Nicméně jak jsem uvedl, teorie kterou jsem nepotřeboval řešit. A jestli někdo z muslimů či muslimek potřebuje, může se ptát Aláha :-).

První nasazení

Poprvé jsem algoritmus použil v Poradně LibreOffice pro extrahování bloků z dokumentu podle číselných identifikátorů. Byla to např. řada čísel takto zadaná: 15, 22-35, 55-65 apod. A to již začal vznikat TreePacking.