Lista de trecere

O  listă de ignorare este o structură de date probabilistică bazată pe mai multe liste conectate sortate în paralel cu o eficiență comparabilă cu un arbore binar (de ordinul timpului mediu O(log n) pentru majoritatea operațiunilor).

O listă de ignorare se bazează pe extinderea unei liste sortate cu legături suplimentare adăugate în căi aleatorii cu o distribuție binomială geometrică /negativă [1] , astfel încât o căutare în listă să poată sări rapid părți din listă. Inserarea, căutarea și ștergerea sunt efectuate în timp aleatoriu logaritmic.

Descriere

O listă sărită este formată din mai multe straturi. Stratul de jos este o listă normală ordonată . Fiecare strat superior reprezintă o „bandă dedicată” pentru listele de mai jos, unde elementul din stratul i apare în stratul i+1 cu o probabilitate fixă ​​p (cele două valori cele mai frecvent utilizate pentru p  sunt 1 /2 și 1/ patru). În medie, fiecare element apare în liste 1/(1 - p ), iar elementul de sus (de obicei, elementul principal special de la începutul listei cu goluri) în liste.

Căutarea elementului dorit începe cu elementul cap al listei de sus și se efectuează pe orizontală până când elementul curent este mai mare sau egal cu ținta. Dacă elementul curent este egal cu ținta, acesta este găsit. Dacă elementul curent este mai mare decât ținta, procedura se repetă după revenirea la elementul anterior și coborând vertical în jos până la următoarea listă inferioară. Numărul așteptat de pași în fiecare listă legată este 1/ p , care poate fi văzut privind înapoi de la elementul țintă până când este atins elementul care apare în lista următoare. Astfel, costul total așteptat al căutării este egal cu în cazul unei constante p . Alegând diferite valori ale lui p , este posibil să alegeți compromisul necesar între costul timpului de căutare și costul memoriei stocării listei.

Detalii de implementare

Elementele utilizate într-o listă de ignorare pot conține mai mult de un indicator, deci pot fi în mai multe liste.

Operațiile de ștergere și inserare sunt implementate în mod foarte similar cu operațiunile lor cu listele legate, cu excepția faptului că „high” trebuie inserat sau eliminat din mai multe liste legate.

Cu toate acestea, fără randomizare, aceste operațiuni ar avea ca rezultat o performanță foarte slabă, deoarece lista ar trebui să fie complet amestecată atunci când a fost adăugat un nou element pentru a menține constant numărul de sărituri la nivelul superior. William Pugh a propus următorul algoritm pentru a decide cât de sus ar trebui să fie împins un nou element. Acest algoritm necesită doar modificări locale ale listei atunci când adăugați elemente noi și vă permite să salvați eficiența „liniilor exprese” (l este valoarea rezultată a nivelului la care doriți să plasați elementul):

l = 1 în timp ce valoare aleatorie în intervalul [0,1] < p și l < nivelul maxim l = l + 1

Ca urmare, elementul este inserat la nivelul l-lea și, în consecință, la toate nivelurile mai mici de l.

Operațiile Θ(n) de care avem nevoie pentru a vizita fiecare nod în ordine crescătoare (de exemplu, tipărirea întregii liste) oferă o oportunitate de a derandomiza subtil structura de nivel a listei lipsite într-un mod optim, atingând timpul de căutare pentru lista legată. . (alegând nivelul 1 al nodului final i-lea plus numărul de ori în care putem împărți i cu 2 până devine impar. De asemenea, i=0 pentru un antet infinit infinit așa cum avem, cazul special obișnuit, alegând cel mai înalt nivel posibil pentru noduri infinite negative și/sau pozitive.) Cu toate acestea, acest lucru permite cuiva să știe unde sunt toate nodurile cu nivel mai mare de 1 și apoi să le elimine.

Alternativ, putem face structura nivelurilor cvasialeatoare în următorul mod:

