Skiplists

(Categoria Structuri de date, Autori Sorin Stancu-Mara, Mihnea Giurgea)

Vreau sa va fac cunostinta cu o noua structura randomizata de stocare a datelor. Ea se numeste Skiplist si permite majoritatea operatiilor in timp logaritmic si este foarte usor de implementat. Structura ocupa O(N) memorie si efectueaza majoritatea operatiilor (adaugare, cautare, stergere) in O(log N). Bineinteles ca exista STL, dar de cele mai multe ori nimic nu bate o structura "home-brewed". Skiplist-urile sunt foarte similare cu arborii AVL, insa sunt un pic mai rapide si mai usor de implementat.

Introducere

Totul porneste de la o lista simplu inlantuita in care fiecare element are un link (pointer sau orice altceva care poate indica alt element) catre urmatorul element din lista. Presupunem ca aceasta lista o tinem sortata. Ce ar fi daca de la elementul x nu am sari la elementul x+1? Ce ar fi daca am sari la x+2? Acesta este principiul din spatele Skiplist-urilor.

Intr-un Skiplist fiecare element are un grad, numarul de link-uri la alte elemente. Un link de nivelul x va indica un element care are cel putin x nivele, astfel este posibil ca sa parcurgem toata lista cu link-uri de un anumit nivel. Cheia este ca, cu cat nivelul este mai mare, elemente de nivelul respectiv sunt mai rare, link-urile sunt din ce in ce mai putine si astfel pointeaza mai departe. La nivelul minim,0, exista un link catre elementul exact urmator, iar cu cat crestem nivelul, cu atat link-urile sunt mai rare si "sar" peste mai multe elemente, de unde vine si denumirea de Skiplist-uri, liste cu salt.

Implementare

Intr-un skiplist nodurile pot avea orice grad, alegerea gradului tine exclusiv de consideratii de viteza. Pentru detalii vezi sectiunea de complexitate.

Cum se implementeaza o structura de genul asta? Mai intai trebuie sa subliniez ca este la fel de usor de implementat si in Pascal, dar nu mai respecta limita de memorie, care se va duce la N log N, dar care in cele mai multe cazuri este ok.

Implementarea in C ar arata ceva de genul:

struct nod {
    int key; 
    /* ce mai vreti sa memorati intrun nod. */
    nod** link;
}

In Pascal nod* link, un array dinamic, este mai dificil de implementat. Pentru a evita asta putem sa alocam la maxim array-ul, mai exact log N elemente. Asta ridica complexitatea de memorie la O(N log N), dar de cele mai multe ori este perfect acceptabil.

type pnod=^nod;
nod=record
    key:integer;
    { ce mai vreti sa memorati intr-un nod }
    link:array[0..logN] of pnod;
end;

Pe langa asta trebuie sa tineti minte capul listei, care trebuie sa fie un nod de grad maxim. De asemenea, cu cat gradul maxim este mai mare cu atat va merge mai repede pt N mai mare (100,000) deci cand va ganditi la gradul maxim luati-l ceva de genul logN*2.

Ca implementare efectiva nu va trebuie decat un singur algoritm, cautarea, restul fiind extrem de usor de dedus. Algoritmul de cautare pe care il vom prezenta isi propune sa caute ultimul element cu cheia mai mica decat o anumita valoare.

Pentru a cauta un element intr-o lista inlantuita normala sortata se incepe de la primul element si se avanseaza pana cand urmatorul nod are cheia mai mare decat cea cautata. Intr-un Skiplist procedam exact la fel, dar folosim faptul ca avem mai multe nivele de inlantuire. Vom incepe de la cel mai inalt nivel, si vom cauta ca intr-o lista inlantuita normala. Cand urmatorul nod la nivelul curent are cheia mai mare (sau este null) vom scadea nivelul.

O implementare in pseudo-C ar arata ceva de genul:

nod *x = cap_de_lista;
int grad = grad_max;
nod temp[grad_max];
    while (gradul >= 0) {
        while (x->link[grad] != NULL && x->link[grad]->key < cheie_cautata)
            x=x->link[grad];
        temp[grad]=x;
        grad--;
    }

Acest algoritm ne da nodul din fata elementului cautat, daca acesta exista, sau cel care are cel mai mare key mai mic decat cel cautat. De aici e simplu sa vedem daca elementul cautat exista in Skiplist, ar trebui sa fie x->link₀ (urmatorul element, pe nivelul 0 structura este o lista simplu inlantuita). De asemenea ne mai ramane si temp, temp contine acum toate nodurile din fata elementului curent care indica catre elemente de la x in sus. Acest vector temp este o modalitate de a evita listele dublu-inlantuite, si a injumatati consumul de memorie.

