Structuri de date fără blocare. Hărți concurente: ignorați lista

Există o părere destul de răspândită că îndeplinirea diferitelor sarcini de testare ajută la ridicarea foarte rapidă a nivelului profesional. Eu însumi îmi place uneori să dezgrop o întrebare dificilă de test și să o rezolv, pentru a fi mereu atent, așa cum se spune. Odată ce finalizam o misiune competitivă pentru un stagiu la o companie, problema mi s-a părut amuzantă și interesantă, iată textul ei scurt:

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:
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ția poate fi foarte interesantă, așa că am crezut că este necesar să o descriu.

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.

Să evaluăm complexitatea abordării pe baza unui tablou dinamic.

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ă

Ideea este aceasta: putem adăuga un anumit număr de niveluri cu un anumit număr de noduri în ele, iar nodurile din niveluri ar trebui să fie distribuite uniform. Să luăm în considerare un exemplu când fiecare dintre nivelurile de deasupra conține jumătate din elementele de la nivelul de bază:

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(
int Element;
SkipListNodeNext;
int Lățimea;
}

De fapt, asta s-a făcut.

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țiile 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() (
int x = randomSeed;
x ^= x<< 13;
x ^= x >>> 17;
randomSeed = x ^= x<< 5;
dacă ((x & 0x80000001) != 0)
întoarce 0;
nivel int = 1;
în timp ce (((x >>>= 1) & 1) != 0) ++nivel;
nivelul de returnare;
}

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.

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ă).

Au fost efectuate trei tipuri de teste pentru introducerea a 10^6 elemente:

Elemente sortate în ordine crescătoare
Articole sortate în ordine descrescătoare
Elemente aleatorii

Testele au fost efectuate pe o mașină cu i5, 8gb ram, ssd și Windows 7 x64.
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

Rezultate destul de așteptate. Puteți vedea că inserarea într-o matrice, atunci când un element este inserat în altă parte decât la sfârșit, este cea mai lentă. În același timp, SkipList este mai lent decât RBTree.

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 =...
pentru (var i = 0; i< 1000000; ++i)
depozitare.Add(i);

Rezultate:

	Matrice	RBTtree	SkipList
Total octeți alocați	8.389.066 octeți	24.000.060 de octeți	23.985.598 octeți

Există, de asemenea, rezultate destul de așteptate: stocarea pe o matrice dinamică a ocupat cea mai mică cantitate de memorie, iar SkipList și RBTree au ocupat aproximativ aceeași cantitate.

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 =)

Listele de ignorare sunt o structură de date care poate fi folosită în locul arborilor echilibrați. Deoarece algoritmul de echilibrare este mai degrabă probabilist decât strict, inserarea și ștergerea unui element în listele de omitere este mult mai ușoară și mult mai rapidă decât în arborele echilibrat.

Listele de ignorare sunt o alternativă probabilistică la arborii echilibrați. Ele sunt echilibrate folosind un generator de numere aleatorii. Deși listele de ignorare au performanțe slabe în cazul cel mai rău, nu există o secvență de operații care să facă acest lucru în mod constant (la fel ca sortarea rapidă cu un element de referință aleatoriu). Este foarte puțin probabil ca această structură de date să devină dezechilibrată semnificativ (de exemplu, pentru un dicționar mai mare de 250 de elemente, șansa ca o căutare să dureze de trei ori timpul estimat este mai mică de unu la un milion).

Este mai ușor să echilibrați o structură de date probabil decât să impuneți în mod explicit echilibrul. Pentru multe sarcini, listele de omitere sunt o reprezentare mai naturală a datelor în comparație cu copacii. Algoritmii se dovedesc a fi mai simplu de implementat și, în practică, mai rapid în comparație cu arborii echilibrați. În plus, listele de ignorare sunt foarte eficiente în memorie. Ele pot fi implementate la o medie de aproximativ 1,33 pointeri per element (sau chiar mai puțin) și nu necesită stocarea informațiilor suplimentare de echilibru sau de prioritate pentru fiecare element.

Pentru a găsi un element într-o listă legată, trebuie să ne uităm la fiecare dintre nodurile sale:

Dacă lista este păstrată sortată și fiecare al doilea nod conține în plus un indicator cu două noduri înainte, trebuie să ne uităm cel mult ⌈ n/2⌉ + 1 noduri (unde n- lungimea listei):

De asemenea, dacă fiecare al patrulea nod conține acum un indicator cu patru noduri înainte, atunci ar trebui să vă uitați la cel mult ⌈ n/4⌉ + 2 noduri:

Dacă la fiecare 2 i i noduri înainte, atunci numărul de noduri care trebuie scanate va fi redus la ⌈log 2 n⌉, iar numărul total de pointeri din structură se va dubla doar:

