Problém s údržbou objednávky - Order-maintenance problem

v počítačová věda, problém s údržbou objednávky zahrnuje údržbu a úplně objednaná sada podpora následujících operací:

• vložka (X, Y), který vloží X bezprostředně za Y v celkové objednávce;
• objednávka (X, Y), který určuje, zda X předchází Y v celkovém pořadí; a
• smazat (X), který odstraní X ze sady.

Paul Dietz poprvé zavedl datovou strukturu k vyřešení tohoto problému v roce 1982.^[1] Tato struktura dat podporuje vložka (X, Y) v ${ displaystyle O ( log n)}$ (v Velká O notace )amortizovaný čas a objednávka (X, Y) v konstantním čase, ale nepodporuje mazání. Athanasios Tsakalidis použité stromy BB [α] se stejnými hranicemi výkonu, které podporují odstranění v ${ displaystyle O ( log n)}$ a vylepšený výkon vkládání a mazání do${ displaystyle O (1)}$ amortizovaný čas s indirection.^[2] Dietz a Daniel Sleator zveřejnila vylepšení nejhoršího konstantního času v roce 1987.^[3] V roce 2004 zveřejnili Michael Bender, Richard Cole a Jack Zito výrazně zjednodušené alternativy.^[4] Bender, Fineman, Gilbert, Kopelowitz a Montes také v roce 2017 zveřejnili deamortizované řešení.^[5]

Efektivní datové struktury pro údržbu objednávek mají aplikace v mnoha oblastech, včetně vytrvalost datové struktury,^[6] grafové algoritmy^[7][8] a datové struktury odolné vůči chybám.^[9]

Označení seznamu

Problém související s problémem údržby objednávek jeproblém se seznamovým označováním ve kterém místo objednávka (X, Y) provoz řešení musí udržovat přiřazení štítků z vesmíru celých čísel ${ displaystyle {1,2, ldots, u }}$ k prvkům sady tak, že X předchází Y v celkovém pořadí, pouze pokud je X přiřazen menší štítek než Y. Musí také podporovat anoperaci štítek (X) vrácení štítku libovolného uzlu X. Všimněte si toho objednávka (X, Y) lze provést jednoduše srovnáním štítek (X) a štítek (Y) takže řešení problému s označováním seznamů okamžitě způsobí problém s údržbou objednávky. Ve skutečnosti většina řešení problému s údržbou objednávek představuje řešení problému se značením seznamů doplněného o úroveň nepřímé výkonnosti datové struktury. Níže uvidíme příklad.

Pro efektivitu je žádoucí velikost ${ displaystyle u}$ univerzity bude omezen počtem prvků ${ displaystyle n}$ uložené v datové struktuře. V případě, že ${ displaystyle u}$ je vyžadováno, aby byl lineární v ${ displaystyle n}$ problém je znám jako zabalená řada údržby nebo hustá sekvenční údržba souborů Problém. Považujte prvky za položky v souboru a štítky za adresy, kde je každý prvek uložen. Potom by efektivní řešení problému s údržbou zabaleného pole umožnilo efektivní vkládání a mazání záznamů do středu souboru s noasymptotickým prostorem nad hlavou.^{[10][11][12][13][14]} Toto použití má nedávné aplikace zapouzdřené datové struktury^[15]a optimální nejhorší případové třídění na místě.^[16]

Za určitých omezení však ${ displaystyle Omega ( log ^ {2} n)}$ dolní hranice byly nalezeny na výkonu vkládání do řešení problému se seznamovým značením u lineárních vesmírů^[17] zatímco níže uvidíme, že řešení s polynomiálním vesmírem může provádět vložení dovnitř ${ displaystyle O ( log n)}$ čas.

Seznamy a binární vyhledávací stromy

Popis cesty X v tomto binárním stromu je 0221, což je reprezentace základny 3 celého čísla 25.

