Třídící síť - Sorting network

Jednoduchá třídicí síť skládající se ze čtyř vodičů a pěti konektorů

v počítačová věda, srovnávací sítě jsou abstraktní zařízení vytvořená z pevného počtu „vodičů“, nosných hodnot a komparačních modulů, které spojují páry vodičů, a vyměňují hodnoty na vodičích, pokud nejsou v požadovaném pořadí. Tyto sítě jsou obvykle navrženy tak, aby fungovaly třídění na pevném počtu hodnot, v takovém případě jsou vyvolány třídění sítí.

Třídění sítí se liší od obecných druhy porovnání v tom, že nejsou schopni zpracovat libovolně velké vstupy, a v tom, že jejich posloupnost srovnání je nastavena předem, bez ohledu na výsledek předchozích srovnání. Aby bylo možné třídit větší množství vstupů, musí být vybudovány nové třídicí sítě. Tato nezávislost porovnávacích sekvencí je užitečná pro paralelní provádění a pro implementaci v Hardware. I přes jednoduchost třídících sítí je jejich teorie překvapivě hluboká a složitá. Třídění sítí byly poprvé studovány kolem roku 1954 Armstrongem, Nelsonem a O'Connorem,[1] který si tento nápad následně patentoval.[2]

Třídicí sítě lze implementovat buď v Hardware nebo v software. Donald Knuth popisuje, jak lze komparátory pro binární celá čísla implementovat jako jednoduchá třístavová elektronická zařízení.[1] Dávkovač, v roce 1968, navrhl jejich použití ke konstrukci přepínání sítí u počítačového hardwaru, přičemž je nutné nahradit oba autobusy a tím rychlejší, ale dražší, příčné spínače.[3] Od roku 2000 jsou třídicí sítě (zejména bitonic mergesort ) jsou používány GPGPU komunita pro konstrukci třídicích algoritmů, na kterých bude běžet jednotky grafického zpracování.[4]

Úvod

Demonstrace komparátoru v třídicí síti.

Třídicí síť se skládá ze dvou typů položek: komparátorů a drátů. Dráty jsou považovány za běžící zleva doprava, nesoucí hodnoty (jedna na vodič), které procházejí sítí současně. Každý komparátor spojuje dva vodiče. Když se dvojice hodnot při procházení dvojicí vodičů setká s komparátorem, komparátor hodnoty zamění kdyby a jen kdyby hodnota horního drátu je větší nebo rovna hodnotě spodního drátu.

Ve vzorci, pokud nese horní drát X a spodní vodič nese y, poté po nárazu na komparátor dráty nesou a , takže dvojice hodnot je tříděna.[5]:635 Síť vodičů a komparátorů, které správně seřadí všechny možné vstupy do vzestupného pořadí, se nazývá třídicí síť nebo rozbočovač Kruskal. Odrazem sítě je také možné třídit všechny vstupy do sestupného pořadí.

Úplný provoz jednoduché třídicí sítě je uveden níže. Je zřejmé, proč tato třídicí síť správně seřadí vstupy; všimněte si, že první čtyři komparátory „potopí“ největší hodnotu dolů a „plovou“ nejmenší hodnotu nahoru. Konečný komparátor třídí prostřední dva dráty.

SimpleSortingNetworkFullOperation.svg

Hloubka a účinnost

Účinnost třídicí sítě lze měřit podle její celkové velikosti, což znamená počet komparátorů v síti, nebo podle její hloubka, definovaný (neformálně) jako největší počet komparátorů, se kterými se může každá vstupní hodnota setkat na své cestě sítí. Bereme na vědomí, že třídicí sítě mohou provádět určitá srovnání paralelně (představovaný v grafickém zápisu komparátory, které leží na stejné svislé čáře) a za předpokladu, že všechna srovnání zabere jednotkový čas, je vidět, že hloubka sítě se rovná počtu časových kroků potřebných k jejímu provedení.[5]:636–637

Vkládací a bublinkové sítě