Această structură de date poate fi utilizată pentru căutări rapide, dar inserarea și ștergerea nodurilor va fi lentă.

Să numim nod un nod care conține k pointeri către elemente înainte nivel k . Dacă la fiecare 2 i Al-lea nod conține un pointer către 2 i nodurile înainte, apoi nivelurile sunt distribuite după cum urmează: 50% dintre noduri sunt nivelul 1, 25% sunt nivelul 2, 12,5% sunt nivelul 3 etc. Dar ce se întâmplă dacă nivelurile nodurilor sunt alese aleatoriu, în aceleași proporții? De exemplu, așa:

Numarul indexului i fiecare nod se va conecta la nivelul următor i sau mai mult, nu tocmai 2 i-1 nod înainte, ca înainte. Inserările și ștergerile vor necesita doar modificări locale; nivelul unui nod ales aleatoriu atunci când este introdus nu se va schimba niciodată. Dacă atribuirea nivelului nu reușește, performanța poate fi slabă, dar vom arăta că astfel de situații sunt rare. Deoarece aceste structuri de date sunt liste legate cu indicatori suplimentari pentru a omite nodurile intermediare, le numesc liste cu omisiuni.

Operațiuni

Să descriem algoritmi de căutare, inserare și ștergere a elementelor într-un dicționar implementat pe liste cu lacune. Operațiune căutare returnează valoarea pentru cheia dată sau semnalează că cheia nu a fost găsită. Operațiune inserții asociază o cheie cu o nouă valoare (și creează o cheie dacă nu a existat înainte). Operațiune îndepărtare sterge cheia. De asemenea, puteți adăuga cu ușurință operațiuni suplimentare la această structură de date, cum ar fi „găsiți cheia minimă” sau „găsiți următoarea cheie”.

Fiecare element de listă este un nod al cărui nivel a fost ales aleatoriu atunci când a fost creat, indiferent de numărul de elemente care erau deja acolo. Nod de nivel i conţine i pointeri către diferitele elemente din față, indexate de la 1 la i. Este posibil să nu stocăm nivelul nodului în nodul în sine. Numărul de niveluri este limitat de o constantă preselectată MaxLevel. Hai sa sunăm nivel de listă nivelul maxim al unui nod din această listă (dacă lista este goală, atunci nivelul este 1). Titlu lista (în imagini este în stânga) conține indicatori către niveluri de la 1 la MaxLevel. Dacă nu există încă elemente de acest nivel, atunci valoarea indicatorului este un element special NIL.

Inițializare

Să creăm un element NIL a cărui cheie este mai mare decât orice cheie care ar putea apărea vreodată în listă. Elementul NIL va termina toate listele cu lacune. Nivelul listei este 1, iar toți pointerii din antet se referă la NIL.

Căutați un element

Începând cu indicatorul de cel mai înalt nivel, avansăm prin indicatori până când se referă la un element care nu este mai mare decât cel pe care îl căutăm. Apoi coborâm un nivel și urmam din nou aceeași regulă. Dacă am ajuns la nivelul 1 și nu putem merge mai departe, atunci ne aflăm chiar în fața elementului pe care îl căutăm (dacă este acolo).

Căutare(listă, cheie de căutare)
x:= list→header
# invariant de buclă: x→key< searchKey
pentru i:= listă→nivel jos la 1 do
in timp ce x→înainte[i]→tasta< searchKey do
x:= x→forward[i]
#x→key< searchKey ≤ x→forward→key
x:= x→înainte
dacă x→key = searchKey apoi întoarcere x→valoare
altfel întoarcere eșec

Inserarea și ștergerea unui element

Pentru a insera sau elimina un nod, folosim un algoritm de căutare pentru a găsi toate elementele înaintea celui care este inserat (sau eliminat), apoi actualizăm pointerii corespunzători:

În acest exemplu, am inserat un element de nivel 2.

Introduce(listă, cheie de căutare, valoare nouă)
local Actualizați
x:= list→header
pentru i:= listă→nivel jos la 1 do
in timp ce x→înainte[i]→tasta< searchKey do
x:= x→forward[i]
#x→key< searchKey ≤ x→forward[i]→key
actualizare[i] := x
x:= x→înainte
dacă x→key = searchKey apoi x→valoare:= newValue
altfel
lvl:= randomLevel()
dacă lvl > listă→nivel apoi
pentru i:= listă→nivel + 1 la lvl do
update[i] := list→header
list→level:= lvl
x:= makeNode(lvl, searchKey, value)
pentru eu:= 1 la nivel do
x→forward[i] := actualizare[i]→forward[i]
actualizare[i]→forward[i] := x