Označení seznamu ve vesmíru o velikosti polynomu v počtu${ displaystyle n}$ prvků v celkovém pořadí souvisí s problémem udržení rovnováhy v a binární vyhledávací strom. Všimněte si, že každý uzel X binárního vyhledávacího stromu je implicitně označen anintegerem, který odpovídá jeho cestě z kořene stromu. Toto celé číslo nazýváme popis cesty z X a definujte jej následovně ${ displaystyle sigma}$ být posloupnost levého a pravého sestupu v této cestě. Například, ${ displaystyle sigma = ({ text {left}}, { text {right}}, { text {right}})}$ pokud X je správné dítě pravého dítěte levého dítěte kořene stromu. Pak je X označeno celým číslem základna 3 reprezentace je dána nahrazením každého výskytu ${ displaystyle { text {left}}}$ v ${ displaystyle sigma}$ s 0, nahrazující každý výskyt ${ displaystyle { text {right}}}$ v${ displaystyle sigma}$ s 2 a připojením 1 na konec výsledného řetězce. V předchozím příkladu je popis cesty X X0221₃ což se rovná 25 v základně 10. Všimněte si, že pathlabels zachovávají stromové pořadí a lze je tedy použít k zodpovězení dotazů na objednávky v konstantním čase.

Pokud má strom výšku ${ displaystyle h}$ pak tato celá čísla pocházejí z vesmíru ${ displaystyle {1,2, ldots, 3 ^ {h + 1} -2 }}$. Pokud je tedy strom samovyvažování takže to udržuje výšku ne větší než ${ displaystyle c log n}$ pak je velikost vesmíru polynomiální ${ displaystyle n}$.

Proto lze problém se značením seznamu vyřešit udržováním vyváženého binárního vyhledávacího stromu na prvcích v seznamu rozšířených o popisky cest pro každý uzel. Protože však každá operace vyvažování stromu bude muset také aktualizovat tyto popisky cest, není pro tuto aplikaci vhodná datová struktura stromu s vlastním vyvážením. Všimněte si například, že rotace uzlu s podstromem velikosti${ displaystyle k}$, které lze provést v konstantním čase za obvyklých okolností, vyžaduje ${ displaystyle Omega (k)}$ aktualizace popisku cesty. Zejména pokud je uzel, který se otáčí, kořenem, pak rotace bude trvat lineárně ve velikosti celého stromu. S tak dlouhou dobou by bylo možné přestavět celý strom. Níže uvidíme, že existují samovyvažující datové struktury binárního vyhledávacího stromu, které během rebalancování způsobí nevhodný počet aktualizací štítků.

Datová struktura

Problém se seznamovým značením lze vyřešit vesmírem sizepolynomial v počtu prvků ${ displaystyle n}$ rozšířením astrom obětního beránka s popisy cest popsanými výše. Scapegoattrees provádí veškeré své vyvážení přestavováním podstromů. Protože to trvá ${ displaystyle Omega (k)}$ čas na přestavbu podstromu velikosti${ displaystyle k}$, rebranding, že podstrom v ${ displaystyle O (k)}$ poté, co je znovu sestaveno, nezmění asymptotický výkon vyrovnávací operace.

Objednat

Vzhledem ke dvěma uzlům X a Y, objednávka (X, Y) určuje jejich pořadí porovnáním jejich popisů cest.

Vložit

Vzhledem k novému uzlu pro X a ukazatel na uzel Y, vložka (X, Y) vloží X bezprostředně za Y obvyklým způsobem. Je-li požadována operace vyvážení, je přestavěn příslušný podstrom, jako je tomu u stromu obětního beránka obvyklé. Poté se podstrom prochází hloubkou a štítky cest každého z jeho uzlů se aktualizují. Jak je popsáno výše, toto asymptoticky netrvá déle než obvyklá operace obnovy.

Vymazat

Odstranění se provádí podobně jako vložení. Vzhledem k tomu, že uzel X byl odstraněn, smazat (X) odstraní X jako obvykle. Po jakékoli následné operaci opětovného sestavení následuje opětovné označení rebuiltsubtree.

Analýza