OK, dar cum se fac celelalte operatii? Sa le luam pe rand...

• Cautare: am explicat deja
• Inserare: vrem sa inseram un nod cu cheia k. Mai intai cautam cheia k in Skiplist-ul deja existent, apoi alocam un nou nod de grad g, pe care il adaugam la fiecare nivel mai mic decat g, exact ca intr-o lista simplu inlantuita.
• Stergere: vrem sa stergem nodul cu cheia k. Mai intai cautam cheia k, apoi stergem nodul la fiecare nivel, exact ca intr-o lista normala.
• Interclasare: aici complexitatea mai depinde si de cat de separate sunt cele doua skip-uri. In principiu comparati primele elemente din fiecare lista iar pe cel mai mare il cautati in celalalt skiplist, luati elementele intre start si pozitia unde s-a oprit algoritmul de cautare si le adaugati in structura care va contine uniunea celor doua.

Complexitate

Pana acum nu am dat nici o explicatie asupra presupusei complexitati O(log N) a operatiilor. Dupa cum puteti vedeam mai sus, operatiile de adaugare si stergere sunt de fapt variante ale operatiiei de cautare, la care se adauga O(grad maxim). Cea mai importanta operatie este cea de cautare.

Operatia de cautare va merge prin toate nivele, deci are complexitate minima O(grad maxim). Ne putem imagina un skip-list ideal, in care grad-maxim este O(log N), iar gradele sunt o secventa de genul (max, 1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 16, 1, 2, 1, 4, 1...). In acest skip-list, cautarea este echivalenta cu o cautare binara, la fiecare pas vom "sari" peste fix jumatate din ce a ramas, pentru o complexitate finala de [O(log N)}. Bineinteles, un skip-list real este destul de departe de acest ideal. In cel mai rau caz este posibil ca toate elementele sa aiba acelasi grad, si totul se reduce la o lista inlantuita cu consum mare de memorie, dar este putin probabil. Pe cazul mediu va avea insa complexitatea de O(log N).

Pentru a aduce insa la complexitatea de O(log N), este nevoie ca gradele sa aiba o distrubutie logaritmica: fiecare nod are gradul ≥1, N/2 au gradul ≥ 2, N/4 au gradul ≥ 3, n/8 au gradul ≥ 4, etc. Pentru asta avem nevoie de o functie de alegere a gradului aleatoare cu probabilitate logaritmica. Putem face ceva simplu de genul:

rang = 1
while (rand() % 2 == 0) {
    ++rang;
}

Functia de mai sus merge satisfacator. Eventual putem sa memoram cate nod-uri de fiecare grad sunt in lista (modificand adaugarea si stergerea), si sa returnam nivelul la care suntem cel mai departe de ideal, dar nu este necesar.

Memorie este oarecum evident O(N). Daca skiplist-ul ar fi complet echilibrat atunci vor exista N link-uri de nivel 0, N/2 de nivel 1, N/4 de nivel 2, etc. Cu putina matematica N + N/2 + N/4 + N/8.. = 2 * N, adica O(n). Pentru cei care programeaza in pascal si nu vor sa se complice cu alocare de array-uri dinamice, memoria va fi evident O(N log N)

Skip Lists vs. AVL - Timpi de executie

Am testat pe laptopul meu implementearea AVL (vezi acest articol ) vs. Skiplists (vezi implementarea de mai jos). Laptopul este destul de performant, dar important este raportul dintre timpii de executie la AVL, respectiv Skiplists.

Concluzia: Skiplisturile sunt de 2 ori mai rapide decat AVL-urile.

Extinderi

Pe langa algoritmii de baza skip list permite imbogatiri care va permit multe alte lucruri cu timp minim de implementare si complexitate O(log N). Cam toate imbogatirile structurii se bazeaza pe memorarea in paralel a unor informatii ajutatoare pt fiecare link (ATENTIE in pascal)

Acces secvential: vrem sa accesam elementul pe pozitia i. Pentru aceasta vom memora pe fiecare link cate noduri "acopera", cu alte cuvinte cate noduri sare. Cautarea se modifica prin introducerea unei noi variabile care memoreaza indicele nodului curent, si prin comparare pozitie la care se sare in loc de cheia la care se sare. La inserare si stergere, trebuiesc actualizate toate linkurile din temp, deoarece si cele care indica peste codul curent contin informatii referitoare la el (il numara).

