Note de curs, clasele 9-12, 13 februarie 2014

Skip lists

Generalități

Skip lists sunt o structură de date care suportă următoarele operații, toate în timp O(log n) sau mai bun:

• inserare
• ștergere
• căutare
• aflarea minimului / maximului
• aflarea elementului anterior / următor

Puteți citi articolul original de William Pugh.

Structura „tradițională” folosită pentru aceste operații sunt arborii binari de căutare. Aceștia sunt însă dificil de implementat, căci trebuie echilibrați prin diverse metode (roșu și negru, splay, arbori B). În lipsa echilibrării, arborii pot degenera din diverse motive:

• cheile pot fi inserate în arbore într-o ordine defavorabilă (crescătoare, de exemplu);
• cheile pot fi șterse cu predilecție dintr-un anumit subarbore.

Skip lists sunt o alternativă la arborii echilibrați, mai ușor de implementat și cu timpi comparabili în practică. Ele pornesc de la observația că, dacă am insera cheile în arbore în ordine aleatoare, arborele ar fi echilibrat cu probabilitate mare. Skip lists sunt o structură de date probabilistică (de tip Las Vegas).

Discuție despre tipurile de algoritmi probabilistici:

• Monte Carlo: dau răspunsuri care pot fi incorecte. Cu cât rulează mai mult, cu atât algoritmul are șanse mai mari să dea răspunsul corect.
• Las Vegas: dau întotdeauna răspunsuri corecte, dar timpul de rulare este distribuit probabilistic.

O încercare deterministă

Să pornim cu o listă simplu înlănțuită. Evident, în cel mai rău caz trebuie să inspectăm n elemente.

Cum putem adăuga niște pointeri pentru a accelera această căutare? Să considerăm că elementele de pe poziții impare țin și un pointer la două elemente în față. Atunci numărul de elemente de inspectat este redus la n / 2 + 1.

Putem adăuga și un al treilea nivel, pe care elementele de pe poziții de forma 4k + 1 țin pointeri la patru elemente în față. Atunci numărul de elemente de inspectat este redus la n / 4 + 2 (cum?).

O altă abordare este să creăm al doilea nivel ca o „autostradă” cu pointeri din k în k elemente. Atunci timpul de căutare devine O(n/k + k), adică O(sqrt(n)) dacă alegem k = sqrt(n).

Problema cu aceste abordări deterministe este că distanțele între elemente nu rămân constante. Mereu se inserează și se șterg elemente. Dacă inserăm 1.000.000 de elemente în aceeași fereastră de k elemente, atunci „autostrada” noastră va degenera.

Aici intervine nedeterminismul. Nu mai alegem în mod determinist care elemente urcă pe nivelurile 2, 3, etc., ci în mod probabilistic.

Comportamentul nedeterminist

Fixăm o valoare subunitară p. Toate nodurile apar în lista de pe nivelul 1, dar doar o fracțiune aproximativ egală cu p dintre ele vor apărea și pe nivelul 2. Dintre acestea, o fracțiune aproximativ egală cu p vor urca la nivelul 3 etc. Numărul de niveluri necesar este deci log_1/p n. El trebuie limitat prin program, căci altfel se poate întâmpla (deși este foarte improbabil) ca un nod să urce mult prea sus.

Exemplu. Observăm că înălțimile nodurilor sunt generate aleator, dar nu uniform. Secțiunile următoare discută, sumar, distribuția geometrică și cum putem genera un număr aleator cu această distribuție.

Exemplu de căutare. Pseudocod:

bool caută (list, x) {
  nod v = list->head;
  for i = list->level downto 1 {
    while (v->next[i]->key < x) {
      v = v->next[i];
  v = v->next[1]
  return (v->key == x);
}

Punem santinele la început și la sfârșit pentru a evita testele de NULL.

La inserarea unei valori x:

• Căutăm elementul.
  • Reținem locurile în listă unde am coborât la un nivel inferior.
  • Dacă îl găsim, nu mai avem nimic de făcut (decât dacă permitem duplicate).
  • Dacă nu îl găsim, ne poziționăm pe elementul imediat mai mare.
• Alegem un nivel pentru acel nod, folosind o distribuție geometrică
• Refacem structura de pointeri.

Pseudocod pentru inserare și ștergere.

Pentru a analiza complexitatea acestui algoritm, vom (re)introduce câteva noțiuni elementare de probabilități.

Noțiuni de probabilități

• experiment Bernoulli; experiment binomial B(n, p)
• valoarea așteptată pt. Bernoulli: p; pentru binomial: np
• nr. de experimente până la succes: distribuție geometrică
• valoarea așteptată a nr. de experimente: 1 / p

Analiza de complexitate

Complexitatea pentru inserare și ștergere este dominată de complexitatea pentru căutare (plus încă O(log_1/p n) pentru refacerea pointerilor).

Complexitatea pentru căutare este dată de distanța drumului parcurs spre dreapta (prin urmarea pointerilor) și în jos (prin coborârea nivelurilor). Pașii în jos sunt exact log_1/p n. Câți pași la dreapta va face, în medie, algoritmul?

Facem observația preliminară că, în clipa în care urmăm un pointer ca să ajungem la un nou element x, vom fi pe nivelul cel mai înalt al lui x. Demonstrația se face prin reducere la absurd: dacă x ar fi mai înalt decât nivelul curent, am fi putut ajunge la el folosind un nivel mai înalt (adică pe o „autostradă” mai rapidă).

Există două metode de analiză:

• metoda înapoi, care reconstituie drumul de la elementul căutat la capul listei;
  • recurența C(k) = (1–p) (1 + C(k)) + p (1 + C(k–1)), unde C(k) este costul necesar pentru a urca k niveluri pe verticală
• metoda înainte, care calculează numărul mediu de pași făcuți înainte de a coborî la nivelul următor
  • numărul așteptat este de 1/p pași pe nivel.

Ambele formule duc la complexitatea O(log_1/p n / p). De aici deducem că valoarea optimă pentru p este 1/e, dar în practică valorile 1/2 și 1/4 sunt foarte bune (discuție).

Cum variază consumul de memorie în funcție de p?

Implementare

Este important să faceți implementarea fără alocare dinamică. Am testat o implementare cu pointeri luată la întâmplare de pe Internet și dura cam cu 75% mai mult.

Spre dezamăgirea mea, nu am reușit să fac implementarea mea mai rapidă decât setul din STL. Fără optimizări merg cam la fel de repede, iar cu „-O3”, implementarea STL merge cam cu 15% mai rapid.

Provocarea și tema pentru voi este să vă gândiți la o implementare mai rapidă!

media:skip-list.cpp media:stl-alternativa-skip-list.cpp