Funnelsort - Funnelsort

Tento článek má několik problémů. Prosím pomozte vylepši to nebo diskutovat o těchto otázkách na internetu diskusní stránka. (Zjistěte, jak a kdy tyto zprávy ze šablony odebrat) Tento článek obsahuje seznam obecných Reference, ale zůstává z velké části neověřený, protože postrádá dostatečné odpovídající vložené citace. Prosím pomozte zlepšit tento článek představuji přesnější citace. (Květen 2014) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) tento článek příliš spoléhá na Reference na primární zdroje. Vylepšete to přidáním sekundární nebo terciární zdroje. (Květen 2014) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) tento článek může být pro většinu čtenářů příliš technická na to, aby je pochopili. Prosím pomozte to vylepšit na aby to bylo srozumitelné pro neodborníky, aniž by byly odstraněny technické podrobnosti. (Květen 2014) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

Funnelsort je na základě srovnání třídicí algoritmus. Je to podobné jako Sloučit třídění, ale je to algoritmus bez paměti cache, určené pro nastavení, kde je počet prvků k třídění příliš velký, aby se vešel do a mezipaměti kde se operace provádějí. Představil ho Matteo Frigo, Charles Leiserson, Harald Prokop a Sridhar Ramachandran v roce 1999 v kontextu mezipaměť model.^[1][2]

Matematické vlastnosti

V model externí paměti, počet přenosů paměti, které potřebuje k provedení ${ displaystyle N}$ položky na stroji s velikostí mezipaměti ${ displaystyle Z}$ a délka mezipaměti ${ displaystyle L}$ je ${ displaystyle O left ({ tfrac {N} {L}} log _ {Z} N right)}$, za předpokladu vysoké mezipaměti ${ displaystyle Z = Omega (L ^ {2})}$. Ukázalo se, že tento počet přenosů paměti je asymptoticky optimální pro srovnávací druhy. Funnelsort také dosahuje asymptoticky optimální běhové složitosti ${ displaystyle Theta (N log N)}$.

Algoritmus

Základní přehled

Funnelsort pracuje na souvislé řadě ${ displaystyle N}$ elementy. Chcete-li seřadit prvky, provede následující:

1. Rozdělte vstup na ${ displaystyle N ^ {1/3}}$ pole velikosti ${ displaystyle N ^ {2/3}}$a rekurzivně třídit pole.
2. Sloučit ${ displaystyle N ^ {1/3}}$ seřazené sekvence pomocí a ${ displaystyle N ^ {1/3}}$-fúze. (Tento proces bude popsán podrobněji.)

Funnelsort je podobný Sloučit třídění v tom, že je rekurzivně seřazen určitý počet dílčích polí, po kterém spojovací krok spojí dílčí pole do jednoho seřazeného pole. Sloučení provádí zařízení zvané k-fúze, které je popsáno v následující části.

k-mergeri

A k-merger bere ${ displaystyle k}$ seřazené sekvence. Po jednom vyvolání k-fúze vydá první ${ displaystyle k ^ {3}}$ prvky seřazené sekvence získané sloučením vstupních sekvencí k.

Na nejvyšší úrovni používá funnelsort a ${ displaystyle N ^ {1/3}}$-jděte na ${ displaystyle N ^ {1/3}}$ sekvence délky ${ displaystyle N ^ {2/3}}$, a vyvolá toto sloučení jednou.

The k-merger je vytvořen rekurzivně z ${ displaystyle { sqrt {k}}}$-mergeri. Skládá se z ${ displaystyle { sqrt {k}}}$ vstup ${ displaystyle { sqrt {k}}}$-mergeri ${ displaystyle I_ {1}, I_ {2}, ldots, I _ { sqrt {k}}}$a jeden výstup ${ displaystyle { sqrt {k}}}$-fúze ${ displaystyle O}$.v k vstupy jsou rozděleny na ${ displaystyle { sqrt {k}}}$ sady ${ displaystyle { sqrt {k}}}$ každý vstup. Každá z těchto sad je vstupem do jedné ze vstupních fúzí. Výstup každého sloučení vstupu je připojen k vyrovnávací paměti, a FIFO fronta které vydrží ${ displaystyle 2k ^ {3/2}}$ elementy. Vyrovnávací paměti jsou implementovány jako kruhové fronty.Výstupy ${ displaystyle { sqrt {k}}}$ vyrovnávací paměti jsou připojeny ke vstupům výstupního sloučení ${ displaystyle O}$. Nakonec výstup ${ displaystyle O}$ je výstup celé k-fúze.

V této konstrukci bude jakékoli vstupní sloučení pouze výstupy ${ displaystyle k ^ {3/2}}$ položky najednou, ale vyrovnávací paměť, do které se vydává, má dvojnásobný prostor. To se děje tak, že lze sloučení vstupu volat pouze tehdy, když jeho vyrovnávací paměť nemá dostatek položek, ale že když se volá, vydává spoustu položek najednou (jmenovitě ${ displaystyle k ^ {3/2}}$ z nich).

