Prstové vyhledávání - Finger search

Příklad prstového vyhledávání na treapech.

v počítačová věda, a prstové vyhledávání na datová struktura je rozšíření jakékoli vyhledávací operace, kterou tato struktura podporuje, kde je spolu s dotazem uveden odkaz (prst) na prvek v datové struktuře. Zatímco doba hledání prvku je nejčastěji vyjádřena jako funkce počtu prvků v datové struktuře, časy vyhledávání prstem jsou funkcí vzdálenosti mezi prvkem a prstem.

V sadě n prvky, vzdálenost d(X,y) (nebo jednoduše d pokud je jednoznačný) mezi dvěma prvky X a y je jejich rozdíl v hodnosti. Li X a y jsou ith a jth největší prvky ve struktuře, pak rozdíl v pořadí je |i - j|. Pokud by normální hledání v nějaké struktuře normálně trvalo O (f (n)) čas, poté vyhledejte prstem X prstem y v ideálním případě by měl brát O (f (d)) čas. Poznamenejte to od té doby d ≤ nz toho vyplývá, že v nejhorším případě je vyhledávání prstem jen tak špatné jako normální vyhledávání. V praxi však tyto zdegenerované vyhledávání prstů fungují více než běžné vyhledávání. Například pokud f (n) je log (n) a vyhledávání prstem provede v nejhorším případě dvakrát tolik srovnání než normální vyhledávání, z čehož vyplývá, že vyhledávání prstem je pomalejší, když d > √n. Hledání prstu by proto mělo být použito pouze tehdy, když lze rozumně očekávat, že cíl bude skutečně blízko prstu.

Implementace

Některé populární datové struktury podporují vyhledávání prstů bez dalších změn skutečné struktury. Ve strukturách, kde je hledání prvku X je dosaženo zúžením intervalu, během kterého X lze najít, prstové vyhledávání z y se obvykle provádí obrácením procesu vyhledávání z y dokud není interval vyhledávání dostatečně velký na to, aby obsahoval X, kdy hledání pokračuje jako obvykle.

Seřazené propojené seznamy

V spojový seznam, jeden normálně hledá prvek lineárně procházením z jednoho konce na druhý. Pokud je propojený seznam seřazen a máme odkaz na nějaký uzel obsahující ypak můžeme najít X v O (d) čas zahájením vyhledávání z y.

Seřazené pole

V seřazené pole A, jeden normálně hledá prvek X v A s binární vyhledávání. Hledání prstu se provádí provedením a jednostranné vyhledávání z A[j] = y. Zatímco binární vyhledávání po každém srovnání snižuje prostor vyhledávání na polovinu, jednostranné vyhledávání po každém porovnání zdvojnásobuje prostor pro vyhledávání. Konkrétně na kiterace jednostranného vyhledávání (za předpokladu x> y), uvažovaný interval je A[j, j+2^k-1]. Expanze se zastaví, jakmile A[j + 2^k-1] ≥ X, kdy je tento interval binárně vyhledáván X.

Pokud jednostranné vyhledávání trvá k iterace k vyhledání intervalu, který obsahuje X, pak z toho vyplývá d > 2^k-2. Binární prohledávání tohoto rozsahu také zabere další k iterace. Proto vyhledejte prstem X z y bere O (k) = O (log d) čas.

Přeskočit seznamy

V přeskočit seznam, lze vyhledávat prstem X z uzlu obsahujícího prvek y pouhým pokračováním hledání od tohoto bodu. Všimněte si, že pokud x , pak hledání pokračuje dozadu, a pokud x> y, poté hledání pokračuje vpřed. Zpětný případ je symetrický k normálnímu vyhledávání v seznamu přeskočení, ale přední případ je ve skutečnosti složitější. Za normálních okolností se očekává rychlé vyhledávání v lyžařském seznamu, protože indikátor na začátku seznamu je stejně vysoký jako nejvyšší uzel. Náš prst by však mohl být uzel výšky 1. Z tohoto důvodu můžeme občas při pokusu o hledání stoupat; něco, co se normálně nikdy nevyskytuje. I s touto komplikací však můžeme dosáhnout O (log d) očekávaná doba hledání.^[1]

