Passilista

Ohituslista on todennäköisyyspohjainen tietorakenne , joka perustuu useisiin rinnakkaisiin lajiteltuihin linkitettyihin listoihin , joiden tehokkuus on  verrattavissa binääripuuhun (suuruusluokkaa O(log n) keskimääräinen aika useimmissa operaatioissa).

Ohituslista perustuu lajitellun linkitetyn listan laajentamiseen lisälinkeillä, jotka on lisätty satunnaisille poluille geometrisella /negatiivisella binomijakaumalla [1] , jotta luettelohaku voi ohittaa listan osia nopeasti. Lisäys, haku ja poisto suoritetaan logaritmisessa satunnaisessa ajassa.

Kuvaus

Ohituslista koostuu useista kerroksista. Alakerros on normaali järjestetty linkitetty lista . Jokainen ylempi kerros edustaa "omistettua kaistaa" alla oleville listoille, jossa i:nnen kerroksen elementti näkyy i+1:nnessä kerroksessa jollain kiinteällä todennäköisyydellä p (kaksi yleisimmin käytettyä arvoa p :lle  ovat 1 /2 ja 1/ neljä). Keskimäärin jokainen elementti esiintyy 1/(1- p ) -listoissa ja ylin elementti (yleensä luettelon alussa oleva erityinen head-elementti, jossa on aukkoja) listoissa.

Halutun elementin haku alkaa yläluettelon head-elementistä ja suoritetaan vaakasuunnassa, kunnes nykyinen elementti on suurempi tai yhtä suuri kuin tavoite. Jos nykyinen elementti on yhtä suuri kuin kohde, se löytyy. Jos nykyinen elementti on suurempi kuin tavoite, toimenpide toistetaan sen jälkeen, kun palataan edelliseen elementtiin ja lasketaan pystysuunnassa alas seuraavaan alempaan luetteloon. Jokaisen linkitetyn listan oletettu askelmäärä on 1/ p , joka näkyy katsomalla taaksepäin kohdeelementistä, kunnes seuraavaksi korkeammassa listassa oleva elementti saavutetaan. Siten haun odotettu kokonaiskustannus on yhtä suuri kuin vakion p tapauksessa . Valitsemalla erilaisia ​​p :n arvoja on mahdollista valita tarvittava kompromissi hakuajan kustannusten ja listan tallennuksen muistikustannusten välillä.

Toteutustiedot

Ohitusluettelossa käytetyt elementit voivat sisältää useamman kuin yhden osoittimen, joten ne voivat olla useammassa kuin yhdessä luettelossa.

Poista- ja lisäystoiminnot toteutetaan hyvin samalla tavalla kuin linkitettyjen luetteloiden toiminnot, paitsi että "korkea" on lisättävä tai poistettava useammasta kuin yhdestä linkitetystä listasta.

Ilman satunnaistamista nämä toiminnot johtaisivat kuitenkin erittäin huonoon suorituskykyyn, koska lista olisi sekoitettava kokonaan, kun uusi elementti lisätään, jotta hyppyjen määrä pysyisi vakiona huipputasolla. William Pugh ehdotti seuraavaa algoritmia sen päättämiseksi, kuinka korkealle uusi elementti tulisi työntää. Tämä algoritmi vaatii vain paikallisia muutoksia luetteloon, kun lisäät uusia elementtejä, ja voit tallentaa "pikerivien" tehokkuuden (l on tuloksena oleva arvo tasolle, jolle haluat sijoittaa elementin):

l = 1 kun taas satunnainen arvo alueella [0,1] < p ja l < maksimitaso l = l + 1

Tämän seurauksena elementti lisätään l:nnelle tasolle ja vastaavasti kaikille tasoille, jotka ovat pienempiä kuin l.

Θ(n)-operaatiot, joita tarvitsemme vieraillaksemme kussakin solmussa nousevassa järjestyksessä (esim. koko listan tulostaminen), tarjoavat mahdollisuuden hienovaraisesti desandomisoida aukkoluettelon tasorakenne optimaalisella tavalla saavuttaen linkitetyn luettelon hakuajan. . (valitsemalla i:nnen pään solmun taso 1 plus kuinka monta kertaa voimme jakaa i:n kahdella, kunnes siitä tulee pariton. Myös i=0 negatiivisesti äärettömälle otsikolle, kuten meillä on, tavallinen erikoistapaus, valittaessa korkein mahdollinen taso negatiiviset ja/tai positiiviset äärettömät solmut.) Tämä antaa kuitenkin mahdollisuuden tietää, missä kaikki solmut, joiden taso on suurempi kuin 1, ovat ja sitten poistaa ne.

