Fingersökning
Inom datavetenskap är en fingersökning på en datastruktur en förlängning av alla sökoperationer som strukturen stöder, där en referens (finger) till ett element i datastrukturen ges tillsammans med frågan. Medan söktiden för ett element oftast uttrycks som en funktion av antalet element i en datastruktur, är fingersökningstider en funktion av avståndet mellan elementet och fingret.
I en uppsättning av n element är avståndet d ( x , y ) (eller helt enkelt d när det är entydigt) mellan två element x och y deras skillnad i rangordning. Om x och y är de i :e och j: e största elementen i strukturen, så är skillnaden i rang | i - j |. Om en normal sökning i någon struktur normalt skulle ta O(f( n )) tid, så bör en fingersökning efter x med finger y helst ta O(f( d )) tid. Observera att eftersom d ≤ n , följer att fingersökning i värsta fall bara är lika dåligt som normalt sök. Men i praktiken fungerar dessa degenererade fingersökningar mer än vanliga sökningar. Till exempel, om f( n ) är log( n ), och fingersökning gör dubbelt så många jämförelser som normal sökning i värsta fall, följer det att fingersökning är långsammare när d > √ n . Därför bör fingersökning endast användas när man rimligen kan förvänta sig att målet faktiskt är nära fingret.
Genomföranden
Vissa populära datastrukturer stöder fingersökning utan ytterligare ändringar av den faktiska strukturen. I strukturer där sökning efter ett element x utförs genom att begränsa ett intervall över vilket x kan hittas, utförs fingersökning från y vanligtvis genom att vända sökprocessen från y tills sökintervallet är tillräckligt stort för att innehålla x , då sökningen fortsätter som vanligt.
Sorterade länkade listor
I en länkad lista söker man normalt linjärt efter ett element genom att gå från ena änden till den andra. Om den länkade listan är sorterad och vi har en referens till någon nod som innehåller y , så kan vi hitta x i O( d ) tid genom att starta vår sökning från y .
Sorterade arrayer
I en sorterad array A söker man normalt efter ett element x i A med en binär sökning . Fingersökning utförs genom att utföra en ensidig sökning från A [ j ] = y . Medan binär sökning halverar sökutrymmet efter varje jämförelse, fördubblar ensidig sökning sökutrymmet efter varje jämförelse. Specifikt, vid den k: te iterationen av ensidig sökning (förutsatt att x > y ), är intervallet som beaktas A [ j , j +2 k -1 ]. Expansionen stannar så snart A [ j + 2 k -1 ] ≥ x , vid vilken punkt detta intervall söks binärt efter x .
Om ensidig sökning tar k iterationer för att hitta ett intervall som innehåller x , så följer det att d > 2 k -2 . Binär sökning i detta intervall kommer också att ta ytterligare k iterationer. Därför tar fingersökning efter x från y O( k ) = O(log d ) tid.
Hoppa över listor
I en överhoppningslista kan man fingersöka efter x från en nod som innehåller elementet y genom att helt enkelt fortsätta sökningen från denna punkt. Observera att om x < y fortsätter sökningen bakåt, och om x > y fortsätter sökningen framåt. Bakåtfallet är symmetriskt med normal sökning i en överhoppningslista, men fallet framåt är faktiskt mer komplext. Normalt förväntas sökningen i en överhoppningslista vara snabb eftersom vaktposten i början av listan är lika hög som den högsta noden. Men vårt finger kan vara en nod med höjd 1. På grund av detta kan vi ibland klättra medan vi försöker söka; något som aldrig inträffar normalt. Men även med denna komplikation kan vi uppnå O(log d ) förväntad söktid.
Treaps
En treap är ett randomiserat binärt sökträd (BST). Att söka i en treap är detsamma som att söka efter ett element i vilken annan BST som helst. Treaps har dock egenskapen att den förväntade väglängden mellan två element av avståndet d är O(log d ). För att fingersökning från noden som innehåller y för x kan man alltså klättra i trädet från y tills en förfader till x hittas, vid vilken punkt normal BST-sökning fortsätter som vanligt. Även om det inte är trivialt att avgöra om en nod är en annans förfader, kan man utöka trädet för att stödja frågor av denna form för att ge förväntad O(log d) fingersökningstid .
Rep och träd
Implementeringar av repet (datastruktur) implementerar vanligtvis en reppositionsiterator för att korsa strängen. Iteratorn kan ses som ett finger som pekar på någon specifik karaktär hos strängen. Liksom de flesta balanserade träd kräver rep O(log( n )) tid för att hämta data i ett blad av trädet när endast trädets rot ges. Att läsa varje löv av trädet verkar kräva O( n *log( n )) tid. Men genom att lagra lite extra information kan iteratorn användas för att läsa "nästa" blad på endast O(1) tid, och varje blad i ett träd på endast O(n) tid . Implementeringar av rep cachelagrar vanligtvis "extra information" om hela vägen från roten till den aktuella nodpositionen i iteratorn. Andra implementeringar av träddatastrukturer lagrar ibland "extra information" i själva trädet, lagrar en pekare i varje nod till dess förälder eller dess efterföljare (utöver de normala pekarna i varje nod till dess underordnade) och lagrar endast den aktuella noden position i iteratorn.
Generaliseringar
Om man kan utföra fingersökning på ett iterativt sätt i O ( f ( d )) tid, där varje iteration tar O (1) tid, så kan man genom att tillhandahålla c olika fingrar utföra fingersökning i O ( c min{ d ( x , y ), ..., d ( x , y c ) }) tid. Detta uppnås genom att starta fingersökning för alla c fingrar och iterera dem framåt ett steg vardera tills det första avslutas.
Givet varje sekvens A = [ a 1 , ..., a m ] av m accesser, sägs en struktur ha den statiska fingeregenskapen för ett fixerat finger f , om tiden att utföra A är . Splayträd har denna egenskap för valfritt f utan ytterligare bearbetning på tillräckligt stora åtkomstsekvenser.
Ansökningar
Fingersökning kan användas för att återanvända arbete som redan gjorts i tidigare sökningar. Till exempel, ett sätt att iterera över elementen i en datastruktur är att helt enkelt fingersöka efter dem i ordning, där fingret för en fråga är platsen för resultatet av den sista. Man kan optimera sin datastruktur genom att göra detta internt om man vet att sökningar ofta är nära den senaste sökningen.
Ett fingersökningsträd är en typ av datastruktur som gör att fingrar kan specificeras så att alla eller några av deras stödda operationer är snabbare när de kommer åt eller ändrar en plats nära ett finger. I motsats till fingersökningarna som beskrivs i den här artikeln tillhandahålls dessa fingrar inte vid frågetillfället, utan specificeras separat så att alla framtida operationer använder dessa fingrar. En fördel med detta är att användaren inte behöver manipulera eller lagra interna referenser till strukturen, de kan helt enkelt specificera ett element i strukturen.