Pass list

A  kihagyási lista egy valószínűségi adatstruktúra , amely több párhuzamosan rendezett linkelt listán alapul , és a hatékonysága egy bináris fához hasonlítható (a legtöbb műveletnél O(log n) átlagos idő nagyságrendje).

A kihagyási lista egy rendezett linkelt lista kibővítésén alapul , további hivatkozásokkal, amelyeket véletlenszerű útvonalakon adnak hozzá geometriai /negatív binomiális eloszlással [1] , így a listakeresés gyorsan átugorhatja a lista egyes részeit. A beillesztés, a keresés és a törlés logaritmikus véletlenszerű időben történik.

Leírás

A kihagyási lista több rétegből áll. Az alsó réteg egy normál rendezett linkelt lista . Minden magasabb réteg egy "dedikált sávot" jelent az alábbi listák számára, ahol az i-edik réteg eleme az i+1-edik rétegben jelenik meg bizonyos p valószínűséggel (a p két leggyakrabban használt értéke  1 /2 és 1/ négy). Átlagosan minden elem 1/(1- p ) listákban fordul elő, a legfelső elem (általában a lista elején található speciális fejelem, hézagokkal) a listákban.

A kívánt elem keresése a felső lista head elemével kezdődik, és vízszintesen történik, amíg az aktuális elem nagyobb vagy egyenlő nem lesz, mint a cél. Ha az aktuális elem megegyezik a céllal, akkor a rendszer megtalálja. Ha az aktuális elem nagyobb, mint a cél, az eljárás megismétlődik, miután visszatért az előző elemhez, és függőlegesen ereszkedik le a következő alsó listára. Az egyes linkelt listákban a várható lépésszám 1/ p , ami a célelemtől visszanézve látható addig, amíg a következő magasabb listában megjelenő elemet el nem érjük. Így a keresés teljes várható költsége egyenlő p konstans esetén . A p különböző értékeinek kiválasztásával kiválasztható a szükséges kompromisszum a keresési idő költsége és a lista tárolásának memóriaköltsége között.

A megvalósítás részletei

A kihagyási listában használt elemek egynél több mutatót is tartalmazhatnak, így egynél több listában is szerepelhetnek.

A törlés és beszúrás műveletei nagyon hasonlóak a csatolt lista műveleteihez, azzal az eltéréssel, hogy a "high"-t egynél több csatolt listából kell beilleszteni vagy eltávolítani.

Véletlenszerűsítés nélkül azonban ezek a műveletek nagyon gyenge teljesítményt eredményeznének, mivel a listát teljesen meg kellene keverni egy új elem hozzáadásakor, hogy az átugrások száma állandó maradjon a legfelső szinten. William Pugh a következő algoritmust javasolta annak eldöntésére, hogy milyen magasra kell tolni egy új elemet. Ez az algoritmus csak helyi változtatásokat igényel a listán új elemek hozzáadásakor, és lehetővé teszi a "kifejezett vonalak" hatékonyságának mentését (l annak a szintnek a kapott értéke, amelyre az elemet el kívánja helyezni):

l = 1 míg véletlenszerű érték a [0,1] tartományban < p és l < maximum szint l = l + 1

Ennek eredményeként az elem bekerül az l-edik szintre, és ennek megfelelően minden l-nél kisebb szintre.

Azok az Θ(n) műveletek, amelyekkel növekvő sorrendben meg kell látogatnunk az egyes csomópontokat (pl. a teljes lista kinyomtatása), lehetőséget adnak a hiányos lista szintstruktúrájának finom derandomizálására optimális módon, elérve a linkelt lista keresési idejét. . (az i-edik végcsomópont 1-es szint kiválasztása plusz ahányszor oszthatjuk i-t 2-vel, amíg páratlanná válik. Szintén i=0 negatívan végtelen fejléc esetén, a szokásos speciális eset, amikor a lehető legmagasabb szintet választjuk negatív és/vagy pozitív végtelen csomópontok.) Ez azonban lehetővé teszi, hogy valaki megtudja, hol van az összes 1-nél nagyobb szintű csomópont, majd eltávolíthatja őket.