Z výše uvedeného argumentu o rebalancování výkonu stromu obětního beránka rozšířeného o popisky cest vyplývá, že výkon vkládání a mazání této datové struktury je asymptotický nyní než v běžném stromu obětního beránka. Pak, protože vkládání a mazání trvá ${ displaystyle O ( log n)}$ amortizovaný čas v obětních stromech, to samé platí pro tuto datovou strukturu.

Kromě toho strom obětního beránka s parametrem α udržuje výšku maximálně ${ displaystyle log _ {1 / alpha} n + 1}$, popisky cesty mají nanejvýš velikost ${ displaystyle 3 ^ { log _ {1 / alpha} n + 2} -2 leq 9n ^ { frac {1} { log _ {3} (1 / alpha)}}}$. Pro typickou hodnotu${ displaystyle alpha = { tfrac {2} {3}}}$ pak jsou štítky nanejvýš${ displaystyle 9n ^ {3}}$.

Pořadí dvou uzlů lze samozřejmě určit v konstantním čase porovnáním jejich popisků. Bližší prohlídka ukazuje, že to platí i pro velké ${ displaystyle n}$. Konkrétně, pokud je velikost slova stroje ${ displaystyle w}$ bitů, pak obvykle dokáže oslovit maximálně${ displaystyle 2 ^ {w}}$ uzly tak ${ displaystyle n <2 ^ {w}}$. Z toho vyplývá, že vesmír má nanejvýš velikost ${ displaystyle 9 cdot 2 ^ {3w}}$ a tak, aby štítky mohly být reprezentovány konstantním počtem (maximálně ${ displaystyle 4 + 3w}$) bity.

Dolní hranice označení seznamu

Ukázalo se, že jakékoli řešení problému s označováním seznamů s vesmírným polynomem v počtu prvků nebude mít výkon vkládání a mazání lepší než ${ displaystyle Omega ( log n)}$.^[18] Pak je výše uvedené řešení pro označování seznamů asymptoticky optimální. Mimochodem, to také dokazuje${ displaystyle Omega ( log n)}$ spodní hranice amortizované doby rebalancování vložení nebo odstranění ve stromu obětního beránka.

Tato dolní mez se však nevztahuje na problém údržby objednávky a, jak je uvedeno výše, existují datové struktury, které poskytují nejhorší případy konstantního časového výkonu u všech operací údržby objednávky.

O (1) amortizované vložení prostřednictvím indirekce

Indirection je technika používaná v datových strukturách, při které je problém rozdělen do několika úrovní datové struktury, aby se zlepšila účinnost. Typicky problém s velikostí ${ displaystyle n}$ je rozdělena na${ displaystyle n / log n}$ problémy s velikostí ${ displaystyle log n}$. Příklad, tato technika se používá v y-rychlé pokusy. Tato strategie také pracuje na zlepšení výkonu vkládání a mazání výše popsané datové struktury na konstantní amortizovaný čas. Infact, tato strategie funguje pro jakékoli řešení problému s označováním seznamů ${ displaystyle O ( log n)}$ čas vložení a vymazání.

Struktura dat o údržbě objednávek s indirection. Celkový počet prvků objednávky je uložen v ${ displaystyle O (N / log N)}$ souvislé seznamy velikostí ${ displaystyle O ( log N)}$, z nichž každý má zástupce ve stromu obětního beránka.

Nová datová struktura je zcela přestavěna, kdykoli se zvětší nebo zvětší. Nechat ${ displaystyle N}$ být počet prvků celkové objednávky, když byla naposledy přestavěna. Datová struktura je znovu sestavena vždy, když je invariantní ${ displaystyle { tfrac {N} {3}} leq n leq 2N}$ je narušen vložením nebo odstraněním. Vzhledem k tomu, že opětovné sestavení lze provést v lineárním čase, nemá to vliv na amortizovaný výkon vložení a odstranění.