Treaps

A šlapat je randomizovaná binární vyhledávací strom (BST). Hledání v treapu je stejné jako hledání prvku v jakémkoli jiném BST. Treapy však mají tu vlastnost, že očekávaná délka cesty mezi dvěma prvky vzdálenosti d je O (log d). Tedy k vyhledávání prstem z uzlu obsahujícího y pro X, lze vylézt na strom y až do předchůdce X je nalezeno, kdy normální BST vyhledávání pokračuje jako obvykle. Zatímco určování, zda je uzel předkem jiného, ​​není triviální, je možné rozšířit strom tak, aby podporoval dotazy tohoto formuláře a poskytoval očekávané O (log d) čas hledání prstu.^[1]

Lana a stromy

Provádění lano (datová struktura) typicky implementovat iterátor polohy šňůry k procházení řetězce. Iterátor lze chápat jako prst, který ukazuje na určitý specifický znak řetězce. Stejně jako většina vyvážených stromů vyžadují lana O (logn)) čas na načtení dat v jednom listu stromu, pokud je uveden pouze kořen stromu. Čtení každého listu stromu by zřejmě vyžadovalo O (n* protokol (n)) time.However, by storage a few extra information, the iterator can be used to read "the next" leaf in only O (1) time, and every leaf of a tree in only O (1)n) time.Implementions of lanes usually cache "extra information" about the whole the path from the root to the current node position in the iterator.Other implementations of tree data structures sometimes store "extra information" in the tree itself, storing a pointer in každý uzel k jeho nadřazenému nebo jeho následníkovi (kromě normálních ukazatelů v každém uzlu k jeho podřízeným položkám) a uložení pouze aktuální polohy uzlu v iterátoru.^[2][3]

Zobecnění

Pokud je možné provést prstové vyhledávání iterativním způsobem v Ó(F(d)) čas, kde každá iterace trvá Ó(1) čas, poté poskytnutím C různé prsty, jeden může provádět vyhledávání prstů v Ó(C min {d(X, y₁), ..., d(X, y_C)}) čas. Toho je dosaženo spuštěním vyhledávání prstem pro všechny C prsty a iterace je dopředu o jeden krok, dokud první neskončí.

Vzhledem k jakékoli posloupnosti A = [A₁, ..., A_m] z m přístupy, říká se, že struktura má statická vlastnost prstu pro fixovaný prst F, pokud je čas na provedení A je ${ displaystyle O left ( sum _ {i = 1} ^ {m} log d (f, a_ {i}) right)}$. Roztáhněte stromy mít tuto vlastnost pro libovolný výběr F bez dalšího zpracování na dostatečně velkých sekvencích přístupů.^[4]

Aplikace

Vyhledávání prstu lze použít k opětovnému použití práce již provedené v předchozích vyhledáváních. Například jedním ze způsobů, jak iterovat prvky v datové struktuře, je jednoduše je vyhledat prstem v pořadí, kde prstem pro jeden dotaz je umístění výsledku posledního. Jeden může optimalizovat jejich datovou strukturu tím, že to provede interně, pokud je známo, že vyhledávání je často blízko posledního vyhledávání.

A strom pro vyhledávání prstů je typ datové struktury, která umožňuje specifikovat prsty tak, aby všechny nebo některé z jejich podporovaných operací byly rychlejší, když přistupují nebo upravují umístění poblíž prstu. Na rozdíl od vyhledávání pomocí prstů popsaných v tomto článku nejsou tyto prsty poskytovány v době dotazu, ale jsou specifikovány samostatně, aby je všechny budoucí operace používaly. Jednou z výhod toho je, že uživatel nemusí manipulovat nebo ukládat interní odkazy na strukturu, může jednoduše určit prvek ve struktuře.

Reference