Radix třídění - Radix sort - Wikipedia

Radix třídění
TřídaAlgoritmus řazení
Datová strukturaPole
Nejhorší případ výkon, kde w je počet bitů potřebných k uložení každého klíče.
Nejhorší případ složitost prostoru

v počítačová věda, radix sort je ne-srovnávací třídicí algoritmus. Vyhýbá se porovnávání vytvořením a rozdělující prvky do kbelíků podle jejich základ. Pro prvky s více než jedním významná číslice, tento proces bucketingu se opakuje pro každou číslici při zachování pořadí předchozího kroku, dokud nebudou brány v úvahu všechny číslice. Z tohoto důvodu, radix sort byl také povolán kbelík třídění a digitální třídění.

Radix sort lze použít na data, která lze třídit lexikograficky, ať už jsou to celá čísla, slova, děrné štítky, hrací karty nebo pošta.

Dějiny

Radixovo třídění sahá až do roku 1887 do práce Herman Hollerith na tabelační stroje.[1] Jako způsob třídění se běžně používaly třídicí algoritmy Radix děrné štítky již v roce 1923.[2]

První paměťově efektivní počítačový algoritmus byl vyvinut v roce 1954 na adrese MIT podle Harold H. Seward. Počítačové druhy radixů byly dříve odmítnuty jako nepraktické kvůli vnímané potřebě variabilní alokace kbelíků neznámé velikosti. Inovace společnosti Seward spočívala v použití lineárního skenování k určení požadovaných velikostí a odchylek lopaty předem, což umožnilo jediné statické přidělení pomocné paměti. Lineární skenování úzce souvisí s dalším Sewardovým algoritmem - počítání řazení.

V moderní době se radixové druhy nejčastěji používají u binárních sbírek struny a celá čísla. V některých srovnávacích testech se ukázalo, že je rychlejší než jiné obecnější algoritmy třídění, někdy 50% až třikrát rychlejší.[3][4][5]

An Třídič karet IBM provedení radixové řady na velké sadě děrné štítky. Karty jsou podávány do násypky pod bradou obsluhy a jsou tříděny do jednoho z 13 výstupních košů stroje na základě údajů děrovaných do jednoho sloupce na kartách. Klika poblíž vstupního zásobníku slouží k přesunu čtecí hlavy do dalšího sloupce, jak probíhá třídění. V poli vzadu jsou karty z předchozího třídicího pasu.

Pořadí číslic

Radixové druhy mohou být implementovány tak, aby začínaly na nejvýznamnější číslice (MSD) nebo nejméně významná číslice (LSD). Například s 1234, jeden by mohl začít s 1 (MSD) nebo 4 (LSD).

Řazení LSD radix obvykle používá následující pořadí řazení: krátké klávesy mají přednost před delšími klávesami a poté jsou tříděny klíče stejné délky lexikograficky. To se shoduje s normálním řádem celočíselných reprezentací, jako je sekvence [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]. Druhy LSD jsou obecně stabilní druhy.

Třídy MSD radix jsou nejvhodnější pro třídění řetězců nebo celočíselných reprezentací pevné délky. Sekvence jako [b, c, e, d, f, g, ba] bude tříděno jako [b, ba, c, d, e, f, g]. Pokud se k třídění celých čísel s proměnnou délkou v základně 10 použije lexikografické řazení, budou čísla od 1 do 10 vypsána jako [1, 10, 2, 3, 4, 5, 6, 7, 8, 9], jako by kratší klávesy byly zarovnány doleva a vyplněny vpravo prázdnými znaky, aby byly kratší klávesy stejně dlouhé jako nejdelší. Druhy MSD nemusí být nutně stabilní, pokud je nutné vždy zachovat původní pořadí duplicitních klíčů.

Kromě pořadí procházení se řazení MSD a LSD liší zpracováním vstupu s proměnnou délkou. Třídy LSD se mohou seskupovat podle délky, radix třídit každou skupinu a poté zřetězit skupiny v pořadí podle velikosti. Třídy MSD musí účinně „rozšířit“ všechny kratší klíče na velikost největšího klíče a podle toho je roztřídit, což může být komplikovanější než seskupení vyžadované LSD.