Během přestavby byla ${ displaystyle N}$ prvky celkového řádu jsou rozděleny na ${ displaystyle O (N / log N)}$ souvislé seznamy, každý velikosti ${ displaystyle Omega ( log N)}$. Cesta-labeledscapegoat strom je konstruován na sadě uzlů představujících každý ze sublistů v jejich původním pořadí seznamu. Pro každý podseznam je vytvořen nepochybně propojený seznam jeho prvků, který ukládá s každým prvkem apointer k jeho zástupci ve stromu i místní integerlabel. Tyto místní štítky jsou nezávislé na štítcích použitých ve stromu a slouží k porovnání jakýchkoli dvou prvků stejného podřízeného seznamu. Prvky podřízeného seznamu jsou označeny místními štítky ${ displaystyle N, 2N, ldots, N log N, ldots}$v původním pořadí.

Objednat

Vzhledem k uzlům dílčích seznamů X a Y, objednávka (X, Y) může odpovídat tak, že nejprve zkontrolujete, zda jsou dva uzly ve stejném seznamu. Pokud ano, jejich pořadí lze určit porovnáním jejich místních štítků. Jinak se srovnávají popisy cest jejich zástupců v treeare. To vyžaduje neustálý čas.

Vložit

Vzhledem k novému uzlu dílčího seznamu pro X a ukazatel na uzel dílčího seznamu Y,vložka (X, Y) vloží X bezprostředně za Y do sublistof Y. Pokud je X vloženo na konec sublist, dostane místní štítek ${ displaystyle ell (Y) + N}$, kde ${ displaystyle ell (Y)}$je místní značka Y; jinak, pokud je to možné, je označen podlahou průměru místních štítků jeho dvou sousedů. Tento snadný případ trvá konstantní čas.

V těžkém případě mají sousedé X sousedící místní štítky a podřízený seznam musí být přestavěn. V tomto případě však alespoň${ displaystyle log N-1}$ od prvního vytvoření byly do podseznamu přidány prvky. Pak si můžeme dovolit strávit lineární množství času ve velikosti podseznamu, abychom jej znovu sestavili a případně rozdělili do menších podseznamů, aniž by to ovlivnilo amortizovanou cenu vložení o více než konstantu.

Pokud má podřízený seznam velikost ${ displaystyle k}$ pak jsme to rozdělili na${ displaystyle O (k / log N)}$ souvislé seznamy velikostí ${ displaystyle O ( log N)}$, místně označit každý nový sublist, jak je popsáno výše, a položit každý prvek sublist na nový reprezentativní uzel, který má být vložen do stromu. Trvá to ${ displaystyle O (k)}$ je čas postavit podskupiny. Jelikož nepovolujeme prázdné seznamy, existují maximálně${ displaystyle n leq 2N}$ z nich a tak lze do stromu vložit zástupce ${ displaystyle O ( log N)}$ čas. Proto to trvá${ displaystyle O (k)}$ čas vložit všechny nové zástupce do stromu.

Vymazat

Vzhledem k tomu, že má být odstraněn uzel podseznamu X, smazat (X) jednoduše odstraní X ze sublistu v konstantním čase. Pokud je tento seznam prázdný, musíme ze stromu odebrat zástupce tohoto seznamu. Protože přinejmenším ${ displaystyle Omega ( log N)}$prvky byly odstraněny z podseznamu, protože byl poprvé postaven, můžeme si dovolit utratit ${ displaystyle O ( log N)}$ čas potřebný k odstranění zástupce, aniž by to ovlivnilo naběhlé náklady na vymazání o více než konstantní hodnotu.

Viz také

• Obětní beránek strom

Reference

externí odkazy

• Dva zjednodušené algoritmy pro udržování pořadí v seznamu. - Tento dokument představuje datovou strukturu označování seznamů s amortizovaným výkonem, který explicitně neukládá strom. Uvedená analýza je pro podobnou datovou strukturu jednodušší než analýza (Dietz a Sleator, 1987).
• Otevřené datové struktury - Kapitola 8 - Stromy obětních beránků, Pat Morin