Intervale: Tot ce trebuie sa adaugam, ca implementare, este o cautare in mod invers, care porneste de la nodul curent (START) si grad = 0, si "urca" pana cand grad > grad_max, sau link_grad > END (nu exista un nod mai inalt intre inceputul si sfarsitul intervalului, dupa care trebuie sa coboare, ca la cautarea obisnuita... (eventual START si END necesita inserare in skiplist). Daca ati fost un pic atenti am parcurs toate link-urile care contin informatii despre intervalul curent. Pentru stabbing querys (avem un punct si ne intereseaza intervalele care le taie punctul respectiv) tot ce trebuie sa face este sa cautam in skiplist punctul respectiv si sa luam din temp informatiile de la fiecare link.

Implementare completa

Va prezint in continuare o implementare eleganta a skip lists-urilor cu cam tot ce ai putea avea nevoie in olimpiade: cautare dupa cheie si index, inserare, stergere, si posibilitatea de a calcula functiile Predecesor(node) si Succesor(node in O(1) cand ai node, pe care il gasesti in timp logaritmic. Vreau sa subliniez ca implementarea fara cautarea dupa index este cu mult mai simpla si scurta.

Nodul de baza contine in cazul de fata un integer pe post de informatie (info), dar puteti pune aici orice altceva, array-ul de dimensiune variabila de pointeri (link), o legatura catre elementul "din spate" (prev), si un array de dimensiune variabila de integeri (jump), in care tin minte pentru fiecare pointer din link "cate elemente sare" - folositor pentru accesul secvential.

struct _node
{
	int info;
	struct _node **link, *prev;
	int *jump;
};
typedef struct _node Node;

Procedura de a afla inaltimea unui nod, cu un singur apel la funtia rand(). In H se tine minte nivelul curent maxim al listei, si o buna optimizare este sa nu introducem nivele mai mari decat H + 1, pentru o mai buna distributie a nodurilor pe nivele.

int GetH()
{
	int h, r;
	for (h = 0, r = rand(); r % 2; r >>= 1, h++);
	if (h > H) h = H + 1;
}

Pentru a procesa Insert si Remove, vom tine un array de pointeri (path) pentru a indica ultimul nod de pe fiecare nivel obtinut in urma cautarii, precum si array-ul jumped, care ne spune "cate noduri am sarit" la fiecare nivel, precum si pointer catre inceputul listei (head) si inaltimea maxima a listei (H).

Node *path[MAX_H], *head;
int jumped[MAX_H], H;

Si restul functiilor, explicate pe scurt mai sus.

int Lookup(int key)
{
	Node *node;
	int i;

	memset(jumped, 0, sizeof(jumped));
	for (i = H+1; i < MAX_H; i++) path[i] = head;
	for (node = head, i = H; i >= 0; i--)
	{
		for (; node->link[i] != NULL && node->link[i]->info < key; node = node->link[i])
			jumped[i] += node->jump[i];
		path[i] = node;
	}
	if (path[0]->link[0] != NULL && path[0]->link[0]->info == key) return 1;
	else return 0;
}

Node* LookupByIndex(int index)
{
	Node *node;
	int lvl;

	node = head;
	for (lvl = H; lvl >= 0 && index > 0; lvl--)
		if (node->link[lvl] != NULL && node->jump[lvl] <= index)
		{
			index -= node->jump[lvl];
			node = node->link[lvl];
		}
	if (index > 0) return NULL;
	else return node;
}

void Insert(int key)
{
	if (Lookup(key)) return;

	Node *node = MakeNode(key, 0);
	int J, i;

	if (path[0]->link[0] != NULL)
		path[0]->link[0]->prev = node;
	node->prev = path[0];
	for (J = i = 0; i <= nodeH; i++)
	{
		node->link[i] = path[i]->link[i];
		path[i]->link[i] = node;

		node->jump[i] = path[i]->jump[i] - J;
		path[i]->jump[i] = J + 1;

		J += jumped[i];
	}

	for (i = nodeH + 1; i <= MAX_H; i++)
		path[i]->jump[i]++;

	if (nodeH > H) H = nodeH;
}

void Remove(int key)
{
	if (!Lookup(key)) return;

	Node *node = path[0]->link[0];
	int i;

	if (node->link[0] != NULL)
		node->link[0]->prev = path[0];
	for (i = 0; i < MAX_H; i++)
		if (path[i]->link[i] == node)
		{
			path[i]->link[i] = node->link[i];
			path[i]->jump[i] += (node->jump[i] - 1);
		}
		else	
			path[i]->jump[i]--;
	delete node;
}

Predecesorul si succesorul fiecarui nod se iau pur si simplu din node->prev, respectiv node->link₀