Vaihtoehtoisesti voimme tehdä tasorakenteesta lähes satunnaisen seuraavasti:

luoda kaikki tason 1 solmut j = 1 kun taas solmujen määrä tasolla j > 1 jokaiselle i:nnelle solmulle tasolla j jos olen outo jos i ei ole tason j viimeinen solmu valita satunnaisesti, nostetaanko se tasolle j+1 muuten älä edistä lopputila muuten jos i edes solmua i-1 ei edistetä siirrä se tasolle j+1 lopputila silmukan loppu for j = j + 1 syklin loppu toistaiseksi

Aivan kuten derandomisoitu versio, kvasisatunnaistaminen tehdään vain, kun on jokin muu syy suorittaa Θ(n)-operaatioita (jotka vierailevat jokaisessa solmussa).

Toteutusesimerkki

C++-luokan koodi käyttäen std :: swap ; malli < typename KEY_T , typename DATA_T > class SkipList { koko_t MaxLevel ; kaksinkertainen SkipDivisor ; struct Pari { KEY_T Avain ; DATA_T Data ; Pari * Edellinen ; Taulukko < Pari *> Seuraava ; Pari ( const KEY_T & InKey , const DATA_T & InData , Pair * InPrevious , size_t InLevel ); Pari ( koko_t InLevel ); ~ pari (); Pari & operaattori = ( const Pair & InPair ); Pari * PreviousOnLevel ( koko_t InLevel ); Pari * NextOnLevel ( koko_t InLevel ); }; Pair Start ; Pari * UusiEdellinen ( const KEY_T & InKey ); Pari * PairByKey ( const KEY_T & InKey ); koko_tNewLevel ( ); julkinen : class Iterator { SkipList * CurrentList ; Pair * CurrentPair ; kaveriluokka SkipList < KEY_T , DATA_T > ; _ julkinen : Iteraattori ( const Iterator & InIterator ); Iteraattori ( SkipList & InSkipList ); operaattori bool (); Iteraattori ja operaattori ++ (); Iteraattori & operaattori -- (); Iteraattorioperaattori ++ ( int ) ; Iteraattorioperaattori -- ( int ) ; Iteraattori & operaattori += ( koko_t n ); Iteraattori & operaattori -= ( koko_t n ); Iteraattori & operaattori = ( const Iterator & InIterator ); Iteraattori & operaattori = ( const KEY_T & InKey ); DATA_T & operaattori * (); void Poista (); }; SkipList ( koko_t InNumberOfLanes = 3 , kaksinkertainen InSkipDivisor = 1,0 / 4,0 ); ~ SkipList (); Iteraattori GetBegin (); Iteraattori GetEnd (); void Add ( const KEY_T & InKey , const DATA_T & InData ); void Delete ( const KEY_T & InKey ); DATA_T & operaattori []( const KEY_T & InKey ); size_t Count (); voidClear ( ); Iteraattorin haku ( const DATA_T & Unknown ); bool IsEmpty (); }; malli < typename KEY_T , typename DATA_T > typename SkipList < KEY_T , DATA_T >:: Pair * SkipList < KEY_T , DATA_T >:: Pair :: PreviousOnLevel ( size_t InLevel ){ jos ( ! tämä ) return NULL ; Pari * Nykyinen = Edellinen ; for (; Nykyinen && ! ( Nykyinen -> Seuraava . Count () >= InLevel + 1 ); Nykyinen = Nykyinen -> Edellinen ){} paluu Nykyinen ; } malli < typename KEY_T , typename DATA_T > typename SkipList < KEY_T , DATA_T >:: Pair * SkipList < KEY_T , DATA_T >:: Pair :: NextOnLevel ( size_t InLevel ){ jos ( ! tämä ) return NULL ; Pari * Nykyinen = Seuraava [ InLevel -1 ]; for (; Nykyinen && ! ( Nykyinen -> Seuraava . Count () >= InLevel + 1 ); Nykyinen = Nykyinen -> Seuraava [ InLevel -1 ]){} paluu Nykyinen ; } malli < typename KEY_T , typename DATA_T > SkipList < KEY_T , DATA_T >:: Pair :: Pair ( const KEY_T & InKey , const DATA_T & InData , const DATA_T & InData , SkipList < KEY_T , DATA_T >:: Pair * Edellinen , size_t InLevel ) : Avain ( InKey ) , Data ( InusData ( Edellinen ){ Pari * Nykyinen = Edellinen -> Seuraava [ 0 ]; Seuraavaksi . AddLast ( nykyinen ); for ( koko_t Laskuri = 1 ; Laskuri <= InLevel ; Laskuri ++ ){ Nykyinen = NextOnLevel ( laskuri ); Seuraavaksi . AddLast ( nykyinen ); } nykyinen = edellinen ; for ( koko_t Laskuri = 0 ; Laskuri <= InLevel ; Laskuri ++ ) if ( Nykyinen = EdellinenOnTaso ( Laskuri )) Nykyinen -> Seuraava [ Laskuri ] = tämä ; } malli < typename KEY_T , typename DATA_T > SkipList < KEY_T , DATA_T >:: Pair :: Pair ( size_t InLevel ) : Previous ( NULL ){ for ( koko_t Laskuri = 0 ; Laskuri <= InLevel ; Laskuri ++ ) Seuraavaksi . AddLast ( NULL ); } malli < typename KEY_T , typename DATA_T > Ohituslista < KEY_T , DATA_T >:: Pari ::~ Pari (){ size_t OurLevel = Seuraava . Count () -1 ; Pari * Nykyinen = tämä ; for ( koko_t Laskuri = 0 ; Laskuri <= Meidän Taso ; Laskuri ++ ) if ( Nykyinen = EdellinenOnTaso ( Laskuri )) Nykyinen -> Seuraava [ Laskuri ] = Seuraava [ Laskuri ]; } malli < typename KEY_T , typename DATA_T > SkipList < KEY_T , DATA_T >:: SkipList ( size_t InMaxLevel , double InSkipDivisor ) : MaxLevel ( InMaxLevel ), SkipDivisor ( InSkipDivisor ), Aloita ( MaxLevel ){} malli < typename KEY_T , typename DATA_T > typename SkipList < KEY_T , DATA_T >:: Pair & SkipList < KEY_T , DATA_T >:: Pair :: operator = ( const SkipList < KEY_T , DATA_T >:: Pair & InPair ){ Avain = InPair . avain ; Data = InPair . tiedot ; Edellinen = InPair . Edellinen ; size_t max = Seuraava . laskea (); for ( koko_t i ; i < max ; ++ i ) Seuraavaksi . AddLast ( Seuraava [ i ]); palauta * tämä ; } malli < typename KEY_T , typename DATA_T > SkipList < KEY_T , DATA_T >::~ SkipList (){ selkeä (); } malli < typename KEY_T , typename DATA_T > tyypin nimi SkipList < KEY_T , DATA_T >:: Pair * SkipList < KEY_T , DATA_T >:: NewPrevious ( const KEY_T & InKey ){ Pari * Edellinen =& Aloita ; Pari * Nykyinen = Aloita . Seuraava [ MaxLevel ]; for ( koko_t Laskuri = MaxTaso ; Laskuri >= 0 ; Laskuri -- ){ while ( Nykyinen && InKey > Nykyinen -> Avain ){ edellinen = nykyinen ; Nykyinen = Nykyinen -> Seuraava [ Laskuri ]; } jos ( ! Counter ) tauko ; nykyinen = edellinen ; }; paluu Edellinen ; } malli < typename KEY_T , typename DATA_T > size_t SkipList < KEY_T , DATA_T >:: Uusi taso (){ koko_t Taso = 0 ; while ( rand () % 1000 < SkipDivisor * 1000 && Taso <= MaxLevel ) Taso ++ ; paluutaso ; _ } malli < typename KEY_T , typename DATA_T > void SkipList < KEY_T , DATA_T >:: Add ( const KEY_T & InKey , const DATA_T & InData ){ Pari * Edellinen = UusiEdellinen ( InKey ); Pari * Seuraava = Edellinen -> Seuraava [ 0 ]; if ( Seuraava && Seuraava -> Avain == InKey ) throw String ( "Ei ainutlaatuinen avain!" ); uusi pari ( InKey , InData , Previous , New Level ()); } malli < typename KEY_T , typename DATA_T > typename SkipList < KEY_T , DATA_T >:: Pair * SkipList < KEY_T , DATA_T >:: PairByKey ( const KEY_T & InKey ){ Pari * Nykyinen = UusiEdellinen ( InKey ); if (( Nykyinen = Nykyinen -> Seuraava [ 0 ]) && Nykyinen -> Avain == InKey ) paluu Nykyinen ; throw String ( "Ei paria tälle avaimelle!" ); } malli < typename KEY_T , typename DATA_T > void SkipList < KEY_T , DATA_T >:: Poista ( const KEY_T & InKey ){ jos ( OnTyhjä ()) throw String ( "Lista on tyhjä!" ); poista PairByKey ( InKey ); } malli < typename KEY_T , typename DATA_T > DATA_T & SkipList < KEY_T , DATA_T >:: operaattori []( const KEY_T & InKey ){ jos ( OnTyhjä ()) throw String ( "Lista on tyhjä!" ); return PairByKey ( InKey ) -> Data ; } malli < typename KEY_T , typename DATA_T > size_t SkipList < KEY_T , DATA_T >:: Count (){ jos ( OnTyhjä ()) paluu 0 ; Pari * Seuraava = Aloita . Seuraava [ 0 ]; koko_t n = 1 ; while ( Seuraava = Seuraava -> Seuraava [ 0 ]) n ++ ; paluu n ; } malli < typename KEY_T , typename DATA_T > void SkipList < KEY_T , DATA_T >:: Tyhjennä (){ Pari * Nykyinen = Aloita . Seuraava [ 1 ]; Pari * Edellinen = NULL ; while ( Nykyinen ){ Nykyinen -> Edellinen = NULL ; edellinen = nykyinen ; Nykyinen = Nykyinen -> Seuraava [ 0 ]; poista Edellinen ; } for ( koko_t i = 0 ; i <= Aloita . Seuraava . Count ( ) -1 ; i ++ ) aloita . Seuraava [ i ] = NULL ; } malli < typename KEY_T , typename DATA_T > SkipList < KEY_T , DATA_T >:: Iteraattori :: Iteraattori ( jatkuva SkipList < KEY_T , DATA_T > :: Iteraattori & InIteraattori ) : CurrentList ( InIterator . CurrentList ), CurrentPair ( InIterator . CurrentPair ) {} malli < typename KEY_T , typename DATA_T > SkipList < KEY_T , DATA_T >:: Iteraattori :: Iteraattori ( SkipList < KEY_T , DATA_T >& InSkipList ) : CurrentList ( & InSkipList ), CurrentPair ( InSkipList . Aloita . Seuraava [ 0 ]){} malli < typename KEY_T , typename DATA_T > SkipList < KEY_T , DATA_T >:: Iteraattori :: operaattori bool (){ return CurrentList && CurrentPair ; } malli < typename KEY_T , typename DATA_T > tyypin nimi SkipList < KEY_T , DATA_T >:: Iteraattori & SkipList < KEY_T , DATA_T >:: Iteraattori :: operaattori ++ (){ jos ( CurrentPair ) CurrentPair = CurrentPair -> Next [ 0 ]; palauta * tämä ; } malli < typename KEY_T , typename DATA_T > tyypin nimi SkipList < KEY_T , DATA_T >:: Iteraattori & SkipList < KEY_T , DATA_T >:: Iteraattori :: operaattori -- (){ if ( CurrentPair && CurrentPair != CurrentList -> Start . Next [ 0 ]) CurrentPair = CurrentPair -> Previous ; muu CurrentPair = NULL ; palauta * tämä ; } malli < typename KEY_T , typename DATA_T > tyypin nimi SkipList < KEY_T , DATA_T >:: Iterator SkipList < KEY_T , DATA_T >:: Iteraattori :: operaattori ++ ( int ){ Iteraattori Vanha ( * this ); ++* tämä ; paluu vanha ; } malli < typename KEY_T , typename DATA_T > tyypin nimi SkipList < KEY_T , DATA_T >:: Iterator SkipList < KEY_T , DATA_T >:: Iteraattori :: operaattori -- ( int ){ Iteraattori Vanha ( * this ); --* tämä ; paluu vanha ; } malli < typename KEY_T , typename DATA_T > tyypin nimi SkipList < KEY_T , DATA_T >:: Iteraattori & SkipList < KEY_T , DATA_T >:: Iteraattori :: operator = ( const SkipList < KEY_T , DATA_T >:: Iterator & InIterator ){ CurrentList = InIterator . CurrentList ; CurrentPair = InIterator . Nykyinen pari ; palauta * tämä ; } malli < typename KEY_T , typename DATA_T > tyypin nimi SkipList < KEY_T , DATA_T >:: Iteraattori & SkipList < KEY_T , DATA_T >:: Iteraattori :: operaattori = ( const KEY_T & InKey ){ CurrentPair = CurrentList -> PairByKey ( InKey ); palauta * tämä ; } malli < typename KEY_T , typename DATA_T > DATA_T & SkipList < KEY_T , DATA_T >:: Iteraattori :: operaattori * (){ jos ( !* tämä ) throw String ( "Luketaan huonosta iteraattorista!" ); return CurrentPair -> Data ; } malli < typename KEY_T , typename DATA_T > void SkipList < KEY_T , DATA_T >:: Iteraattori :: Poista (){ jos ( !* tämä ) throw String ( "Poistetaan huonon iteraattorin tietoja!" ); poista CurrentPair ; CurrentPair = NULL ; } malli < typename KEY_T , typename DATA_T > tyypin nimi SkipList < KEY_T , DATA_T >:: Iteraattori & SkipList < KEY_T , DATA_T >:: Iteraattori :: operaattori += ( koko_t n ){ for ( koko_t Laskuri = 0 ; Laskuri < n && CurrentPair ; Laskuri ++ ) CurrentPair = CurrentPair -> Next [ 0 ]; palauta * tämä ; } malli < typename KEY_T , typename DATA_T > tyypin nimi SkipList < KEY_T , DATA_T >:: Iteraattori & SkipList < KEY_T , DATA_T >:: Iteraattori :: operaattori -= ( koko_t n ){ for ( koko_t Laskuri = 0 ; Laskuri < n && CurrentPair ; Laskuri ++ ) CurrentPair = CurrentPair -> Previous ; if ( CurrentPair ==& CurrentList -> Start ) palauta * tämä ; } malli < typename KEY_T , typename DATA_T > typename SkipList < KEY_T , DATA_T >:: Iterator SkipList < KEY_T , DATA_T >:: GetBegin (){ return Iterator ( * this ); } malli < typename KEY_T , typename DATA_T > typename SkipList < KEY_T , DATA_T >:: Iterator SkipList < KEY_T , DATA_T >:: GetEnd (){ Iterator ReturnValue ( * this ); ReturnValue += ReturnValue . CurrentList -> Count () -1 ; return ReturnValue ; } malli < typename KEY_T , typename DATA_T > tyypin nimi SkipList < KEY_T , DATA_T >:: Iterator SkipList < KEY_T , DATA_T >:: Etsi ( jatkuva DATA_T & Tuntematon ) { Iteraattorin tulos ( * tämä ); while ( Tulos && ! ( * Tulos == Tuntematon )) ++ tulos ; palautus Tulos ; } malli < typename KEY_T , typename DATA_T > bool SkipList < KEY_T , DATA_T >:: IsEmpty (){ tyyppinimi Array < Pari *>:: Iteraattori i ( Aloita . Seuraava ); kun ( i ) jos ( * i ++ ) return false ; return true ; }

Muistiinpanot

  1. ↑ Pugh, William. Ohituslistat: todennäköisyyspohjainen vaihtoehto tasapainoisille puille  // Communications of the ACM  :  Journal. - 1990. - Kesäkuu ( nide 33 , nro 6 ). - s. 668-676 . doi : 10.1145 / 78973.78977 .

Kirjallisuus

  • William Pugh. Ohituslistat: Todennäköisyyspohjainen vaihtoehto tasapainoisille puille / Algoritmeja ja tietorakenteita käsittelevä työpaja. Springer Berlin Heidelberg, 1989; ACM CACM:n kotisivuarkiston kommunikaatiot Nide 33 Numero 6, kesäkuu 1990 Sivut 668-676 doi:10.1145/78973.78977  - alkuperäinen teos
  • Manning K., Raghavan P., Schütze H. Johdatus tiedonhakuun. - Williams , 2011. - 512 s. - ISBN 978-5-8459-1623-5 .

Linkit

 Tietorakenteet
Luettelot
puut
Laskee
muu