Můžeme snadno postavit síť jakékoli velikosti rekurzivně pomocí principů vkládání a výběru. Za předpokladu, že máme třídicí síť velikosti n, můžeme postavit síť velikosti n + 1 "vložením" dalšího čísla do již seřazené podsítě (podle principu za) třídění vložení ). Stejné věci můžeme dosáhnout také tak, že nejprve „vybereme“ nejnižší hodnotu ze vstupů a poté rekurzivně setřídíme zbývající hodnoty (pomocí principu třídění bublin ).

Třídicí síť vytvořená rekurzivně, která nejprve potopí největší hodnotu na dno a poté roztřídí zbývající vodiče. Na základě třídění bublin
Třídicí síť vytvořená rekurzivně, která nejprve seřadí prvních n vodičů a poté vloží zbývající hodnotu. Na základě třídění vložení

Struktura těchto dvou třídících sítí je velmi podobná. Konstrukce dvou různých variant, která sbalí dohromady komparátory, které lze provést současně, ukazuje, že jsou ve skutečnosti identické.[1]

Síť třídění bublin
Síť pro třídění vkládání
Při povolení paralelních komparátorů jsou třídění bublin a třídění vkládání identické

Vkládací síť (nebo ekvivalentně bublinová síť) má hloubku 2n - 3[1], kde n je počet hodnot. To je lepší než Ó(n log n) čas potřebný do stroje s náhodným přístupem, ale ukazuje se, že existují mnohem efektivnější třídicí sítě s hloubkou spravedlnosti Ó(log2 n), jak je popsáno níže.

Princip nuly

I když je snadné prokázat platnost některých třídicích sítí (jako je vkládací / třídič bublin), není to vždy tak snadné. Existují n! obměny čísel v n- drátová síť a otestovat všechny z nich by zabralo značné množství času, zvláště když n je velký. Počet testovacích případů lze výrazně snížit na 2npomocí takzvaného principu nula jedna. I když je stále exponenciální, je menší než n! pro všechny n ≥ 4a rozdíl roste poměrně rychle s rostoucím n.

Princip nuly jedna uvádí, že pokud třídicí síť dokáže správně třídit všechny 2n posloupnosti nul a jedniček, pak platí i pro libovolně seřazené vstupy. To nejen drasticky snižuje počet testů potřebných k ověření platnosti sítě, ale je také velmi užitečné při vytváření mnoha konstrukcí třídících sítí.

Princip lze dokázat nejprve pozorováním následujícího faktu o komparátorech: když a monotónně roste funkce F se aplikuje na vstupy, tj. X a y jsou nahrazeny F(X) a F(y), pak produkuje komparátor min (F(X), F(y)) = F(min (X, y)) a max (F(X), F(y)) = F(max (X, y)). Podle indukce v hloubce sítě lze tento výsledek rozšířit na a lemma s tím, že pokud síť transformuje sekvenci A1, ..., An do b1, ..., bn, transformuje se F(A1), ..., F(An) do F(b1), ..., F(bn). Předpokládejme, že nějaký vstup A1, ..., An obsahuje dvě položky Ai < Aja síť je nesprávně zamění ve výstupu. Pak se také nesprávně seřadí F(A1), ..., F(An) pro funkci

Tato funkce je monotónní, takže máme princip nuly jedna jako kontrapozitivní.[5]:640–641

Vytváření třídících sítí

Pro konstrukci třídicích sítí hloubky existují různé algoritmy Ó(log2 n) (proto velikost Ó(n log2 n)) jako Dávkové liché – sudé sloučení, bitonické třídění, Třídění skořápky a Síť pro párové párování. Tyto sítě se v praxi často používají.

Je také možné budovat sítě hloubky Ó(log n) (proto velikost Ó(n log n)) pomocí konstrukce zvané Síť AKS, po jeho objevitelích Ajtai, Komlós, a Szemerédi.[6] I když je to důležitý teoretický objev, síť AKS má velmi omezené praktické použití z důvodu velké lineární konstanty skryté v Big-O notace.[5]:653 To je částečně způsobeno výstavbou expandér graf.