Druhy MSD jsou však vhodnější pro dělení a rekurzi. Každý segment vytvořený krokem MSD může být sám radix tříděn pomocí další nejvýznamnější číslice bez odkazu na další segmenty vytvořené v předchozím kroku. Jakmile je dosaženo poslední číslice, je k dokončení třídění zapotřebí pouze zřetězení segmentů.

Příklady

Nejméně významná číslice

Seznam vstupů (základ 10):

[170, 45, 75, 90, 2, 802, 2, 66]

Počínaje od pravé (poslední) číslice seřaďte čísla podle této číslice:

[{170, 90}, {02, 802, 02}, {45, 75}, {66}]
Všimněte si, že a 0 je připraveno pro dvě 2s, takže 802 udržuje své relativní pořadí jako v předchozím seznamu (tj. umístěné před druhou 2) na základě zásluh druhé číslice.

Řazení podle další levé číslice:

[{02, 802, 02}, {45}, {66}, {170, 75}, {90}]

A nakonec číslicí úplně vlevo:

[{002, 002, 045, 066, 075, 090}, {170}, {802}]

Každý krok vyžaduje pouze jeden průchod dat, protože každou položku lze umístit do jejího kbelíku bez porovnání s jakýmkoli jiným prvkem.

Některé implementace radixového řazení přidělují prostor kbelíkům tak, že nejprve spočítají počet klíčů, které patří do každého kbelíku, než klíče přesunou do těchto segmentů. Počet výskytů každé číslice je uložen v pole.

I když je vždy možné předem určit hranice segmentu pomocí počtů, některé implementace se rozhodnou místo toho použít dynamickou alokaci paměti.

Nejvýznamnější číslice, dopředu rekurzivní

Vstupní seznam, číselné řetězce s pevnou šířkou s úvodními nulami:

[170, 045, 075, 025, 002, 024, 802, 066]

První číslice se závorkami označujícími lopaty:

[{045, 075, 025, 002, 024, 066}, {170}, {802}]
Všimněte si, že 170 a 802 jsou již kompletní, protože jsou všechny, které zůstávají v jejich kbelích, takže není nutná žádná další rekurze

Další číslice:

[{ {002}, {025, 024}, {045}, {066}, {075} }, 170, 802]

Konečná číslice:

[ 002, { {024}, {025} }, 045, 066, 075 , 170, 802]

Zbývá jen zřetězení:

[002, 024, 025, 045, 066, 075, 170, 802]

Složitost a výkon

Radix sort působí v Ó (nw) čas, kde n je počet klíčů a w je délka klíče. Varianty LSD mohou dosáhnout dolní meze pro w „průměrná délka klíče“ při rozdělení klíčů s proměnnou délkou do skupin, jak je popsáno výše.

Optimalizované řazení radixů může být velmi rychlé, když pracujete v doméně, která jim vyhovuje.[6]Jsou omezeny na lexikografická data, ale pro mnoho praktických aplikací to není omezení. Velké velikosti kláves mohou bránit implementacím LSD, když se z indukovaného počtu průchodů stane překážka.[2]

Specializované varianty

Místní implementace řazení radix MSD

Binární MSD radix sort, nazývaný také binární quicksort, lze implementovat na místě rozdělením vstupního pole na dva koše - zásobník 0 s a zásobník 1 s. Zásobník 0 s je pěstován od začátku pole, zatímco zásobník 1 s je pěstován od konce pole. Hranice zásobníku 0 s je umístěna před první prvek pole. Hranice bin 1 s je umístěna za poslední prvek pole. Nejvýznamnější bit prvního prvku pole je zkoumán. Pokud je tento bit 1, pak se první prvek zamění s prvkem před hranicí bin 1 s (poslední prvek pole) a bin 1 s se zvětší o jeden prvek dekrementováním indexu hranice 1 s. Pokud je tento bit 0, pak první prvek zůstane na svém aktuálním místě a zásobník 0 s se zvětší o jeden prvek. Dalším zkoumaným prvkem pole je ten před hranicí zásobníku 0 s (tj. První prvek, který není v zásobníku 0 s nebo 1 s zásobníku). Tento proces pokračuje, dokud se zásobník 0 s a zásobník 1 s nedostanou k sobě. Zásobník 0 s a zásobník 1 s jsou poté rekurzivně tříděny na základě dalšího bitu každého prvku pole. Rekurzivní zpracování pokračuje, dokud se pro třídění nepoužije nejméně významný bit.[7][8] Zpracování celých čísel se znaménkem vyžaduje zpracování nejvýznamnějšího bitu v opačném smyslu, následované nepodepsaným zpracováním zbytku bitů.