creați toate nodurile de nivel 1 j = 1 în timp ce numărul de noduri la nivelul j > 1 pentru fiecare i-lea nod la nivelul j daca sunt ciudat dacă i nu este ultimul nod din nivelul j alegeți aleatoriu dacă îl promovați la nivelul j+1 in caz contrar nu promovați starea finală altfel, dacă i chiar nodul i-1 nu este promovat avansa-l la nivelul j+1 starea finală sfârşitul buclei pentru j = j + 1 sfârşitul ciclului deocamdată

La fel ca versiunea derandomizată, cvasi-randomizarea se face numai atunci când există un alt motiv pentru a efectua operații Θ(n) (care vor vizita fiecare nod).

Exemplu de implementare

Cod de clasă C++ folosind std :: swap ; șablon < nume de tip KEY_T , nume de tip DATA_T > clasa SkipList { size_t MaxLevel ; SkipDivisor dublu ; struct Pair { KEY_T Cheie ; DATA_T Date ; Pereche * Anterior ; Array < Pereche *> Următorul ; Pair ( const KEY_T & InKey , const DATA_T & InData , Pair * InPrevious , size_t InLevel ); Pereche ( size_t InLevel ); ~ pereche (); Pair & operator = ( const Pair & InPair ); Pereche * PreviousOnLevel ( size_t InLevel ); Pereche * NextOnLevel ( size_t InLevel ); }; Start pereche ; Pereche * NewPrevious ( const KEY_T & InKey ); Pair * PairByKey ( const KEY_T & InKey ); size_tNewLevel ( ); public : Iterator de clasă { SkipList * CurrentList ; Pereche * CurrentPair ; clasa prieten SkipList < KEY_T , DATA_T > ; public : Iterator ( const Iterator & InIterator ); Iterator ( SkipList & InSkipList ); operator bool (); Iterator și operator ++ (); Iterator și operator -- (); Operator iterator ++ ( int ); Operator iterator -- ( int ); Iterator & operator += ( size_t n ); Iterator & operator -= ( size_t n ); Iterator & operator = ( const Iterator & InIterator ); Iterator & operator = ( const KEY_T & InKey ); DATA_T & operator * (); void Șterge (); }; SkipList ( size_t InNumberOfLanes = 3 , dublu InSkipDivisor = 1.0 / 4.0 ); ~ SkipList (); Iterator GetBegin (); Iterator GetEnd (); void Add ( const KEY_T & InKey , const DATA_T & InData ); void Delete ( const KEY_T & InKey ); DATA_T & operator []( const KEY_T & InKey ); size_t Count (); voidClear ( ); Iterator Find ( const DATA_T & Unknown ); bool IsEmpty (); }; șablon < nume de tip KEY_T , nume de tip DATA_T > typename SkipList < KEY_T , DATA_T >:: Pair * SkipList < KEY_T , DATA_T >:: Pair :: PreviousOnLevel ( size_t InLevel ){ dacă ( ! asta ) returnează NULL ; Pereche * Curent = Anterior ; pentru (; Current && ! ( Current -> Next . Count () >= InLevel + 1 ); Current = Current -> Previous ){} return Curent ; } șablon < nume de tip KEY_T , nume de tip DATA_T > typename SkipList < KEY_T , DATA_T >:: Pair * SkipList < KEY_T , DATA_T >:: Pair :: NextOnLevel ( size_t InLevel ){ dacă ( ! asta ) returnează NULL ; Pereche * Current = Următorul [ InLevel -1 ]; pentru (; Current && ! ( Current -> Next . Count () >= InLevel + 1 ); Current = Current -> Next [ InLevel -1 ]){} return Curent ; } șablon < nume de tip KEY_T , nume de tip DATA_T > SkipList < KEY_T , DATA_T >:: Pair :: Pair ( const KEY_T & InKey , const DATA_T & InData , SkipList < KEY_T , DATA_T >:: Pair * InPrevious , size_t InLevel ) : Key ( InKey ), Data ( InKey ), Data ( Interior ) ( ÎnAnterior ){ Pereche * Current = Anterior -> Următorul [ 0 ]; Următorul . AddLast ( Curent ); pentru ( size_t Counter = 1 ; Counter <= InLevel ; Counter ++ ){ Curent = NextOnLevel ( Counter ); Următorul . AddLast ( Curent ); } curent = anterior ; pentru ( size_t Counter = 0 ; Counter <= InLevel ; Counter ++ ) if ( Current = PreviousOnLevel ( Counter )) Current -> Next [ Counter ] = this ; } șablon < nume de tip KEY_T , nume de tip DATA_T > SkipList < KEY_T , DATA_T >:: Pair :: Pair ( size_t InLevel ) : Previous ( NULL ){ pentru ( size_t Counter = 0 ; Counter <= InLevel ; Counter ++ ) Următorul . AddLast ( NULL ); } șablon < nume de tip KEY_T , nume de tip DATA_T > SkipList < KEY_T , DATA_T >:: Pair ::~ Pair (){ size_t OurLevel = Următorul . Număr () -1 ; Pereche * Curent = aceasta ; pentru ( size_t Counter = 0 ; Counter <= OurLevel ; Counter ++ ) if ( Current = PreviousOnLevel ( Counter )) Current -> Next [ Counter ] = Next [ Counter ]; } șablon < nume de tip KEY_T , nume de tip DATA_T > SkipList < KEY_T , DATA_T >:: SkipList ( size_t InMaxLevel , double InSkipDivisor ) : MaxLevel ( InMaxLevel ), SkipDivisor ( InSkipDivisor ), Start ( MaxLevel ){} șablon < nume de tip KEY_T , nume de tip DATA_T > typename SkipList < KEY_T , DATA_T >:: Pair & SkipList < KEY_T , DATA_T >:: Pair :: operator = ( const SkipList < KEY_T , DATA_T >:: Pair & InPair ){ Cheie = InPair . cheie ; Date = InPair . date ; Previous = InPair . Anterior ; size_t max = Următorul . numără (); pentru ( dimensiunea_t i ; i < max ; ++ i ) Următorul . AddLast ( Următorul [ i ]); returneaza * asta ; } șablon < nume de tip KEY_T , nume de tip DATA_T > SkipList < KEY_T , DATA_T >::~ SkipList (){ clar (); } șablon < nume de tip KEY_T , nume de tip DATA_T > typename SkipList < KEY_T , DATA_T >:: Pair * SkipList < KEY_T , DATA_T >:: NewPrevious ( const KEY_T & InKey ){ Pereche * Anterior =& Start ; Pereche * Current = Start . Următorul [ MaxLevel ]; pentru ( size_t Counter = MaxLevel ; Counter >= 0 ; Counter -- ){ while ( Current && InKey > Current -> Key ){ precedent = curent ; Current = Current -> Next [ Counter ]; } dacă ( ! Contor ) rupe ; curent = anterior ; }; revenire Anterior ; } șablon < nume de tip KEY_T , nume de tip DATA_T > size_t SkipList < KEY_T , DATA_T >:: NewLevel (){ size_t Level = 0 ; while ( rand () % 1000 < SkipDivisor * 1000 && Nivel <= MaxLevel ) Nivel ++ ; returnLevel ; _ } șablon < nume de tip KEY_T , nume de tip DATA_T > void SkipList < KEY_T , DATA_T >:: Add ( const KEY_T & InKey , const DATA_T & InData ){ Pereche * Previous = NewPrevious ( InKey ); Pereche * Următorul = Anterior -> Următorul [ 0 ]; if ( Următorul && Următorul -> Tasta == InKey ) throw String ( „Nu cheie unică!” ); pereche nouă ( InKey , InData , Previous , NewLevel ()); } șablon < nume de tip KEY_T , nume de tip DATA_T > typename SkipList < KEY_T , DATA_T >:: Pair * SkipList < KEY_T , DATA_T >:: PairByKey ( const KEY_T & InKey ){ Pereche * Current = NewPrevious ( InKey ); if (( Current = Current -> Next [ 0 ]) && Current -> Key == InKey ) return Curent ; throw String ( "Nici o pereche pentru această cheie!" ); } șablon < nume de tip KEY_T , nume de tip DATA_T > void SkipList < KEY_T , DATA_T >:: Delete ( const KEY_T & InKey ){ dacă ( Este gol ()) throw String ( "Există o listă goală!" ); ștergeți PairByKey ( InKey ); } șablon < nume de tip KEY_T , nume de tip DATA_T > DATA_T & SkipList < KEY_T , DATA_T >:: operator []( const KEY_T & InKey ){ dacă ( Este gol ()) throw String ( "Lista este goală!" ); returnează PairByKey ( InKey ) -> Date ; } șablon < nume de tip KEY_T , nume de tip DATA_T > size_t SkipList < KEY_T , DATA_T >:: Count (){ dacă ( Este gol ()) returnează 0 ; Pereche * Următorul = Start . Următorul [ 0 ]; dimensiunea_t n = 1 ; în timp ce ( Următorul = Următorul -> Următorul [ 0 ]) n ++ ; întoarcere n ; } șablon < nume de tip KEY_T , nume de tip DATA_T > void SkipList < KEY_T , DATA_T >:: Clear (){ Pereche * Current = Start . Următorul [ 1 ]; Pereche * Anterior = NULL ; în timp ce ( Curent ){ Curent -> Anterior = NULL ; precedent = curent ; Current = Current -> Next [ 0 ]; şterge Previous ; } pentru ( size_t i = 0 ; i <= Start . Next . Count () -1 ; i ++ ) începe . Următorul [ i ] = NULL ; } șablon < nume de tip KEY_T , nume de tip DATA_T > SkipList < KEY_T , DATA_T >:: Iterator :: Iterator ( const SkipList < KEY_T , DATA_T >:: Iterator & InIterator ) : CurrentList ( InIterator . CurrentList ), CurrentPair ( InIterator . CurrentPair ){} șablon < nume de tip KEY_T , nume de tip DATA_T > SkipList < KEY_T , DATA_T >:: Iterator :: Iterator ( SkipList < KEY_T , DATA_T >& InSkipList ) : CurrentList ( & InSkipList ), CurrentPair ( InSkipList . Start . Next [ 0 ]){} șablon < nume de tip KEY_T , nume de tip DATA_T > SkipList < KEY_T , DATA_T >:: Iterator :: operator bool (){ return CurrentList && CurrentPair ; } șablon < nume de tip KEY_T , nume de tip DATA_T > typename SkipList < KEY_T , DATA_T >:: Iterator & SkipList < KEY_T , DATA_T >:: Iterator :: operator ++ (){ dacă ( Perechea curentă ) CurrentPair = CurrentPair -> Următorul [ 0 ]; returneaza * asta ; } șablon < nume de tip KEY_T , nume de tip DATA_T > typename SkipList < KEY_T , DATA_T >:: Iterator & SkipList < KEY_T , DATA_T >:: Iterator :: operator -- (){ if ( Perechea curentă && Perechea curentă != Listă curentă -> Începe . Următorul [ 0 ]) CurrentPair = CurrentPair -> Previous ; altfel CurrentPair = NULL ; returneaza * asta ; } șablon < nume de tip KEY_T , nume de tip DATA_T > typename SkipList < KEY_T , DATA_T >:: Iterator SkipList < KEY_T , DATA_T >:: Iterator :: operator ++ ( int ){ Iterator Vechi ( * asta ); ++** asta ; intoarce Vechi ; } șablon < nume de tip KEY_T , nume de tip DATA_T > typename SkipList < KEY_T , DATA_T >:: Iterator SkipList < KEY_T , DATA_T >:: Iterator :: operator -- ( int ){ Iterator Vechi ( * asta ); --* asta ; intoarce Vechi ; } șablon < nume de tip KEY_T , nume de tip DATA_T > typename 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 . Perechea curentă ; returneaza * asta ; } șablon < nume de tip KEY_T , nume de tip DATA_T > typename SkipList < KEY_T , DATA_T >:: Iterator & SkipList < KEY_T , DATA_T >:: Iterator :: operator = ( const KEY_T & InKey ){ CurrentPair = CurrentList -> PairByKey ( InKey ); returneaza * asta ; } șablon < nume de tip KEY_T , nume de tip DATA_T > DATA_T & SkipList < KEY_T , DATA_T >:: Iterator :: operator * (){ dacă ( !* asta ) throw String ( "Citind de la un iterator prost!" ); returnează CurrentPair -> Date ; } șablon < nume de tip KEY_T , nume de tip DATA_T > void SkipList < KEY_T , DATA_T >:: Iterator :: Delete (){ dacă ( !* asta ) throw String ( "Ștergerea datelor iteratorului prost!" ); șterge CurrentPair ; CurrentPair = NULL ; } șablon < nume de tip KEY_T , nume de tip DATA_T > typename SkipList < KEY_T , DATA_T >:: Iterator & SkipList < KEY_T , DATA_T >:: Iterator :: operator += ( size_t n ){ pentru ( size_t Counter = 0 ; Counter < n && CurrentPair ; Counter ++ ) CurrentPair = CurrentPair -> Următorul [ 0 ]; returneaza * asta ; } șablon < nume de tip KEY_T , nume de tip DATA_T > typename SkipList < KEY_T , DATA_T >:: Iterator & SkipList < KEY_T , DATA_T >:: Iterator :: operator -= ( size_t n ){ pentru ( size_t Counter = 0 ; Counter < n && CurrentPair ; Counter ++ ) CurrentPair = CurrentPair -> Previous ; if ( CurrentPair ==& CurrentList -> Start ) returneaza * asta ; } șablon < nume de tip KEY_T , nume de tip DATA_T > typename SkipList < KEY_T , DATA_T >:: Iterator SkipList < KEY_T , DATA_T >:: GetBegin (){ return Iterator ( * this ); } șablon < nume de tip KEY_T , nume de tip 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 ; } șablon < nume de tip KEY_T , nume de tip DATA_T > typename SkipList < KEY_T , DATA_T >:: Iterator SkipList < KEY_T , DATA_T >:: Find ( const DATA_T & Unknown ){ Rezultat Iterator ( * this ); while ( Rezultat && ! ( * Rezultat == Necunoscut )) ++ rezultat ; returnează rezultat ; } șablon < nume de tip KEY_T , nume de tip DATA_T > bool SkipList < KEY_T , DATA_T >:: IsEmpty (){ typename Array < Pereche *>:: Iterator i ( Start . Next ); în timp ce ( i ) dacă ( * i ++ ) returnează fals ; returnează adevărat ; }

Note

  1. ↑ Pugh, William. Liste de ignorare: o alternativă probabilistică la arbori echilibrați  // Comunicarea ACM  :  jurnal. - 1990. - Iunie ( vol. 33 , nr. 6 ). - P. 668-676 . doi : 10.1145 / 78973.78977 .

Literatură

  • William Pugh. Omite liste: o alternativă probabilistică la arbori echilibrați / Atelier de lucru despre algoritmi și structuri de date. Springer Berlin Heidelberg, 1989; Comunicări ale arhivei ACM CACM Homepage Volumul 33 Numărul 6, iunie 1990 Paginile 668-676 doi:10.1145/78973.78977  - lucrare originală
  • Manning K., Raghavan P., Schütze H. Introduction to information retriever. - Williams , 2011. - 512 p. - ISBN 978-5-8459-1623-5 .

Link -uri

 Structuri de date
Liste
Copaci
Contează
Alte