Șterge(listă, cheie de căutare)
local Actualizați
x:= list→header
pentru i:= listă→nivel jos la 1 do
in timp ce x→înainte[i]→tasta< searchKey do
x:= x→forward[i]
actualizare[i] := x
x:= x→înainte
dacă x→key = searchKey apoi
pentru eu:= 1 la listă→nivel do
dacă actualizare[i]→forward[i] ≠ x apoi pauză
actualizare[i]→forward[i] := x→forward[i]
gratuit(x)
in timp ce listă→nivel > 1 și list→header→forward = NIL do
listă→nivel:= listă→nivel – 1

O matrice este folosită pentru a reține elemente înainte de inserare (sau îndepărtare) Actualizați. Element actualizare[i]- acesta este un pointer către nodul cel mai din dreapta al nivelului i sau mai mare, de la cele situate în stânga locației de actualizare.

Dacă nivelul selectat aleatoriu al nodului inserat se dovedește a fi mai mare decât nivelul întregii liste (adică dacă nu au existat încă noduri cu un astfel de nivel), creștem nivelul listei și inițializam elementele matricei corespunzătoare Actualizați indicii către titlu. După fiecare ștergere, verificăm dacă am șters nodul cu nivelul maxim și, dacă da, reducem nivelul listei.

Generarea unui număr de nivel

Anterior, am prezentat distribuția nivelurilor nodurilor în cazul în care jumătate din nodurile care conțin indicatorul de nivel i, conținea și un pointer către nodul de nivel i+1. Pentru a scăpa de constanta magică 1/2, notăm prin p ponderea nodurilor de nivel i, care conține un pointer către nodurile de nivel i+i. Numărul nivelului pentru noul vârf este generat aleatoriu folosind următorul algoritm:

randomLevel()
lvl:= 1
# random() returnează un număr aleator într-un interval de jumătate, lungime: " + lungime); ) )

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 (); Node n5=new Node(n1.setData(4); skiplist.insert(n3); skiplist.insert(n5); * tipăriți numai nodul de bandă rapidă*/ skiplist.displayFast() ) class Node( private int date; private Node one_next; //conține pointer la următorul nod privat Node two_next; //pointer la nod după următorul nod public int getData() ( return date; ) 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 Nodul getTwo_next() ( return two_next; ) public void setTwo_next(Nodul two_next) ( this.two_next = 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 = new Node(); end=new Node(); temp_next=start; ( node.setOne_next(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(node temp_next=node.setTwo_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 (// implicația dvs.)
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 > implementează Iterable (Nodul _head = Nod nou<>(nul, 33); privat final Random aleatoriu = new Random(); private int _levels = 1; private AtomicInteger size = new AtomicInteger(0); ///
/// Inserează o valoare în lista de ignorare. ///
public void insert(valoarea T) ( // Determinați nivelul noului nod. Generați un număr aleator R. // numărul de // 1-biți înainte de a întâlni primul 0-bit este nivelul nodului . / / Deoarece R este // de 32 de biți, nivelul poate fi de cel mult 32. int level = 0.incrementAndGet(); (R & 1) == 1; ; R >>= 1) ( level++; if (level == _levels) ( _levels++; break; ) ) // Inserați acest nod în lista de omitere newNode = nou Nod<>(valoare, nivel + 1); Nodul cur = _cap; pentru (int i = _levels - 1; i >= 0; i--) ( pentru (; cur.next[i] != null; cur = cur.next[i]) ( dacă (cur.next[i]) .getValue().compareTo(valoare) > 0) break ) dacă (i<= level) { newNode.next[i] = cur.next[i]; cur.next[i] = newNode; } } } ///
/// Returnează dacă o anumită valoare există deja în lista de omitere ///
public boolean conține (valoarea T) ( Node cur = _cap; pentru (int i = _levels - 1; i >= 0; i--) ( pentru (; cur.next[i] != null; cur = cur.next[i]) ( dacă (cur.next[i]) .getValue().compareTo(value) > 0) break if (cur.next[i].getValue().compareTo(value) == 0) return false; ) ///
/// Încearcă să elimine o apariție a unei anumite valori din lista /// de ignorare. Returnează /// dacă valoarea a fost găsită în lista de omitere. ///
public boolean remove (valoare T) ( Node cur = _cap; boolean găsit = fals; pentru (int i = _levels - 1; i >= 0; i--) ( pentru (; cur.next[i] != null; cur = cur.next[i]) ( dacă (cur.next[i]) .getValue().compareTo(valoare) == 0) ( găsit = adevărat; cur.next[i] = cur.next[i].next[i]; break; ) dacă (cur.next[i].getValue ().compareTo(valoare) > 0) break ) ) if (găsit) size.decrementAndGet(); retur găsit; ) @SuppressWarnings(( „tipuri brute”, „nebifat” )) @Override public Iterator iterator() ( return new SkipListIterator(this, 0); ) public int size() ( return size.get(); ) public Double toArray() ( Double a = new Double; int i = 0; for (T t: this) ( a[i] = (Dublu) t; i++; ) return a ) ) clasa Nod > ( Public Node Următorul; valoare publică N; @SuppressWarnings(„nebifat”) public Node(N valoare, nivel int) ( this.value = value; next = new Node; ) public N getValue() ( return value; ) public Node getNext() ( return next; ) public Node getNext(nivel int) ( return next; ) public void setNext(Node next) ( this.next = next; ) ) clasa SkipListIterator > implementează Iterator ( SkipList listă; Nodul actual; nivel int; public SkipListIterator(SkipList listă, nivel int) ( this.list = list; this.current = list._head; this.level = level; ) public boolean hasNext() ( return current.getNext(level) != null; ) public E next() ( current = current.getNext(level); return current.getValue(); ) public void remove() aruncă UnsupportedOperationException (aruncă nou UnsupportedOperationException(); ) )

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 > ( NIVELURI int = 5; ștergere booleană (T țintă); void print(); void insert (T date); SkipNode căutare (date T); ) clasa SkipNode > ( N date; @SuppressWarnings(„nebifat”) SkipNode următorul = (SkipNode ) noul SkipNode; SkipNode(N date) ( this.data = data; ) void refreshAfterDelete(int level) ( SkipNode curent = aceasta; în timp ce (curent != null && curent.getNext(nivel) != nul) ( dacă (current.getNext(nivel).data == nul) ( SkipNode succesor = current.getNext(level).getNext(level); current.setNext(succesor, nivel); întoarcere; ) curent = curent.getNext(nivel); ) ) void setNext(SkipNode next, int level) ( this.next = next; ) SkipNode getNext(nivel int) ( return this.next; ) SkipNode search(N date, int level, boolean print) ( if (print) ( System.out.print("Se caută: " + date + " la "); print(level); ) SkipNode rezultat = nul; SkipNode curent = this.getNext(level); while (current != null && current.data.compareTo(data)< 1) { if (current.data.equals(data)) { result = current; break; } current = current.getNext(level); } return result; } void insert(SkipNodeskipNode, nivel int) ( SkipNode curent = this.getNext(level); if (current == null) ( this.setNext(skipNode, nivel); return; ) if (skipNode.data.compareTo(current.data)< 1) { this.setNext(skipNode, level); skipNode.setNext(current, level); return; } while (current.getNext(level) != null && current.data.compareTo(skipNode.data) < 1 && current.getNext(level).data.compareTo(skipNode.data) < 1) { current = current.getNext(level); } SkipNodesuccesor = current.getNext(level); current.setNext(skipNode, nivel); skipNode.setNext(succesor, nivel); ) void print(nivel int) ( System.out.print("nivel " + nivel + ": [ "); lungime int = 0; SkipNode curent = this.getNext(level); while (current != null) ( length++; System.out.print(current.data + " "); curent = current.getNext(level); ) System.out.println("], lungime: " + lungime); ) ) clasa publică SkipList > implementează SkipableList ( SkipNode final privat cap = nou SkipNode<>(nul); privat final Random aleatoriu = new Random(); @Override public void insert (T date) ( SkipNode skipNode = SkipNode nou<>(date); pentru (int i = 0; i< LEVELS; i++) { if (rand.nextInt((int) Math.pow(2, i)) == 0) { //insert with prob = 1/(2^i) insert(skipNode, i); } } } @Override public boolean delete(T target) { System.out.println("Deleting " + target); SkipNodevictimă = căutare (țintă, adevărat); if (victima == null) returnează fals; victim.data = nul; pentru (int i = 0; i< LEVELS; i++) { head.refreshAfterDelete(i); } System.out.println("deleted..."); return true; } @Override public SkipNodesearch(T data) ( return search(data, true); ) @Override public void print() (pentru (int i = LEVELS-1; i >= 0 ; i--) ( head.print(i); ) System.out.println(); inserare void privată (SkipNode SkipNode, nivel int) ( head.insert(SkipNode, nivel); ) privat SkipNode căutare (date T, imprimare booleană) ( SkipNode rezultat = nul; pentru (int i = NIVELELE-1; i >= 0; i--) ( if ((rezultat = head.search(data, i, print)) != null) ( if (print) ( System.out.println ("Găsit " + data.toString() + " la nivelul " + i + ", deci oprit"); ) public static void main(String args) ( SkipList sl = SkipList nou<>(); int date = (4,2,7,0,9,1,3,7,3,4,5,6,0,2,8); pentru (int i: date) ( sl.insert(i); ) sl.print(); sl.search(4); sl.delete(4); System.out.println("Se introduc 10"); sl.inserat(10); sl.print(); sl.search(10); ) )

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

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