Místní binární radix MSD lze rozšířit na větší radix a zachovat schopnost na místě. Počítání řazení se používá k určení velikosti každého koše a jejich počátečního indexu. Swapping se používá k umístění aktuálního prvku do jeho koše, následované rozšířením hranice koše. Jak jsou skenovány prvky pole, jsou přeskočeny koše a jsou zpracovávány pouze prvky mezi zásobníky, dokud nebude zpracováno celé pole a všechny prvky skončí v příslušných košech. Počet košů je stejný jako použitý radix - např. 16 košů pro 16-radix. Každý průchod je založen na jedné číslici (např. 4 bity na číslici v případě 16 radixů), počínaje nejvýznamnější číslice. Každá přihrádka je poté rekurzivně zpracována pomocí další číslice, dokud nebudou pro třídění použity všechny číslice.[9][10]

Ani místní binární radixové třídění, ani n-bitové radixové řazení, popsané v odstavcích výše, nejsou stabilní algoritmy.

Stabilní implementace radixu MSD radix

Řazení radixů MSD lze implementovat jako stabilní algoritmus, ale vyžaduje použití vyrovnávací paměti stejné velikosti jako vstupní pole. Tato dodatečná paměť umožňuje skenovat vstupní vyrovnávací paměť od prvního prvku pole do posledního a přesunout prvky pole do cílových přihrádek ve stejném pořadí. Rovné prvky budou tedy umístěny do vyrovnávací paměti paměti ve stejném pořadí, v jakém byly ve vstupním poli. Algoritmus založený na MSD používá extra paměťovou vyrovnávací paměť jako výstup na první úrovni rekurze, ale zamění vstup a výstup na další úrovni rekurze, aby se zabránilo režii kopírování výstupního výsledku zpět do vstupní vyrovnávací paměti. Každá z přihrádek je rekurzivně zpracována, jak je tomu u místního řazení MSD radix. Po dokončení třídění podle poslední číslice se zkontroluje výstupní vyrovnávací paměť, aby se zjistilo, zda se jedná o původní vstupní pole, a pokud tomu tak není, provede se jedna kopie. Pokud je velikost číslice zvolena tak, že velikost klíče dělená velikostí číslice je sudé číslo, kopie na konci se vyhne.[11]

Hybridní přístupy

Radixové třídění, například dvouprůchodová metoda kde počítání řazení se používá při prvním průchodu každé úrovně rekurze, má velkou konstantní režii. Když se tedy přihrádky zmenší, měly by se použít jiné třídicí algoritmy, například třídění vložení. Dobrá implementace třídění vložení je rychlý pro malá pole, stabilní, na místě a může výrazně urychlit třídění radixů.

Aplikace na paralelní výpočty

Všimněte si, že tento rekurzivní třídicí algoritmus má konkrétní aplikaci paralelní výpočty, protože každý z košů lze třídit samostatně. V tomto případě je každý zásobník předán dalšímu dostupnému procesoru. Na začátku by byl použit jeden procesor (nejvýznamnější číslice). Do druhé nebo třetí číslice by pravděpodobně byly zapojeny všechny dostupné procesory. V ideálním případě, protože každé rozdělení je plně tříděno, by bylo využito stále méně procesorů. V nejhorším případě budou všechny klíče identické nebo téměř totožné, takže výsledkem bude malá nebo žádná výhoda použití paralelních výpočtů k třídění klíčů.

