h1. Skiplists

(Creat de ==user(user="wickedman" type="tiny")== la data de _2005-02-05_ categoria _Liste_, autor(i) _Stancu Mara Sorin_)

(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 e 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.
 
==Include(page="template/raw")==

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.

h2. 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 elemntul $x$ nu am sari la elementul {$x+1$}? Ce ar fi daca am sari la {$x+2$}? Acesta este principiul din spatele skiplist.

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, link-urile sunt din ce in ce mai putine si 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.

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.

h2. 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.

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:
== code(cpp) |struct nod {

    int key;

    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.

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.

== code(pas) |type pnod=^nod;
nod=record

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 skip-list 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.

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:

== code(cpp) |nod* x = cap_de_lista;

== code(cpp) |
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)) {

        while (x->link[grad] != NULL && x->link[grad]->key < cheie_cautata)

            x=x->link[grad];

            temp[grad]=x;
        }

        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{~0~}$ (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.

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{~0~}$ (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.

* 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.

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

h2. Skip Lists vs. AVL - Timpi de executie
 
Am testat pe laptopul meu implementearea AVL (vezi "acest articol":http://infoarena.ro/multe-smenuri-de-programare-in-cc-si-nu-numai ) vs. Skiplists (vezi implementarea de mai jos). Laptopul este destul de performant, dar important este raportul dintre timpii de executie la AVL, respectiv Skiplists.
 
|_. Numar de inserari |_. Numar de stergeri |_. Numar de Cautari |_. Timp Skiplists(1) |_. Timp AVL(2) |_. Raportul timpilor (2) / (1)|
|1.000.000	|0	|0	|1.265	|2.656	|2.099604743|
|1.000.000	|0	|1.000.000	|1.479	|2.672	|1.806626099|
|1.000.000	|1.000.000	|0	|1.969	|4.797	|2.436262062|
|1.000.000	|1.000.000	|1.000.000	|2.437	|4.85	|1.990151826|
 
Concluzia: Skiplisturile sunt de 2 ori mai rapide decat AVL-urile.
 
 

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

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.

 
h2. 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.
 
== code(cpp)|
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.
 
== code(cpp)|
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).
 
== code(cpp)|
Node *path[MAX_H], *head;
int jumped[MAX_H], H;
==
 
Si restul functiilor, explicate pe scurt mai sus.
 
== code(cpp)|
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{~0~}$

3688