Zjednodušenou verzi sítě AKS popsal Paterson v roce 1990, který poznamenal, že „konstanty získané pro vázanou hloubku stále brání tomu, aby stavba měla praktickou hodnotu“.[7]

Novější stavba s názvem cik-cak třídicí síť velikosti Ó(n log n) byl objeven uživatelem Goodrich v roce 2014.[8] I když je jeho velikost mnohem menší než u sítí AKS, jeho hloubka Ó(n log n) je nevhodný pro paralelní implementaci.

Optimální třídicí sítě

Pro malý, pevný počet vstupů n, optimální Mohou být konstruovány třídicí sítě s minimální hloubkou (pro maximální paralelní provedení) nebo minimální velikostí (počet komparátorů). Tyto sítě lze použít ke zvýšení výkonu větších třídicích sítí vyplývajících z rekurzivní konstrukce, např. Batcher, zastavením předčasné rekurze a vložením optimálních sítí jako základních případů.[9] Následující tabulka shrnuje výsledky optimality pro malé sítě, pro které je známá optimální hloubka:

n1234567891011121314151617
Hloubka[10]013355667788999910
Velikost, horní mez[11]01359121619252935394551566071
Velikost, spodní mez (pokud se liší)[12]4347515560

U větších sítí není v současné době známa optimální hloubka ani optimální velikost. Hranice dosud známé jsou uvedeny v následující tabulce:

n181920212223242526272829303132
Hloubka, horní mez[10][13][14]111111121212121313141414141414
Hloubka, dolní mez[10]101010101010101010101010101010
Velikost, horní mez[14]778591100107115120132139150155165172180185
Velikost, spodní mez[12]65707580859095100105110115120125130135


Prvních šestnáct hloubkově optimálních sítí je uvedeno v Knuthově Umění počítačového programování,[1] a jsou od vydání z roku 1973; nicméně, zatímco optimálnost prvních osmi byla stanovena Floyd a Knuth v šedesátých letech, tato vlastnost nebyla prokázána pro posledních šest až do roku 2014[15] (o případech devět a deset bylo rozhodnuto v roce 1991[9]).

Pro jeden až jedenáct vstupů jsou známé minimální (tj. Velikostně optimální) třídicí sítě a pro vyšší hodnoty nižší hranice jejich velikostí S(n) lze odvodit indukčně pomocí lematu kvůli Van Voorhisovi[1] (str. 240): S(n) ≥ S(n - 1) + ⌈log2n⌉. Prvních deset optimálních sítí je známo od roku 1969, přičemž prvních osm je opět známých jako optimální od práce Floyda a Knutha, ale optimálnost případů n = 9 a n = 10 vyřešení trvalo do roku 2014.[11]Optimální síť pro velikost 11 našel v prosinci 2019 Jannis Harder, který také spodní hranici 12 přizpůsobil její horní hranici.[16]

Některé práce při navrhování optimální třídicí sítě byly provedeny pomocí genetické algoritmy: D. Knuth uvádí, že nejmenší známá třídicí síť pro n = 13 byl nalezen Hugues Juillé v roce 1995 „simulací evolučního procesu genetického šlechtění“[1] (str. 226), a že minimální hloubka třídění sítí pro n = 9 a n = 11 byly nalezeny Loren Schwiebertovou v roce 2001 „pomocí genetických metod“[1] (str. 229).

Složitost testování třídicích sítí

Je nepravděpodobné, že lze provést další významná vylepšení pro testování obecných třídicích sítí, pokud P = NP, protože je známo, že problém testování, zda je kandidátská síť třídicí sítí co-NP -kompletní.[17]

