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.

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

3688