Rozsah dotazu (datové struktury) - Range query (data structures)
Tento článek je tón nebo styl nemusí odrážet encyklopedický tón použitý na Wikipedii.Prosinec 2017) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) ( |
v datové struktury, a rozsah dotazu spočívá v předzpracování některých vstupních dat do a datová struktura efektivně odpovědět na libovolný počet dotazů na libovolnou podmnožinu vstupu. Zejména existuje skupina problémů, které byly rozsáhle studovány, pokud jde o vstup pole netříděných čísel a dotaz se skládá z výpočtu nějaké funkce, například minima, pro konkrétní rozsah pole.
Definice
Rozsahový dotaz na poli z n prvky nějaké množiny S, označeno , bere dva indexy , funkce F definováno přes pole prvků S a výstupy .
Například pro a pole čísel, dotaz na rozsah počítá , pro všechny . Na tyto dotazy lze odpovědět konstantní čas a pomocí extra prostor výpočtem součtu prvního i prvky A a ukládat je do pomocného pole B, takový, že obsahuje součet prvního i prvky A pro každého . Na jakýkoli dotaz tedy může být odpovězeno provedením .
Tuto strategii lze rozšířit pro všechny skupina operátor F kde je pojem je dobře definovaný a snadno vypočítatelný.[1] Nakonec lze toto řešení rozšířit na dvourozměrná pole s podobným předzpracováním.[2]
Příklady
Operátoři poloskupin
Když je zájmová funkce v dotazu na rozsah a poloskupina operátor, pojem není vždy definováno, takže strategie v předchozí části nefunguje. Andrew Yao ukázal[3] že existuje efektivní řešení pro dotazy na rozsah, které zahrnují operátory poloskupin. Dokázal to pro každou konstantu C, předzpracování času a prostoru umožňuje odpovídat na dotazy rozsahu na seznamech, kde F je operátor poloskupiny v čas, kde je určitá funkční inverze k Ackermannova funkce.
Existují operátoři poloskupin, kteří připouštějí o něco lepší řešení. Například když . Převzít pak vrací index souboru minimální prvek . Pak označuje odpovídající dotaz minimálního rozsahu. Existuje několik datových struktur, které umožňují odpovědět na minimální dotaz v rozsahu čas pomocí předzpracování času a prostoru . Jedno takové řešení je založeno na rovnocennosti tohoto problému s nejnižší společný předek problém.
The Kartézský strom pole má jako root a jako levý a pravý podstrom kartézský strom a kartézský strom resp. Rozsah minimální dotaz je nejnižší společný předek v z a . Protože nejnižšího společného předka lze vyřešit v konstantní čas pomocí předzpracování času a prostoru , rozsah minimální dotaz může také. Řešení, když je analogický. Kartézské stromy mohou být postaveny v lineární čas.
Režim
The režimu pole A je prvek, který se nejvíce objevuje v A. Například režim je 4. V případě vazeb může být jako režim vybrán některý z nejčastějších prvků. Dotaz v režimu rozsahu spočívá v předzpracování takže můžeme najít režim v jakémkoli rozsahu . K vyřešení tohoto problému bylo navrženo několik datových struktur, některé výsledky shrnujeme v následující tabulce.[1]
Prostor | Čas dotazu | Omezení |
---|---|---|
Nedávno Jørgensen a kol. prokázal dolní mez na model buněčné sondy z pro jakoukoli datovou strukturu, která používá S buňky.[4]
Medián
Tento konkrétní případ je obzvláště zajímavý od nalezení medián má několik aplikací.[5] Na druhou stranu mediánový problém, zvláštní případ problém s výběrem, je řešitelný v Ó(n), za použití medián mediánů algoritmus.[6] Jeho zobecnění prostřednictvím mediánu dotazů na rozsah je však nedávné.[7] Medián dotazu rozsahu kde A, i a j mít obvyklý význam vrací střední prvek z . Ekvivalentně by měl vrátit prvek hodnosti . Medián dotazů na rozsah nelze vyřešit sledováním žádné z předchozích metod diskutovaných výše, včetně přístupu Yao pro operátory poloskupin.[8]
Byly studovány dvě varianty tohoto problému, offline verze, kde všechny k dotazy, které vás zajímají, jsou dávány v dávce a verze, kde se veškeré předzpracování provádí předem. Offline verzi lze vyřešit pomocí čas a prostor.
Následující pseudokód algoritmus quickselect ukazuje, jak najít prvek pořadí r v netříděné pole odlišných prvků, abychom našli medián rozsahu, který jsme nastavili .[7]
rangeMedian (A, i, j, r) { -li A.length () == 1 vrátit se A [1] -li A.low není definováno pak m = medián (A) A.low = [e v A | e <= m] A.vysoká = [e v A | e> m] vypočítat t počet prvků A [i, j], které patří A.low -li r <= t pak vrátit se rangeMedian (A.low, i, j, r) jiný vrátit se rangeMedian (A.high, i, j, r-t)}
Postup rangeMedian
oddíly A
, použitím A
je medián, do dvou polí A.low
a Výška
, kde první obsahuje prvky A
které jsou menší nebo rovny mediánu m
a druhý zbytek prvků A
. Pokud víme, že počet prvků které končí v A.low
je t
a toto číslo je větší než r
pak bychom měli dál hledat prvek hodnosti r
v A.low
; jinak bychom měli hledat prvek hodnosti v Výška
. Najít t, stačí najít maximální index takhle je v A.low
a maximální index takhle je v Výška
. Pak . Celková cena za jakýkoli dotaz, bez ohledu na část rozdělení, je protože nanejvýš rekurzivní volání se provádějí a v každém z nich se provádí pouze konstantní počet operací (pro získání hodnoty t částečné kaskádování Pokud se použije lineární algoritmus k nalezení mediánů, celkové náklady na předzpracování pro k medián rozsahu dotazů je . Algoritmus lze také upravit tak, aby vyřešil online verze problému.[7]
Související problémy
Všechny výše popsané problémy byly studovány pro vyšší dimenze i pro jejich dynamické verze. Na druhou stranu lze rozsahové dotazy rozšířit na další datové struktury, jako je stromy,[8] tak jako problém předků na úrovni. Podobná rodina problémů je ortogonální rozsah dotazy, známé také jako počítání dotazů.
Viz také
Reference
- ^ A b Krizanc, Danny; Morin, Pat; Smid, Michiel H. M. (2003). "Režim rozsahu a střední rozsah dotazů na seznamy a stromy". ISAAC: 517–526.
- ^ Meng, He; Munro, J. Ian; Nicholson, Patrick K. (2011). "Výběr dynamického rozsahu v lineárním prostoru". ISAAC: 160–169.
- ^ Yao, A. C (1982). "Časoprostorový kompromis pro zodpovězení dotazů na rozsah". 14. výroční ACM sympozium o teorii práce s počítačem: 128–136.
- ^ Greve, M; J { o} rgensen, A .; Larsen, K .; Truelsen, J. (2010). Msgstr "Dolní hranice a aproximace sondy buňky pro režim dosahu". Automaty, jazyky a programování: 605–616.
- ^ Har-Peled, Sariel; Muthukrishnan, S. (2008). "Range Medians". ESA: 503–514.
- ^ Blum, M.; Floyd, R. W.; Pratt, V. R.; Rivest, R. L.; Tarjan, R. E. (Srpen 1973). „Časové hranice pro výběr“ (PDF). Journal of Computer and System Sciences. 7 (4): 448–461. doi:10.1016 / S0022-0000 (73) 80033-9.CS1 maint: ref = harv (odkaz)
- ^ A b C Beat, Gfeller; Sanders, Peter (2009). "Směrem k optimálnímu dosahu mediánu". ICALP (1): 475–486.
- ^ A b Bose, P; Kranakis, E .; Morin, P.; Tang, Y. (2005). „Režim přibližného rozsahu a medián dotazu na rozsah“. Ve sborníku z 22. sympozia o teoretických aspektech informatiky (STACS 2005), svazek 3404 přednášek v ComputerScience: 377–388.