Celočíselné řazení

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 22. ledna 2021; kontroly vyžadují 2 úpravy .

Celočíselné třídění je  úkolem seřadit nějakou sadu hodnot pomocí celočíselných klíčů. Algoritmy třídění celých čísel lze také použít pro problémy, kde klíče jsou čísla s plovoucí desetinnou čárkou nebo textové řetězce [1] . Schopnost provádět celočíselné aritmetické operace s klíči umožňuje, aby algoritmy třídění celých čísel byly v mnoha případech rychlejší než podobné třídicí algoritmy využívající srovnání, v závislosti na operacích povolených ve výpočetním modelu a velikosti čísel klíčů.

Obvyklé celočíselné třídicí algoritmy: košový sort , radix sort , počítání sort jsou široce používané a efektivní [2] [3] . Další výzkum celočíselných třídicích algoritmů se zaměřil na teoretická vylepšení nejhorších případů a získané algoritmy nejsou považovány za efektivní na moderních 64bitových počítačích, ačkoli experimenty ukázaly, že některé z těchto metod mohou být lepší než bitové třídění dat. se 128 nebo více bity .na klíči [4] . Pro velké datové sady je omezením téměř náhodný přístup do paměti u celočíselných třídicích algoritmů, zejména ve srovnání s jinými třídicími algoritmy, které byly navrženy s ohledem na hierarchickou paměťovou strukturu .

Celočíselné řazení se používá v jednom ze šesti benchmarků v sadě DARPA High Productivity Computing Systems Discrete Mathematics a v jednom z jedenácti kritérií v sadě NAS Parallel Benchmarks [5] .

Výpočtové modely

Časová omezení celočíselných třídicích algoritmů obvykle závisí na třech parametrech:  - počtu datových hodnot, které mají být tříděny,  - řádové velikosti největšího možného klíče a  - počtu bitů ve strojovém slově počítače na který bude algoritmus proveden. Obecně se předpokládá , že strojová slova jsou dostatečně velká, aby reprezentovala jak index ve vstupní sekvenci, tak klíč [6] .

Algoritmy celočíselného řazení jsou obecně navrženy tak, aby fungovaly buď pro ukazovací strojnebo pro počítač s náhodným přístupem do paměti . Hlavní rozdíl mezi těmito modely spočívá v tom, že stroje s náhodným přístupem vám umožňují používat libovolnou hodnotu v registru jako adresu paměti při operacích čtení a zápisu s hodnotou jednotky času a organizovat složité manipulace s daty pomocí vyhledávací tabulky . Model ukazatelového stroje umožňuje přístup k paměti pouze prostřednictvím ukazatelů, které nelze manipulovat aritmetickými operacemi. V obou modelech lze bitové operace provádět zpravidla v jednom časovém řezu . Různé celočíselné třídicí algoritmy vytvářejí různé předpoklady o tom, zda lze celočíselné násobení provést v jednom časovém řezu [6] [7] . Lze také zvážit specializovanější modely počítání, jako jsou paralelní stroje s náhodným přístupem [8] [9] [10] [11] [12] .

V roce 1999 se ukázalo, že v některých případech může být násobení nebo vyhledávání v tabulce požadované pro některé celočíselné třídicí algoritmy nahrazeno specializovanými operacemi, které lze snadno implementovat v hardwaru, ale nejsou běžně dostupné na počítačích pro všeobecné použití [7] .

Poznámky

  1. ↑ Han, Thorup, 2002 .
  2. ↑ McIlroy, Bostic, McIlroy, 1993 .
  3. ↑ Andersson, Nilsson, 1998 .
  4. ↑ Rahman, Raman, 1998 .
  5. ↑ DARPA HPCS Discrete Mathematics Benchmarks Archivováno 10. března 2016 na Wayback Machine , Duncan A. Buell, University of South Carolina, získáno 20. 4. 2011.
  6. ↑ 1 2 Fredman, Willard, 1993 .
  7. ↑ 1 2 Andersson, Miltersen, Thorup, 1999 .
  8. ↑ Reif, 1985 .
  9. ↑ Cole, Vishkin, 1986 , Komentář.
  10. ↑ Hagerup, 1987 .
  11. ↑ Bhatt a kol., 1991 .
  12. ↑ Albers, Hagerup, 1997 .

Literatura