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

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

    }
==

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.

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];

			path[i]->link[i] = node->link[i];
			path[i]->jump[i] += (node->jump[i] - 1);
		}

		else

		else

			path[i]->jump[i]--;
	delete node;
}
==

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