Omite liste: o alternativă probabilistică la arborii echilibrați. Încă o dată despre skiplist... Distribuția neuniformă a cererilor
Un tip interesant de structură de date pentru o implementare eficientă a dicționarului ordonat ADT este skip^cnucoK (skip list). Această structură de date organizează obiectele într-o ordine aleatorie, astfel:
astfel încât căutarea și actualizarea sunt finalizate în medie în timp 0(log n), unde n este numărul de obiecte din dicționar. În mod interesant, conceptul de complexitate medie a timpului utilizat aici nu depinde de distribuția posibilă a cheilor în intrare. Dimpotrivă, este dictată de utilizarea generatoarelor de numere aleatorii în implementarea procesului de intrare pentru a facilita procesul de decizie unde să insereze un nou obiect. Timpul de execuție în acest caz va fi egal cu media timpului de execuție al introducerii oricăror numere aleatorii utilizate ca obiecte de intrare.
Metodele de generare a numerelor aleatoare sunt încorporate în majoritatea computerelor moderne, deoarece sunt utilizate pe scară largă în jocurile pe calculator, criptografie și simulări pe computer. Unele metode, numite generatoare de numere pseudoaleatoare, generează numere pseudoaleatoare conform unor legi, pornind de la așa-numita sămânță. Alte metode folosesc hardware pentru a extrage numere „cu adevărat” aleatorii. În ambele cazuri, computerul are numere care îndeplinesc cerințele pentru numere aleatorii în analiza dată.
Principalul avantaj al utilizării numerelor aleatoare în structura de date și în crearea unui algoritm este simplitatea și fiabilitatea structurilor și metodelor rezultate. În acest fel, este posibil să se creeze o structură simplă de date randomizate numită o listă de ignorare, care oferă un cost de timp de căutare logaritmic similar cu cel al unui algoritm de căutare binar. Cu toate acestea, costul de timp estimat al unei liste de ignorare va fi mai mare decât cel al unei căutări binare într-un tabel de căutare. Pe de altă parte, atunci când actualizați un dicționar, o listă de ignorare este mult mai rapidă decât tabelele de căutare.
Fie ca lista de ignorare S pentru dicționarul D să fie formată dintr-o serie de liste (iSo, S\, Si, З/j). Fiecare listă S\ stochează un set de obiecte dicționar D după taste în ordine nedescrescătoare, plus obiecte cu două chei speciale, scrise ca „-oo” și „+oo”, unde „-oo” înseamnă mai puțin și „+oo” înseamnă mai mult decât orice cheie posibilă care poate fi în D. În plus, listele din S îndeplinesc următoarele cerințe:
Lista S 0 conține fiecare obiect al dicționarului D (plus obiecte speciale cu tastele „-oo” și „+oo”);
Pentru / = 1, …, h – 1, lista Si conține (în plus față de „-oo” și „+oo”) un set de obiecte generat aleatoriu din lista S t _ ь
Lista S h conține doar „-oo” și „+oo”.
Un exemplu de astfel de listă de ignorare este prezentat în Fig. 8.9, care reprezintă vizual lista S cu o listă la bază și listează S\, ..., S^ deasupra. Notăm înălțimea listei S ca h.
Orez. 8.9. exemplu de listă sărită
Intuitiv, listele sunt organizate astfel; astfel încât?/+/ conţine cel puţin fiecare al doilea obiect 5/. După cum se va arăta când se analizează metoda de introducere, obiectele din St+\ sunt selectate aleatoriu dintre obiectele din Si, astfel încât fiecare obiect selectat 5/ să fie inclus în 5/ + \ cu probabilitatea 1/2. Figurat vorbind, dacă să plasați sau nu un obiect din Si + 1 este determinat în funcție de partea pe care aterizează moneda aruncată - capete sau cozi. Astfel, putem presupune că S\ conține aproximativ n/2 obiecte, S2 - n/4 și, în consecință, Sj - aproximativ n/2′ obiecte. Cu alte cuvinte, înălțimea h a listei S poate fi aproximativ logn. Deși, înjumătățirea numărului de obiecte de la o listă la alta nu este o cerință obligatorie sub forma unei proprietăți explicite skip-list. Dimpotrivă, selecția aleatorie este mai importantă.
Folosind abstracția pozițională aplicată listelor și arborilor, ne putem gândi la o listă de ochiuri ca la o colecție bidimensională de poziții, organizate orizontal în niveluri și vertical în turnuri. Fiecare nivel este o listă S^ și fiecare turn este un set de poziții care stochează același obiect și sunt situate unul peste altul în liste. Pozițiile listei de ignorare pot fi parcurse utilizând următoarele operații:
după(/?): returnează poziția de lângă același nivel; before(/?): returnează poziția care precede p la același nivel; dedesubt(/?): returnează poziția situată sub p în același turn; deasupra(/?): returnează poziția de deasupra p în același turn.
Să stabilim că operațiunile de mai sus trebuie să returneze null dacă poziția solicitată nu există. Fără a intra în detalii, rețineți că o listă de ignorare poate fi implementată cu ușurință folosind o structură conectată în așa fel încât metodele de trecere necesită timp 0(1) (dacă există poziția p în listă). O astfel de structură conectată este o colecție de h liste dublu legate, care sunt la rândul lor liste dublu legate.
Structura listei de ignorare permite aplicarea unor algoritmi simpli de căutare dicționarelor. De fapt, toți algoritmii de căutare în lista de omitere se bazează pe metoda SkipSearch destul de elegantă, care preia o cheie și găsește obiectul din lista de omitere S cu cea mai mare cheie (care poate fi „-oo”) mai mică sau egală. la k. Să presupunem că avem cheia dorită pentru Metoda SkipSearch setează poziția lui p în poziția din stânga sus în lista de omitere S. Adică p este setată la poziția obiectului special cu tasta „-oo " în S^. Apoi se face următoarele:
1) dacă S.below(/?) este nul, atunci căutarea se termină - cel mai mare obiect din S cu o cheie mai mică sau egală cu cheia dorită k se găsește la nivelul de mai jos. În caz contrar, coborâm un nivel în acest turn, aşezând p S.be \ow(p);
2) din poziția p ne deplasăm la dreapta (înainte) până ne găsim în poziția extremă dreaptă a nivelului curent, unde keu(/?)< к. Такой шаг называется сканированием вперед (scan forward). Указанная позиция существует всегда, поскольку каждый уровень имеет специальные ключи «+оо» и «-оо». И на самом деле, после шага вправо по текущему уровню р может остаться на исходном месте. В любом случае после этого снова повторяется предыдущее действие.
Orez. 8.10. Un exemplu de căutare într-o listă de ignorare. Cele 50 de poziții examinate în timpul căutării cheilor sunt evidențiate cu o desemnare întreruptă
Fragmentul de cod 8.4 conține o descriere a algoritmului de căutare a listei de ignorare. Având o astfel de metodă, este ușor de implementat operația findElement(/:). Operația p^-SkipSearch(A;) este efectuată și se verifică cheia de egalitate(p)~ k. Dacă ^ este egal, /?.element este returnat. În caz contrar, este returnat un mesaj de semnalizare NO_SUCH_KEY.
Algoritmul SkipSearch(/:):
Intrare: tasta de căutare.
Ieșire: poziția p în S al cărei obiect are cea mai mare cheie mai mică sau egală cu k.
Să presupunem că p este poziția din stânga sus în S (constând din cel puțin două niveluri), în timp ce sub (p) * null do
р de mai jos (p) (scanați în jos) tasta while (după (p))< к do
Fie p după(p) (scanare înainte) întoarce p
Fragment de cod 8.4. Algoritm de căutare în lista de omitere S
Se pare că timpul de execuție estimat al algoritmului SkipSearch este 0(log n). Înainte de a justifica acest lucru, vă prezentăm implementarea metodelor de actualizare a listelor de ignorare
OCOLIRE este un sistem de monitorizare a executării comenzilor bazat pe MS SharePoint, care vă permite să automatizați complet procesul de lucru cu comenzile. Aceasta este o soluție atentă și ieșită din cutie pentru organizarea muncii cu comisioane. Este potrivit pentru lucrul atât în companii mari și distribuite geografic, cât și pentru companii mijlocii datorită posibilității de a oferi cea mai flexibilă configurație a tuturor modulelor.
Sistemul SKIP se bazează pe platforma Microsoft SharePoint, ceea ce înseamnă automat că poate fi integrat cu produsele Microsoft, inclusiv Microsoft Office.
Funcționalitatea sistemului
Sistemul SKIP este o soluție „cutie” și în această versiune conține un set de bază de funcționalități necesare automatizării lucrărilor cu comenzi:
- Atribuirea, executarea, controlul instrucțiunilor;
- Urmărirea stării de executare a comenzii;
- Abilitatea de a crea comenzi imbricate („copil”).
Lista de instrucțiuni cu indicație de culoare 
În același timp, funcționalitatea prezentată este implementată astfel încât să ofere utilizatorului cele mai largi posibilități posibile de lucru cu sistemul:
- Catalogarea comenzilor (o comandă poate fi localizată în dosare diferite);
- Filtrarea listelor de comenzi;
- Exportați liste de comenzi în MS Excel;
- Rapoarte de disciplină de performanță;
- Indicarea culorii comenzilor in functie de timpul de executie si starea comenzii;
- Posibilitatea atașării unui număr arbitrar de fișiere de orice format la Cardul de Comandă;
- Integrare cu calendarele Outlook;
- Notificări personalizabile despre atribuirea și progresul lucrării cu comanda;
- Sistem de înlocuire a angajaților în vacanțe sau călătorii de afaceri;
- Crearea de comenzi periodice (sau comenzi cu program) pentru evenimente care au o anumita perioada (intalniri, intalniri etc.);
- Afișarea termenelor limită pentru finalizarea comenzilor pe o diagramă Gantt;
- Și așa mai departe
Lista sarcinilor cu diagrama Gantt 
Imaginează-ți că colegul tău plângăcios a venit să vorbească despre sarcina lui dificilă - nu trebuie doar să sorteze un set de numere întregi în ordine crescătoare, ci să scoată toate elementele mulțimii ordonate de la L la R inclusiv!
Ați afirmat că aceasta este o sarcină elementară și că vă va lua zece minute pentru a scrie o soluție în C#. Ei bine, sau o oră. Sau două. Sau baton de ciocolată Alyonka
Se presupune că în set sunt permise duplicate, iar numărul de elemente nu va fi mai mare de 10^6.
Există mai multe comentarii cu privire la evaluarea soluției:
Codul dvs. va fi evaluat și testat de trei programatori:Soluția poate fi foarte interesantă, așa că am crezut că este necesar să o descriu.
- Bill va rula soluția dvs. pe teste nu mai mari de 10 Kb.
- În testele lui Stephen, numărul de solicitări nu va fi mai mare de 10^5, în timp ce numărul de solicitări de adăugare nu va depăși 100.
- În testele lui Mark, numărul de solicitări nu va fi mai mare de 10^5.
Soluţie
Să avem un depozit abstract.Să notăm Add(e) - adăugarea unui element în magazin și Range(l, r) - luarea unei felii de la l la r elemente.
O opțiune de stocare banală ar putea fi astfel:
- Baza stocării va fi o matrice dinamică ordonată în ordine crescătoare.
- La fiecare inserare, o căutare binară găsește poziția în care trebuie inserat elementul.
- Când se solicită Range(l, r), pur și simplu vom lua o porțiune din matrice de la l la r.
C Range(l, r) - luarea unei felii poate fi estimată ca O(r - l).
C Add(e) - inserarea în cel mai rău caz va funcționa în O(n), unde n este numărul de elemente. La n ~ 10^6, inserția este blocajul. Mai jos în articol va fi propusă o opțiune de stocare îmbunătățită.
Un exemplu de cod sursă poate fi vizualizat.
Skiplist
Skiplist este o alternativă aleatorie la arborele de căutare care se bazează pe mai multe liste conectate. A fost inventat de William Pugh în 1989. Operațiile de căutare, inserare și ștergere sunt efectuate în timp aleatoriu logaritmic.Această structură de date nu este cunoscută pe scară largă (apropo, pe Habré este scrisă o recenzie despre ea), deși are estimări asimptotice bune. Din curiozitate, am vrut să o implementez, mai ales că aveam o sarcină potrivită.
Să presupunem că avem o listă sortată cu legături unice:
În cel mai rău caz, căutarea se efectuează în O(n). Cum poate fi accelerat?
Într-una dintre prelegerile video pe care le-am urmărit în timp ce lucram la problemă, a existat un exemplu minunat despre liniile expres în New York:
- Liniile expres conectează unele stații
- Liniile obișnuite leagă toate stațiile
- Există linii regulate între stațiile comune ale liniilor de mare viteză
Exemplul arată o SkipList ideală, în realitate totul arată similar, dar puțin diferit :)
Căutare
Așa se întâmplă căutarea. Să presupunem că căutăm al 72-lea element:
Introduce
Cu inserția, totul este puțin mai complicat. Pentru a insera un element, trebuie să înțelegem unde să-l inserăm în lista cea mai de jos și, în același timp, să-l împingem la un anumit număr de niveluri superioare. Dar prin câte niveluri ar trebui să fie împins fiecare element specific?Se propune să rezolvăm astfel: la introducere, adăugăm un nou element la nivelul cel mai de jos și începem să aruncăm o monedă, până când aceasta cade, împingem elementul la nivelul următor superior.
Să încercăm să inserăm elementul - 67. Mai întâi, să găsim unde trebuie inserat în lista de bază:
Am presupus că moneda a căzut de două ori la rând. Aceasta înseamnă că trebuie să împingeți elementul în sus două niveluri:
Acces prin index
Pentru a accesa prin index, se propune să faceți următoarele: marcați fiecare tranziție cu numărul de noduri care se află sub ea:
Odată ce obținem acces la elementul i (apropo, îl obținem în O(ln n)), a face o felie nu pare dificilă.
Fie necesar să găsim Range(5, 7). Mai întâi obținem elementul de la indicele cinci:
Și acum Range(5, 7):
Despre implementare
Pare o implementare naturală ca nodul SkipList să arate astfel:SkipListNode(De fapt, asta s-a făcut.
int Element;
SkipListNodeNext;
int Lățimea;
}
Dar în C#, matricea își stochează și lungimea și am vrut să fac asta în cât mai puțină memorie posibil (după cum s-a dovedit, în condițiile problemei totul nu a fost evaluat atât de strict). În același timp, am vrut să mă asigur că implementarea SkipList și a arborelui RB extins ocupă aproximativ aceeași cantitate de memorie.
Răspunsul la modul de reducere a consumului de memorie a fost găsit în mod neașteptat la o inspecție mai atentă din pachetul java.util.concurrent.
Skiplist 2D
Să existe o listă unică a tuturor elementelor dintr-o singură dimensiune. Al doilea va conține „linii exprese” pentru tranziții cu legături către nivelul inferior.ListNode(
int Element;
ListNodeNext;
}BANDĂ (
Lane dreapta;
Lane Down;
Nodul ListNode;
}
Monedă necinstită
De asemenea, puteți utiliza o monedă „necinstită” pentru a reduce consumul de memorie: reduceți probabilitatea de a împinge un element la nivelul următor. Articolul lui William Pugh a analizat o secțiune transversală a mai multor valori ale probabilității de împingere. Luând în considerare valorile de ½ și ¼, în practică, s-a obținut aproximativ același timp de căutare, reducând în același timp consumul de memorie.Câteva despre generarea numerelor aleatorii
Săpând în curajul lui ConcurrentSkipListMap, am observat că numerele aleatoare sunt generate după cum urmează:int randomLevel() (Puteți citi mai multe despre generarea numerelor pseudoaleatoare folosind XOR în acest articol. Nu am observat o creștere specială a vitezei, așa că nu am folosit-o.
int x = randomSeed;
x ^= x<< 13;
x ^= x >>> 17;
randomSeed = x ^= x<< 5;
dacă ((x & 0x80000001) != 0)
returnează 0;
nivel int = 1;
în timp ce (((x >>>= 1) & 1) != 0) ++nivel;
nivelul de returnare;
}
Vă puteți uita la sursa depozitului rezultat.
Toate împreună pot fi descărcate de pe googlecode.com (proiect de paginare).
Teste
Au fost utilizate trei tipuri de depozitare:- ArrayBased (matrice dinamică)
- SkipListBased (SkipList cu parametrul ¼)
- RBTreeBased (arborele roșu-negru: implementarea unui prieten de-al meu care a făcut o sarcină similară).
- Elemente sortate în ordine crescătoare
- Articole sortate în ordine descrescătoare
- Elemente aleatorii
Rezultate:
| Matrice | RBTtree | SkipList | |
|---|---|---|---|
| Aleatoriu | 127033 ms | 1020 ms | 1737 ms |
| Ordonat | 108 ms | 457 ms | 536 ms |
| Ordonate descendent | 256337 ms | 358 ms | 407 ms |
S-au făcut și măsurători: cât ocupă fiecare stocare în memorie cu 10^6 elemente introduse în ea. Am folosit un studio profiler; pentru simplitate, am rulat următorul cod:
var stocare =...Rezultate:
pentru (var i = 0; i< 1000000; ++i)
depozitare.Add(i);
| Matrice | RBTtree | SkipList | |
|---|---|---|---|
| Total octeți alocați | 8.389.066 octeți | 24.000.060 de octeți | 23.985.598 octeți |
Sfârșit fericit cu „Alenka”
Un coleg plângător, conform termenilor sarcinii, mi-a pariat un baton de ciocolată. Soluția mea a fost acceptată cu punctajul maxim. Sper că acest articol va fi de folos cuiva. Dacă aveți întrebări, vă voi răspunde cu plăcere.P.S.: Am avut un stagiu la SKB Kontur. Asta pentru a evita să răspunzi la aceleași întrebări =)
7 răspunsuri
Deoarece ați menționat o listă care este atât indexabilă (presupun că doriți o recuperare mai rapidă) cât și pentru a permite duplicate, v-aș sugera să utilizați un set personalizat cu LinkedList sau ArrayList.
Trebuie să aveți un set de bază, cum ar fi un HashSet, și să continuați să adăugați valori la acesta. Dacă întâlniți un duplicat, valoarea acestui set ar trebui să indice lista. Deci, veți avea atât căutare rapidă, cât și, bineînțeles, vă veți salva obiectele ca o colecție pseudo.
Acest lucru ar trebui să vă ofere o eficiență bună de extracție. În mod ideal, dacă cheile nu sunt duplicate, veți obține O(1) în viteza de căutare.
Acest răspuns întârzie 3 ani, dar sper că va fi de folos celor care doresc de acum înainte o listă de sărituri Java :)
Această soluție permite duplicarea așa cum ați solicitat. Urmează aproximativ ghidul de aici http://igoro.com/archive/skip-lists-are-fascinating, așa că dificultățile sunt similare cu acestea șterge costă O(nlogn) - cum am făcut-o „Nu încercați să utilizați noduri dublu conectate, bănuiesc că acest lucru va duce la șterge la O(logn).
Codul conține: o interfață, o listă de ignorare care implementează interfața și o clasă de noduri. Este, de asemenea, general.
Puteți personaliza parametrul NIVELURI pentru performanță, dar amintiți-vă de compromisul dintre spațiu și timp.
Puteți folosi codul de mai jos pentru a vă crea propriul dvs skipper de bază:
1) Faceți startȘi Sfârşit pentru a reprezenta începutul și sfârșitul listei de ignorare.
2) Adăugați nodurile și atribuiți pointeri la următorul pe baza
Dacă (nodul este par) atunci, atribuiți un indicator de bandă rapidă cu următorul pointer, altfel atribuiți doar pointerul următorului nod
Cod Java pentru o listă de ochire de bază (puteți adăuga funcții suplimentare):
Clasa publică MyClass ( public static void main(String args) ( Skiplist skiplist=new Skiplist(); Nodul n1=new Node(); Node n2=new Node(); Node n3=new Node(); Node n4=new Node (); Nodul n5=nodul nou(); Nodul n6=nodul nou(); n1.setData(1); n2.setData(2); n3.setData(3); n4.setData(4); n5.setData(4); n5.setData (5); n6.setData(6); skiplist.insert(n1); skiplist.insert(n2); skiplist.insert(n3); skiplist.insert(n4); skiplist.insert(n5); skiplist.insert( n6); /*tipărește toate nodurile*/ skiplist.display(); System.out.println(); /* imprimă numai nodul de bandă rapidă*/ skiplist.displayFast(); ) ) class Node (date private int; private Node one_next; //conține pointer către următorul nod privat Node doi_next; //pointer către nod după următorul nod public int getData() ( return data; ) public void setData(int data) ( this.data = data; ) public Node getOne_next() ( return one_next; ) public void setOne_next(Nod one_next) ( this.one_next = one_next; ) public Node getTwo_next() ( return two_next; ) public void setTwo_next(Nodul two_next; ) ) class Skiplist( Nod start; //start pointer pentru a omite lista Cap de nod; Node temp_next; //pointer pentru a stoca ultimul nod de bandă rapidă folosit Sfârșitul nodului; //sfârșitul listei de ignorare int lungime; public Skiplist())( start = nod nou(); sfârşit=nodul nou(); lungime=0; temp_next=start; ) public void insert(nodul Nod)( /*dacă lista de omitere este goală */ if(lungime==0)( start.setOne_next (nod); node.setOne_next(end); temp_next.setTwo_next(end); head=start; length++; ) else( length++; Node temp=start.getOne_next(); Node prev=start; while(temp !=end) ( prev=temp; temp=temp.getOne_next(); ) /*adăugați un indicator de bandă rapidă pentru nici unul dintre noduri*/ if(length%2==0)( prev.setOne_next(node); node.setOne_next(end) ); temp_next.setTwo_next(nod); temp_next=node; node.setTwo_next(end); ) /*numărul impar al nodului nu va conține indicator pentru banda rapidă*/ else( prev.setOne_next(nod); node.setOne_next(end) ; ) ) ) public void display())( System.out.println("--Simple Traversal--"); Node temp=start.getOne_next(); while(temp != end)( System.out.print( temp. getData()+" =>"); temp=temp.getOne_next(); ) ) public void displayFast())( System.out.println("--Fast Lane Traversal--"); Node temp=start.getTwo_next(); while(temp !=end)( System.out.print(temp . getData()+"==>"); temp=temp.getTwo_next(); ) ) )
Concluzie:
Bypass simplu -
1 = > 2 = > 3 = > 4 = > 5 = > 6 = >
Redirecționarea rapidă a unei piese -
2 == > 4 == > 6 == >
Când creați un ConcurrentSkipListSet, treceți un comparator constructorului.
Nou ConcurrentSkipListSet<>(nou ExampleComparator()); clasă publică ExampleComparator implementează Comparator
Puteți crea un comparator care vă va face SkipListSet să se comporte ca o listă obișnuită.
Nu pretind că aceasta este propria mea implementare. Pur și simplu nu-mi amintesc unde l-am găsit. Dacă știți, anunțați-mă și voi actualiza. Acest lucru funcționează bine pentru mine:
Clasa publică SkipList
S-a remediat o eroare în implementarea oferită de @PoweredByRice. A lansat un NPE pentru cazurile în care nodul la distanță a fost primul nod. Alte actualizări includ nume de variabile redenumite și tipărirea inversă a ordinii listelor de ignorare.
Import java.util.Random; interfață SkipableList