Reference

  1. ^ A b C d E F G h Knuth, D. E. (1997). The Art of Computer Programming, Volume 3: Sorting and Searching (Druhé vydání.). Addison – Wesley. 219–247. ISBN  978-0-201-89685-5. Oddíl 5.3.4: Sítě pro třídění.
  2. ^ USA 3029413, O'Connor, Daniel G. & Raymond J. Nelson, "Systém třídění s n-line sorting switch “, publikováno 10. dubna 1962 
  3. ^ Batcher, K. E. (1968). Třídění sítí a jejich aplikací. Proc. AFIPS Jarní společná počítačová konference. 307–314.
  4. ^ Owens, J. D .; Houston, M .; Luebke, D .; Green, S .; Stone, J. E .; Phillips, J. C. (2008). "Výpočet GPU". Sborník IEEE. 96 (5): 879–899. doi:10.1109 / JPROC.2008.917757.
  5. ^ A b C d Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. (1990). Úvod do algoritmů (1. vyd.). MIT Press a McGraw-Hill. ISBN  0-262-03141-8.
  6. ^ Ajtai, M.; Komlós, J.; Szemerédi, E. (1983). An O (n log n) třídicí síť. STOC '83. Sborník z patnáctého ročníku sympozia ACM o teorii práce s počítačem. s. 1–9. doi:10.1145/800061.808726. ISBN  0-89791-099-0.
  7. ^ Paterson, M. S. (1990). "Vylepšené třídění sítí s Ó(log N) hloubka". Algorithmica. 5 (1–4): 75–92. doi:10.1007 / BF01840378.
  8. ^ Goodrich, Michael (Březen 2014). Cik-cak řazení: Jednoduchý deterministický algoritmus řazení dat, který nezapomíná na čas O (n log n). Sborník 46. výročního sympozia ACM o teorii práce s počítači - STOC '14. str. 684–693. arXiv:1403.2777. doi:10.1145/2591796.2591830. ISBN  9781450327107.
  9. ^ A b Parberry, Ian (1991). „Počítačem podporovaná optimální hloubka spodní hranice pro sítě třídění s devíti vstupy“ (PDF). Teorie matematických systémů. 24: 101–116. CiteSeerX  10.1.1.712.219. doi:10.1007 / bf02090393.
  10. ^ A b C Codish, Michael; Cruz-Filipe, Luís; Ehlers, Thorsten; Müller, Mike; Schneider-Kamp, Peter (2015). Třídění sítí: na konec a zpět. arXiv:1507.01428. Bibcode:2015arXiv150701428C.
  11. ^ A b Codish, Michael; Cruz-Filipe, Luís; Frank, Michael; Schneider-Kamp, Peter (2014). Dvacet pět komparátorů je optimální při třídění devíti vstupů (a dvacet devět za deset). Proc. Mezinárodní konf. Nástroje s AI (ICTAI). 186–193. arXiv:1405.5754. Bibcode:2014arXiv1405,5754C.
  12. ^ A b Získané Van Voorhis lemmatem a hodnotou S(11) = 35
  13. ^ Ehlers, Thorsten (únor 2017). "Sloučením téměř seřazených sekvencí se získá 24 třídič". Dopisy o zpracování informací. 118. doi:10.1016 / j.ipl.2016.08.005.
  14. ^ A b Dobbelaere, Berte. "SorterHunter". GitHub. Citováno 4. července 2020.
  15. ^ Bundala, D .; Závodný, J. (2014). Optimální sítě pro třídění. Teorie a aplikace jazyků a automatů. Přednášky z informatiky. 8370. 236–247. arXiv:1310.6271. doi:10.1007/978-3-319-04921-2_19. ISBN  978-3-319-04920-5.
  16. ^ Těžší, Jannis. "sortnetopt". GitHub. Citováno 7. prosince 2019.
  17. ^ Parberry, Ian (1991). O výpočetní složitosti optimálního třídění ověření sítě. Proc. PARLE '91: Parallel Architectures and Languages ​​Europe, Volume I: Parallel Architectures and Algorithms, Eindhoven, Nizozemsko. str. 252–269.

externí odkazy