Alternatív megoldásként a szintstruktúrát kvázi véletlenszerűvé tehetjük a következő módon:

hozza létre az összes 1. szintű csomópontot j = 1 míg a j szinten lévő csomópontok száma > 1 minden i-edik csomópontra a j szinten ha páratlan vagyok ha i nem az utolsó csomópont a j szinten véletlenszerűen válassza ki, hogy j+1 szintre emeli-e másképp ne reklámozzák végfeltétel különben, ha még az i-1 csomópont sem kerül előléptetésre előrelép a j+1 szintre végfeltétel hurok vége for j = j + 1 ciklus vége egyelőre

Csakúgy, mint a derandomizált változat, a kvázi-randomizálás csak akkor történik meg, ha valamilyen más ok van a Θ(n) műveletek végrehajtására (amelyek minden csomópontot meglátogatnak).

Megvalósítási példa

C++ osztálykód std használatával :: swap ; sablon < típusnév KEY_T , típusnév DATA_T > class SkipList { size_t MaxLevel ; dupla SkipDivisor ; struct pár { KEY_T Kulcs ; DATA_T Adatok ; Pár * Előző ; Tömb < Pár *> Következő ; Pár ( const KEY_T & InKey , const DATA_T & InData , Pair * InPrevious , size_t InLevel ); Pár ( méret_t InLevel ); ~ pár (); Pair & operator = ( const Pair & InPair ); Pár * PreviousOnLevel ( size_t InLevel ); Pár * NextOnLevel ( size_t InLevel ); }; Pair Start ; Pár * NewPrevious ( konst KEY_T & InKey ); Pair * PairByKey ( konst KEY_T & InKey ); size_tNewLevel ( ); nyilvános : class Iterator { SkipList * CurrentList ; Pair * CurrentPair ; barát osztály SkipList < KEY_T , DATA_T > ; nyilvános : Iterátor ( const Iterator & InIterator ); Iterátor ( SkipList & InSkipList ); operátor bool (); Iterátor és operátor ++ (); Iterátor és operátor -- (); Iterátor operátor ++ ( int ); Iterátor operátor -- ( int ); Iterátor és operátor += ( méret_t n ); Iterátor és operátor -= ( méret_t n ); Iterátor & operátor = ( const Iterator & InIterator ); Iterátor & operátor = ( const KEY_T & InKey ); DATA_T & operátor * (); void Törlés (); }; SkipList ( size_t InNumberOfLanes = 3 , dupla InSkipDivisor = 1,0 / 4,0 ); ~ SkipList (); Iterátor GetBegin (); Iterátor GetEnd (); void Add ( const KEY_T & InKey , const DATA_T & InData ); void Delete ( const KEY_T & InKey ); DATA_T & operátor []( const KEY_T & InKey ); size_t Szám ( ); voidClear ( ); Iterátor keresés ( const DATA_T & Unknown ); bool IsEmpty (); }; sablon < típusnév KEY_T , típusnév DATA_T > típusnév SkipList < KEY_T , DATA_T >:: Pair * SkipList < KEY_T , DATA_T >:: Pair :: PreviousOnLevel ( size_t InLevel ){ ha ( ! ez ) return NULL ; Pár * Aktuális = Előző ; for (; Jelenlegi && ! ( Aktuális -> Következő . Számlálás () >= InLevel + 1 ); Aktuális = Aktuális -> Előző ){} visszatérés Áram ; } sablon < típusnév KEY_T , típusnév DATA_T > típusnév SkipList < KEY_T , DATA_T >:: Pair * SkipList < KEY_T , DATA_T >:: Pair :: NextOnLevel ( size_t InLevel ){ ha ( ! ez ) return NULL ; Pár * Aktuális = Következő [ InLevel -1 ]; for (; Jelenlegi && ! ( Aktuális -> Következő . Számlálás () >= InLevel + 1 ); Aktuális = Aktuális -> Következő [ InLevel -1 ]){} visszatérés Áram ; } sablon < típusnév KEY_T , típusnév 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 * InPrevious , size_t InLevel ) : Key ( InKey ), Data ( InusData ) ( Előző ){ Pár * Aktuális = Előző -> Következő [ 0 ]; Következő . AddLast ( Aktuális ); for ( méret_t Számláló = 1 ; Számláló <= InLevel ; Számláló ++ ){ Current = NextOnLevel ( Számláló ); Következő . AddLast ( Aktuális ); } jelenlegi = előző ; for ( méret_t Számláló = 0 ; Számláló <= InLevel ; Számláló ++ ) if ( Current = PreviousOnLevel ( Számláló )) Aktuális -> Következő [ Számláló ] = ez ; } sablon < típusnév KEY_T , típusnév DATA_T > SkipList < KEY_T , DATA_T >:: Pair :: Pair ( size_t InLevel ) : Previous ( NULL ){ for ( méret_t Számláló = 0 ; Számláló <= InLevel ; Számláló ++ ) Következő . AddLast ( NULL ); } sablon < típusnév KEY_T , típusnév DATA_T > SkipList < KEY_T , DATA_T >:: Pair ::~ Pár (){ size_t OurLevel = Következő . Szám () -1 ; Pár * Aktuális = ez ; for ( méret_t Számláló = 0 ; Számláló <= Saját szint ; Számláló ++ ) if ( Current = PreviousOnLevel ( Számláló )) Aktuális -> Következő [ Számláló ] = Következő [ Számláló ]; } sablon < típusnév KEY_T , típusnév DATA_T > SkipList < KEY_T , DATA_T >:: SkipList ( size_t InMaxLevel , double InSkipDivisor ) : MaxLevel ( InMaxLevel ), SkipDivisor ( InSkipDivisor ), Start ( MaxLevel ){} sablon < típusnév KEY_T , típusnév DATA_T > típusnév SkipList < KEY_T , DATA_T >:: Pair & SkipList < KEY_T , DATA_T >:: Pair :: operator = ( const SkipList < KEY_T , DATA_T >:: Pair & InPair ){ Kulcs = InPair . kulcs ; Adatok = InPair . adatok ; Előző = InPair . Előző ; size_t max = Következő . számolni (); for ( méret_t i ; i < max ; ++ i ) Következő . AddLast ( Következő [ i ]); return * this ; } sablon < típusnév KEY_T , típusnév DATA_T > SkipList < KEY_T , DATA_T >::~ SkipList (){ tiszta (); } sablon < típusnév KEY_T , típusnév DATA_T > típusnév SkipList < KEY_T , DATA_T >:: Pair * SkipList < KEY_T , DATA_T >:: NewPrevious ( const KEY_T & InKey ){ Pár * Előző =& Start ; Pár * Aktuális = Kezdés . Következő [ MaxLevel ]; for ( size_t Számláló = MaxLevel ; Számláló >= 0 ; Számláló -- ){ while ( Aktuális && InKey > Aktuális -> Kulcs ){ előző = aktuális ; Aktuális = Aktuális -> Következő [ Számláló ]; } ha ( ! Számláló ) szünet ; jelenlegi = előző ; }; visszatérés Előző ; } sablon < típusnév KEY_T , típusnév DATA_T > size_t SkipList < KEY_T , DATA_T >:: NewLevel (){ size_t Szint = 0 ; while ( rand () % 1000 < SkipDivisor * 1000 && Level <= MaxLevel ) ++ szint ; returnLevel ; _ } sablon < típusnév KEY_T , típusnév DATA_T > void SkipList < KEY_T , DATA_T >:: Add ( const KEY_T & InKey , const DATA_T & InData ){ Pár * Előző = ÚjElőző ( InKey ); Pár * Következő = Előző -> Következő [ 0 ]; if ( Következő && Következő -> Kulcs == InKey ) throw String ( "Nem egyedi kulcs!" ); new Pair ( InKey , InData , Previous , New Level ()); } sablon < típusnév KEY_T , típusnév DATA_T > típusnév SkipList < KEY_T , DATA_T >:: Pair * SkipList < KEY_T , DATA_T >:: PairByKey ( const KEY_T & InKey ){ Pár * Aktuális = ÚjElőző ( InKey ); if (( Aktuális = Aktuális -> Következő [ 0 ]) && Aktuális -> Kulcs == InKey ) visszatérés Áram ; throw String ( "Nincs pár ehhez a kulcshoz!" ); } sablon < típusnév KEY_T , típusnév DATA_T > void SkipList < KEY_T , DATA_T >:: Törlés ( const KEY_T & InKey ){ ha ( Üres ()) throw String ( "Van egy üres lista!" ); törölje PairByKey ( InKey ); } sablon < típusnév KEY_T , típusnév DATA_T > DATA_T & SkipList < KEY_T , DATA_T >:: operátor []( const KEY_T & InKey ){ ha ( Üres ()) throw String ( "A lista üres!" ); return PairByKey ( InKey ) -> Data ; } sablon < típusnév KEY_T , típusnév DATA_T > size_t SkipList < KEY_T , DATA_T >:: Szám (){ ha ( Üres ()) return 0 ; Pár * Következő = Kezdés . Következő [ 0 ]; méret_t n = 1 ; while ( Következő = Következő -> Következő [ 0 ]) n ++ ; return n ; } sablon < típusnév KEY_T , típusnév DATA_T > void SkipList < KEY_T , DATA_T >:: Törlés (){ Pár * Aktuális = Kezdés . Következő [ 1 ]; Pár * Előző = NULL ; while ( Aktuális ){ Aktuális -> Előző = NULL ; előző = aktuális ; Aktuális = Aktuális -> Következő [ 0 ]; törlés Előző ; } for ( méret_t i = 0 ; i <= Kezdés . Következő . Számlálás ( ) -1 ; i ++ ) kezdeni . Következő [ i ] = NULL ; } sablon < típusnév KEY_T , típusnév DATA_T > SkipList < KEY_T , DATA_T >:: Iterator :: Iterator ( const SkipList < KEY_T , DATA_T >:: Iterator & InIterator ) : CurrentList ( InIterator . CurrentList ), CurrentPair ( InIterator . CurrentPair ){} sablon < típusnév KEY_T , típusnév DATA_T > SkipList < KEY_T , DATA_T >:: Iterator :: Iterator ( SkipList < KEY_T , DATA_T >& InSkipList ) : CurrentList ( & InSkipList ), CurrentPair ( InSkipList . Start . Next [ 0 ]){} sablon < típusnév KEY_T , típusnév DATA_T > SkipList < KEY_T , DATA_T >:: Iterator :: operator bool (){ return CurrentList && CurrentPair ; } sablon < típusnév KEY_T , típusnév DATA_T > típusnév SkipList < KEY_T , DATA_T >:: Iterator & SkipList < KEY_T , DATA_T >:: Iterator :: operator ++ (){ if ( CurrentPair ) CurrentPair = CurrentPair -> Next [ 0 ]; return * this ; } sablon < típusnév KEY_T , típusnév DATA_T > típusnév SkipList < KEY_T , DATA_T >:: Iterator & SkipList < KEY_T , DATA_T >:: Iterator :: operator -- (){ if ( CurrentPair && CurrentPair != CurrentList -> Start . Next [ 0 ]) CurrentPair = CurrentPair -> Previous ; más CurrentPair = NULL ; return * this ; } sablon < típusnév KEY_T , típusnév DATA_T > típusnév SkipList < KEY_T , DATA_T >:: Iterator SkipList < KEY_T , DATA_T >:: Iterator :: operator ++ ( int ){ Iterator Old ( * this ); ++* ez ; return Old ; } sablon < típusnév KEY_T , típusnév DATA_T > típusnév SkipList < KEY_T , DATA_T >:: Iterator SkipList < KEY_T , DATA_T >:: Iterator :: operator -- ( int ){ Iterator Old ( * this ); --* ez ; return Old ; } sablon < típusnév KEY_T , típusnév DATA_T > típusnév SkipList < KEY_T , DATA_T >:: Iterator & SkipList < KEY_T , DATA_T >:: Iterator :: operator = ( const SkipList < KEY_T , DATA_T >:: Iterator & InIterator ){ CurrentList = InIterator . CurrentList ; CurrentPair = InIterator . Jelenlegi pár ; return * this ; } sablon < típusnév KEY_T , típusnév DATA_T > típusnév SkipList < KEY_T , DATA_T >:: Iterator & SkipList < KEY_T , DATA_T >:: Iterator :: operator = ( const KEY_T & InKey ){ CurrentPair = CurrentList -> PairByKey ( InKey ); return * this ; } sablon < típusnév KEY_T , típusnév DATA_T > DATA_T & SkipList < KEY_T , DATA_T >:: Iterátor :: operátor * (){ ha ( !* ez ) throw String ( "Olvasás rossz iterátorból!" ); return CurrentPair -> Data ; } sablon < típusnév KEY_T , típusnév DATA_T > void SkipList < KEY_T , DATA_T >:: Iterator :: Törlés (){ ha ( !* ez ) throw String ( "Rossz iterátor adatainak törlése!" ); törölje CurrentPair ; CurrentPair = NULL ; } sablon < típusnév KEY_T , típusnév DATA_T > típusnév SkipList < KEY_T , DATA_T >:: Iterator & SkipList < KEY_T , DATA_T >:: Iterator :: operator += ( size_t n ){ for ( méret_t Számláló = 0 ; Számláló < n && CurrentPair ; Számláló ++ ) CurrentPair = CurrentPair -> Next [ 0 ]; return * this ; } sablon < típusnév KEY_T , típusnév DATA_T > típusnév SkipList < KEY_T , DATA_T >:: Iterator & SkipList < KEY_T , DATA_T >:: Iterator :: operator -= ( size_t n ){ for ( méret_t Számláló = 0 ; Számláló < n && CurrentPair ; Számláló ++ ) CurrentPair = CurrentPair -> Previous ; if ( CurrentPair ==& CurrentList -> Start ) return * this ; } sablon < típusnév KEY_T , típusnév DATA_T > típusnév SkipList < KEY_T , DATA_T >:: Iterator SkipList < KEY_T , DATA_T >:: GetBegin (){ return Iterator ( * this ); } sablon < típusnév KEY_T , típusnév DATA_T > típusnév SkipList < KEY_T , DATA_T >:: Iterator SkipList < KEY_T , DATA_T >:: GetEnd (){ Iterátor ReturnValue ( * this ); ReturnValue += ReturnValue . CurrentList -> Count () -1 ; return ReturnValue ; } sablon < típusnév KEY_T , típusnév DATA_T > típusnév SkipList < KEY_T , DATA_T >:: Iterator SkipList < KEY_T , DATA_T >:: Find ( const DATA_T & Unknown ){ Iterátor eredménye ( * this ); while ( Eredmény && ! ( * Eredmény == Ismeretlen )) ++ eredmény ; vissza Eredmény ; } sablon < típusnév KEY_T , típusnév DATA_T > bool SkipList < KEY_T , DATA_T >:: IsEmpty (){ típusnév Tömb < Pár *>:: Iterátor i ( Start . Következő ); míg ( i ) ha ( * i ++ ) return false ; return true ; }

Jegyzetek

  1. ↑ Pugh, William. Skip lists: a kiegyensúlyozott fák valószínűségi alternatívája  // Communications of the ACM  :  Journal. - 1990. - június ( 33. évf. , 6. sz.). - P. 668-676 . doi : 10.1145 / 78973.78977 .

Irodalom

  • William Pugh. Kihagyó listák: A kiegyensúlyozott fák valószínűségi alternatívája / Algoritmusokról és adatstruktúrákról szóló workshop. Springer Berlin Heidelberg, 1989; Az ACM CACM honlapja archívumának közleményei, 33. évfolyam, 6. szám, 1990. június, 668-676 oldal doi:10.1145/78973.78977  - eredeti mű
  • Manning K., Raghavan P., Schütze H. Bevezetés az információkeresésbe. - Williams , 2011. - 512 p. - ISBN 978-5-8459-1623-5 .

Linkek

 Adatstruktúrák
Listák
fák
Számít
Egyéb