Clasele 11-12 lecția 16 - 21 ian 2015

Skip lists

După două lecții mai grele (arbori și șiruri de sufixe), vom continua cu una mai ușoară despre skip lists. Lecția este totuși foarte utilă, întrucât skip lists oferă complexități egale cu ale arborilor echilibrați, dar consumă de două ori mai puțină memorie decât aceștia (cel puțin comparativ cu std::set).

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 când cheile sunt inserate sau șterse dintr-un anumit subarbore cu predilecție.

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, adică vor da întotdeauna răspunsul corect, dar ocazional vor avea nevoie de mai mult timp pentru aceasta.

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ă ordonată. Evident, timpul de rulare este $O(n)$ pentru inserări, căutări sau ștergeri.

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({\frac {n}{k}}+k)$, de exemplu $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 _{\frac {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

Alegerea înălțimii unui nod nou inserat

Există diverse variante pentru a alege un nivel conform unei distribuții geometrice. Nu par să existe mari diferențe ca timp de rulare, deși asta depinde de arhitectură. Presupunem că p = 1/2.

Metoda repetitivă

Pornim cu un nivel 1 și generăm în mod repetat numere 0 sau 1 aleatoare, incrementând nivelul cât timp primim 1. Nu depășim nivelul maxim.

int randomLevel() {
  int l = 1;
  while ((rand() & 1) && (l < MAX_LEVEL)) {
    l++;
  }
  return l;
}

Metoda biților 0 de la coadă

Generăm un număr aleator. Setăm un bit 0 pe poziția MAX_LEVEL - 1, pentru a ne asigura că numărul generat are între 0 și MAX_LEVEL-1 biți de 0 la coadă. Returnăm numărul de zerouri de la coada numărului.

int randomLevel() {
  unsigned r = rand() & ~(1 << (MAX_LEVEL - 1));
  int l = 1;
  while (r & 1) {
    l++;
    r >>= 1;
  }
  return l;
}

Metoda logaritmului discret

Generăm un număr aleator r. Calculăm h = r & -r pentru a obține un singur bit 1 cu o distribuție geometrică. Calculăm logaritmul discret al lui h prin metode performante (de exemplu cu un tabel).

Analiza de complexitate

Complexitatea pentru inserare și ștergere este dominată de complexitatea pentru căutare (plus încă $O(\log _{\frac {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 _{\frac {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;
  • cu probabilitate p pot face un pas în sus, iar cu probabilitate 1 - p continui drumul spre stânga;
  • 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, deoarece între două noduri de înălțime h ne așteptăm să vedem p turnuri de înălțime h - 1.

Ambele formule duc la complexitatea $O({\frac {1}{p}}log_{\frac {1}{p}}n)$. De aici deducem că valoarea optimă pentru p este 1/e (de ce?), 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. Pe calculatorul meu, și cu optimizări -O2 merg la fel de repede, dar pe calculatorul Varena.ro, varianta cu seturi STL, optimizată cu -O2, merge cam cu 25% mai rapid.

Iată rezultatele pentru 1.000.000 de elemente. Programele efectuează 1.000.000 de inserări, 1.000.000 de căutări, o iterare completă în ordine crescătoare, apoi 1.000.000 de ștergeri.

$ time ./skip-list 
inserare: 2246 ms
căutare: 2634 ms
iterare: 118 ms
ștergere: 2603 ms

real	0m7.607s
user	0m7.544s
sys	0m0.048s

$ time ./set
inserare: 1838 ms
căutare: 1651 ms
iterare: 130 ms
ștergere: 1898 ms

real	0m5.625s
user	0m5.468s
sys	0m0.052s

Diferența cea mare apare însă la memorie. Skip lists ocupă cam 12 MB de memorie, pe când setul STL ocupă 24 MB. Pe arhitecturi pe 64 de biți, necesarul crește chiar la 48 MB! Am folosit acest script pentru măsurarea memoriei ocupate (cu constanta sleep modificată de la 0.1 s la 0.001 s).

Iată și sursele: media:skip-list-v2.cpp media:stl-alternativa-skip-list-v2.cpp.

Skip lists deterministe

În limita timpului, vorbim despre skip lists 1-2. Acestea nu ne interesează direct, dar se aplică în situații când dorim să garantăm timpi $O(\log n)$ worst-case, nu doar în cazul mediu.

Temă

• Tema 13 seniori