h1. Skiplists

(Categoria _Liste_, autor(i) _Stancu Mara Sorin_, _Giurgea Mihnea_)
 

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

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.

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

    }
==

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

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.

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|

	if (path[0]->link[0] != NULL)
		path[0]->link[0]->prev = node;

	node->prev = path[0]->link[0];

	node->prev = path[0];

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

}
==

Predecesorul si succesorul fiecarui nod se iau pur si simplu din node->prev, respectiv node->link{~0~}.

Predecesorul si succesorul fiecarui nod se iau pur si simplu din node->prev, respectiv $node->link{~0~}$

3688