A k-merger pracuje rekurzivně následujícím způsobem. Výstup ${ displaystyle k ^ {3}}$ prvků, rekurzivně vyvolá své výstupní sloučení ${ displaystyle k ^ {3/2}}$ krát. Než však zavolá ${ displaystyle O}$, zkontroluje všechny své vyrovnávací paměti a vyplní všechny z nich, které jsou méně než z poloviny plné. K vyplnění i-té vyrovnávací paměti rekurzivně vyvolá odpovídající vstupní fúzi ${ displaystyle I_ {i}}$ jednou. Pokud to nelze provést (kvůli sloučení vstupů), je tento krok přeskočen. Protože toto volání vychází ${ displaystyle k ^ {3/2}}$ prvky, vyrovnávací paměť obsahuje alespoň ${ displaystyle k ^ {3/2}}$ elementy. Na konci všech těchto operací k-merger má výstup první ${ displaystyle k ^ {3}}$ jejích vstupních prvků v seřazeném pořadí.

Analýza

Většina analýzy tohoto algoritmu se točí kolem analýzy složitosti k-fúze v prostoru a mezipaměti.

První důležitá vazba je, že k-fúze může zapadat ${ displaystyle O (k ^ {2})}$ prostor. Abychom to viděli, nechali jsme to ${ displaystyle S (k)}$ označuje prostor potřebný pro k-fúzi. Aby se vešly ${ displaystyle k ^ {1/2}}$ nárazníky velikosti ${ displaystyle 2k ^ {3/2}}$ bere ${ displaystyle O (k ^ {2})}$ prostor. Aby se vešly ${ displaystyle { sqrt {k}} + 1}$ menší nárazníky trvá ${ displaystyle ({ sqrt {k}} + 1) S ({ sqrt {k}})}$ prostor. Prostor tedy uspokojuje opakování ${ displaystyle S (k) = ({ sqrt {k}} + 1) S ({ sqrt {k}}) + O (k ^ {2})}$. Toto opakování má řešení ${ displaystyle S (k) = O (k ^ {2})}$.

Z toho vyplývá, že existuje pozitivní konstanta ${ displaystyle alpha}$ takové, že problém s velikostí nanejvýš ${ displaystyle alpha { sqrt {Z}}}$ zapadá zcela do mezipaměti, což znamená, že nevznikají žádné další chyby mezipaměti.

Pronájem ${ displaystyle Q_ {M} (k)}$ označit počet zmeškaných mezipaměti vzniklých voláním k-fúze, lze to ukázat ${ displaystyle Q_ {M} (k) = O ((k ^ {3} log _ {Z} k) / L).}$ To se provádí indukčním argumentem. Má to ${ displaystyle k leq alpha { sqrt {Z}}}$ jako základní případ. Pro větší k můžeme omezit počet a ${ displaystyle { sqrt {k}}}$- volá se merger. Sloučení výstupu se nazývá přesně ${ displaystyle k ^ {3/2}}$ krát. Celkový počet hovorů při sloučení vstupů je maximálně ${ displaystyle k ^ {3/2} +2 { sqrt {k}}}$. To dává celkovou hranici ${ displaystyle 2k ^ {3/2} +2 { sqrt {k}}}$ rekurzivní volání. Algoritmus navíc kontroluje každou vyrovnávací paměť, aby zjistil, zda je třeba ji vyplnit. To se děje ${ displaystyle { sqrt {k}}}$ vyrovnává každý krok pro ${ displaystyle k ^ {3/2}}$ kroky vedoucí k maximu ${ displaystyle k ^ {2}}$ chybí mezipaměť pro všechny kontroly.

To vede k opakování ${ displaystyle Q_ {M} (k) leq (2k ^ {3/2} +2 { sqrt {k}}) Q_ {M} ({ sqrt {k}}) + k ^ {2}}$, u kterého lze prokázat výše uvedené řešení.

Nakonec celková mezipaměť chybí ${ displaystyle Q (N)}$ pro celý druh lze analyzovat. Uspokojuje opakování ${ displaystyle Q (N) = N ^ {1/3} Q (N ^ {2/3}) + Q_ {M} (N ^ {1/3}).}$ To může být prokázáno, že má řešení ${ displaystyle Q (N) = O ((N / L) log _ {Z} N).}$

Líný trychtýř

Líný trychtýř je modifikace trychtýře, kterou zavedl Gerth Stølting Brodal a Rolf Fagerberg v roce 2002.^[3]Modifikace spočívá v tom, že když je vyvolána fúze, nemusí vyplnit každou ze svých vyrovnávacích pamětí. Místo toho líně vyplní vyrovnávací paměť, pouze když je prázdná. Tato modifikace má stejný asymptotický běh a přenosy paměti jako původní trychtýř, ale má aplikace v mezipaměťových algoritmech pro řešení problémů ve výpočetní geometrii metodou známou jako zametání distribuce.

Viz také

• Algoritmus zapomínající na mezipaměť
• Distribuce bez zapamatování na mezipaměť
• Externí třídění

Reference