Na nejvyšší úrovni rekurze je příležitost k paralelismu v počítání řazení část algoritmu. Počítání je vysoce paralelní, přístupné vzoru parallel_reduce a dobře rozděluje práci mezi více jader, dokud nedosáhne limitu šířky pásma paměti. Tato část algoritmu má na datech nezávislý paralelismus. Zpracování každého zásobníku v následujících úrovních rekurze však závisí na datech. Například pokud by všechny klíče měly stejnou hodnotu, pak by existoval pouze jeden koš s jakýmikoli prvky a nebyl by k dispozici žádný paralelismus. U náhodných vstupů by všechny zásobníky byly téměř stejně osídlené a byla by k dispozici velká příležitost k paralelismu.[12]

Všimněte si, že jsou k dispozici rychlejší algoritmy paralelního třídění, například optimální složitost O (log (n)) jsou ti ze tří Maďarů a Richarda Colea[13][14] a Dávkovač je bitonické sloučení má algoritmickou složitost O (log2(n)), z nichž všechny mají nižší algoritmickou časovou složitost pro radixové řazení na POSÁDKU-PRAM. Nejrychleji známé druhy PRAM popsal v roce 1991 David Powers s paralelizovaným quicksortem, který může pracovat v O (log (n)) čase na CRCW-PRAM s n procesory implicitním provedením rozdělení, stejně jako radixsort, který pracuje se stejným trikem v O (k), kde k je maximální délka klíče.[15] Ani architekturu PRAM, ani jediný sekvenční procesor však nelze ve skutečnosti postavit způsobem, který se bude škálovat bez počtu konstant fan-out zpoždění brány na cyklus se zvyšují jako O (log (n)), takže ve skutečnosti zřetězená verze Batcherova bitonického sloučení a O (log (n)) Druhy PRAM jsou všechny O (log2(n)), pokud jde o hodinové cykly, přičemž Powers uznává, že Batcher's bude mít z hlediska zpoždění brány nižší konstantu než jeho Parallel quicksort a radix sort, nebo Colea Sloučit třídění, pro délku klíče nezávislou třídicí síť O (nlog2(n)).[16]

Třídění radixů na bázi Trie

Radix třídění lze také dosáhnout vybudováním trie (nebo radix strom) ze vstupní sady a provedením a předobjednávka traverz. To je podobné vztahu mezi heapsort a halda datová struktura. To může být užitečné pro určité typy dat, viz prasknout.

Viz také

Reference

  1. ^ USA 395781  a UK 327 
  2. ^ A b Donald Knuth. Umění počítačového programování, Svazek 3: Třídění a vyhledávání, Třetí edice. Addison-Wesley, 1997. ISBN  0-201-89685-0. Oddíl 5.2.5: Řazení podle distribuce, s. 168–179.
  3. ^ „Napsal jsem rychlejší algoritmus třídění“. 28. prosince 2016.
  4. ^ „Je radix řadit rychleji než quicksort pro celočíselná pole?“. erik.gorset.no.
  5. ^ "Šablona funkce integer_sort - 1.62.0". www.boost.org.
  6. ^ „Efektivní třídění velkých sad řetězců podle trie“.
  7. ^ R. Sedgewick, „Algorithms in C ++“, třetí vydání, 1998, s. 424-427
  8. ^ Duvanenko, Victor J. „Zlepšení algoritmu měřením výkonu: 2. část“. Dr. Dobb.
  9. ^ Duvanenko, Victor J. „Zlepšení algoritmu měřením výkonu: 3. část“. Dr. Dobb.
  10. ^ Duvanenko, Victor J. „Parallel In-Place Radix Sort Simplified“. Dr. Dobb.
  11. ^ Duvanenko, Victor J. „Zlepšení algoritmu měřením výkonu: 4. část“. Dr. Dobb.
  12. ^ Duvanenko, Victor J. „Parallel In-Place N-bit-Radix Sort“. Dr. Dobb.
  13. ^ A. Gibbons a W. Rytter, Efektivní paralelní algoritmy. Cambridge University Press, 1988.
  14. ^ H. Casanova a kol., Paralelní algoritmy. Chapman & Hall, 2008.
  15. ^ David M. W. Powers, Paralelní Quicksort a Radixsort s optimálním zrychlením, Sborník z mezinárodní konference o technologiích paralelních výpočtů. Novosibirsk. 1991.
  16. ^ David M. W. Powers, Paralelní sjednocení: praktická složitost, Australasian Computer Architecture Workshop, Flinders University, leden 1995

externí odkazy