c++ - Omitir listas, ¿realmente están funcionando tan bien como el reclamo en papel de Pugh?
skip list c++ (2)
Historia
Los tiempos han cambiado un poco desde que William Pugh escribió su artículo original. No vemos ninguna mención en su artículo sobre la jerarquía de memoria de la CPU y el sistema operativo, que se ha convertido en un foco tan actual en la actualidad (ahora a menudo tan importante como la complejidad algorítmica).
Su caso de entrada para la evaluación comparativa tenía un mísero 2 ^ 16 elementos, y el hardware en ese entonces típicamente tenía, como máximo, direccionamiento de memoria extendida de 32 bits disponible. Esto hizo que el tamaño de un puntero sea la mitad del tamaño o más pequeño de lo que estamos acostumbrados hoy en día en máquinas de 64 bits. Mientras tanto, un campo de cadena, por ejemplo, podría ser igual de grande, haciendo que la proporción entre los elementos almacenados en la lista de omisión y los punteros requeridos por un nodo de omisión sea mucho más pequeña, especialmente dado que a menudo necesitamos un número de punteros por nodo de omisión .
C Los compiladores no eran tan agresivos en la optimización en ese momento con respecto a cosas como la asignación de registros y la selección de instrucciones. Incluso un ensamblaje promedio escrito a mano a menudo podría proporcionar un beneficio significativo en el rendimiento. Los consejos del compilador como el register y la inline realidad hicieron un gran problema durante esos tiempos. Si bien esto podría parecer un tanto discutible, ya que tanto una implementación equilibrada de BST como una lista de omitir serían en igualdad de condiciones aquí, la optimización de incluso un ciclo básico fue un proceso más manual. Cuando la optimización es un proceso cada vez más manual, algo que es más fácil de implementar suele ser más fácil de optimizar. Las listas de saltos a menudo se consideran mucho más fáciles de implementar que un árbol de balanceo.
Entonces, todos estos factores probablemente tuvieron parte en las conclusiones de Pugh en ese momento. Sin embargo, los tiempos han cambiado: el hardware ha cambiado, los sistemas operativos han cambiado, los compiladores han cambiado, se ha investigado más sobre estos temas, etc.
Implementación
Aparte de eso, divirtámonos e implementemos una lista de omisión básica. Terminé adaptando la implementación disponible here por pereza. Es un tipo de implementación de tipo "run-of-the-mill", difícilmente diferente de la gran cantidad de implementaciones de listas de salto ejemplares fácilmente accesibles que existen hoy en día.
Vamos a comparar el rendimiento de nuestra implementación con std::set que casi siempre se implementa como un árbol rojo-negro *.
* Algunos pueden preguntarse por qué uso 0 lugar de nullptr y cosas de ese tipo. Es un hábito. En mi lugar de trabajo, todavía tenemos que escribir bibliotecas abiertas que se dirigen a una amplia gama de compiladores, incluidos aquellos que solo admiten C ++ 03, por lo que todavía estoy acostumbrado a escribir código de implementación de nivel medio / bajo de esa manera, e incluso a veces en C, así que perdona el estilo antiguo en el que escribí este código.
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <vector>
#include <cassert>
#include <cstring>
#include <set>
using namespace std;
static const int max_level = 32;
static const float probability = 0.5;
static double sys_time()
{
return static_cast<double>(clock()) / CLOCKS_PER_SEC;
}
static int random_level()
{
int lvl = 1;
while ((static_cast<float>(rand()) / RAND_MAX) < probability && lvl < max_level)
++lvl;
return lvl;
}
template <class T>
class SkipSet
{
public:
SkipSet(): head(0)
{
head = create_node(max_level, T());
level = 0;
}
~SkipSet()
{
while (head)
{
Node* to_destroy = head;
head = head->next[0];
destroy_node(to_destroy);
}
}
bool contains(const T& value) const
{
const Node* node = head;
for (int i=level; i >= 0; --i)
{
while (node->next[i] && node->next[i]->value < value)
node = node->next[i];
}
node = node->next[0];
return node && node->value == value;
}
void insert(const T& value)
{
Node* node = head;
Node* update[max_level + 1];
memset(update, 0, sizeof(Node*)*(max_level + 1));
for (int i = level; i >= 0; i--)
{
while (node->next[i] && node->next[i]->value < value)
node = node->next[i];
update[i] = node;
}
node = node->next[0];
if (!node || node->value != value)
{
int lvl = random_level();
assert(lvl >= 0);
if (lvl > level)
{
for (int i = level + 1; i <= lvl; i++) {
update[i] = head;
}
level = lvl;
}
node = create_node(lvl, value);
for (int i = 0; i <= lvl; i++) {
node->next[i] = update[i]->next[i];
update[i]->next[i] = node;
}
}
}
bool erase(const T& value)
{
Node* node = head;
Node* update[max_level + 1];
memset(update, 0, sizeof(Node*)*(max_level + 1));
for (int i = level; i >= 0; i--)
{
while (node->next[i] && node->next[i]->value < value)
node = node->next[i];
update[i] = node;
}
node = node->next[0];
if (node->value == value)
{
for (int i = 0; i <= level; i++) {
if (update[i]->next[i] != node)
break;
update[i]->next[i] = node->next[i];
}
destroy_node(node);
while (level > 0 && !head->next[level])
--level;
return true;
}
return false;
}
private:
struct Node
{
T value;
struct Node** next;
};
Node* create_node(int level, const T& new_value)
{
void* node_mem = malloc(sizeof(Node));
Node* new_node = static_cast<Node*>(node_mem);
new (&new_node->value) T(new_value);
void* next_mem = calloc(level+1, sizeof(Node*));
new_node->next = static_cast<Node**>(next_mem);
return new_node;
}
void destroy_node(Node* node)
{
node->value.~T();
free(node->next);
free(node);
}
Node* head;
int level;
};
template <class T>
bool contains(const std::set<T>& cont, const T& val)
{
return cont.find(val) != cont.end();
}
template <class T>
bool contains(const SkipSet<T>& cont, const T& val)
{
return cont.contains(val);
}
template <class Set, class T>
void benchmark(int num, const T* elements, const T* search_elements)
{
const double start_insert = sys_time();
Set element_set;
for (int j=0; j < num; ++j)
element_set.insert(elements[j]);
cout << "-- Inserted " << num << " elements in " << (sys_time() - start_insert) << " secs" << endl;
const double start_search = sys_time();
int num_found = 0;
for (int j=0; j < num; ++j)
{
if (contains(element_set, search_elements[j]))
++num_found;
}
cout << "-- Found " << num_found << " elements in " << (sys_time() - start_search) << " secs" << endl;
const double start_erase = sys_time();
int num_erased = 0;
for (int j=0; j < num; ++j)
{
if (element_set.erase(search_elements[j]))
++num_erased;
}
cout << "-- Erased " << num_found << " elements in " << (sys_time() - start_erase) << " secs" << endl;
}
int main()
{
const int num_elements = 200000;
vector<int> elements(num_elements);
for (int j=0; j < num_elements; ++j)
elements[j] = j;
random_shuffle(elements.begin(), elements.end());
vector<int> search_elements = elements;
random_shuffle(search_elements.begin(), search_elements.end());
typedef std::set<int> Set1;
typedef SkipSet<int> Set2;
for (int j=0; j < 3; ++j)
{
cout << "std::set" << endl;
benchmark<Set1>(num_elements, &elements[0], &search_elements[0]);
cout << endl;
cout << "SkipSet" << endl;
benchmark<Set2>(num_elements, &elements[0], &search_elements[0]);
cout << endl;
}
}
En GCC 5.2, -O2, obtengo esto:
std::set
-- Inserted 200000 elements in 0.104869 secs
-- Found 200000 elements in 0.078351 secs
-- Erased 200000 elements in 0.098208 secs
SkipSet
-- Inserted 200000 elements in 0.188765 secs
-- Found 200000 elements in 0.160895 secs
-- Erased 200000 elements in 0.162444 secs
... lo que es bastante horrible. Somos casi el doble de lentos en todo el tablero.
Mejoramiento
Sin embargo, hay una optimización deslumbrante que podemos hacer. Si nos fijamos en Node , sus campos actuales se ven así:
struct Node
{
T value;
struct Node** next;
};
Esto implica que la memoria para los campos de Nodo y su lista de los siguientes punteros son dos bloques separados, posiblemente con un paso muy distante entre ellos, como por ejemplo:
[Node fields]-------------------->[next0,next1,...,null]
Esto hace mal para la localidad de referencia. Si queremos mejorar las cosas aquí, deberíamos fusionar estos bloques de memoria en una única estructura contigua, así:
[Node fields,next0,next1,...,null]
Podemos lograr esto a través del lenguaje de estructura de longitud variable común en C. Es un poco incómodo de implementar en C ++ que no lo admite tan directamente, pero podemos emular el efecto así:
struct Node
{
T value;
struct Node* next[1];
};
Node* create_node(int level, const T& new_value)
{
void* node_mem = malloc(sizeof(Node) + level * sizeof(Node*));
Node* new_node = static_cast<Node*>(node_mem);
new (&new_node->value) T(new_value);
for (int j=0; j < level+1; ++j)
new_node->next[j] = 0;
return new_node;
}
void destroy_node(Node* node)
{
node->value.~T();
free(node);
}
Con este modesto ajuste, ahora tenemos estos tiempos:
SkipSet (Before)
-- Inserted 200000 elements in 0.188765 secs
-- Found 200000 elements in 0.160895 secs
-- Erased 200000 elements in 0.162444 secs
SkipSet (After)
-- Inserted 200000 elements in 0.132322 secs
-- Found 200000 elements in 0.127989 secs
-- Erased 200000 elements in 0.130889 secs
... lo que nos acerca considerablemente a competir con el rendimiento de std::set .
Generador de números aleatorios
Una implementación de lista de omisión realmente eficiente generalmente requerirá un RNG muy rápido. Sin embargo, descubrí durante una sesión de creación de perfiles rápida que solo se dedica una parte muy pequeña del tiempo a generar un nivel / altura aleatorio, apenas lo suficiente como para considerarlo un punto de acceso. También afectaría los tiempos de inserción a menos que proporcionara una distribución más uniforme, por lo que he decidido omitir esta optimización.
Asignador de memoria
En este punto, diría que tenemos una visión general bastante razonable de lo que podemos esperar con una implementación de lista de omisión frente a una BST:
Insertion
-- std::set: 0.104869 secs
-- SkipList: 0.132322 secs
Search:
-- std::set: 0.078351 secs
-- SkipList: 0.127989 secs
Removal:
-- std::set: 0.098208 secs
-- SkipList: 0.130889 secs
Sin embargo, si queremos un poco más de soldado, podemos utilizar un asignador fijo. En este punto, estamos haciendo trampa un poco ya que std::set está diseñado para funcionar con cualquier asignador de propósito general que cumpla con los requisitos de interfaz de un asignador estándar. Pero echemos un vistazo a usar un asignador fijo:
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <vector>
#include <cassert>
#include <set>
using namespace std;
static const int max_level = 32;
class FixedAlloc
{
public:
FixedAlloc(): root_block(0), free_element(0), type_size(0), block_size(0), block_num(0)
{
}
FixedAlloc(int itype_size, int iblock_size): root_block(0), free_element(0), type_size(0), block_size(0), block_num(0)
{
init(itype_size, iblock_size);
}
~FixedAlloc()
{
purge();
}
void init(int new_type_size, int new_block_size)
{
purge();
block_size = max(new_block_size, type_size);
type_size = max(new_type_size, static_cast<int>(sizeof(FreeElement)));
block_num = block_size / type_size;
}
void purge()
{
while (root_block)
{
Block* block = root_block;
root_block = root_block->next;
free(block);
}
free_element = 0;
}
void* allocate()
{
assert(type_size > 0);
if (free_element)
{
void* mem = free_element;
free_element = free_element->next_element;
return mem;
}
// Create new block.
void* new_block_mem = malloc(sizeof(Block) - 1 + type_size * block_num);
Block* new_block = static_cast<Block*>(new_block_mem);
new_block->next = root_block;
root_block = new_block;
// Push all but one of the new block''s elements to the free pool.
char* mem = new_block->mem;
for (int j=1; j < block_num; ++j)
{
FreeElement* element = reinterpret_cast<FreeElement*>(mem + j * type_size);
element->next_element = free_element;
free_element = element;
}
return mem;
}
void deallocate(void* mem)
{
FreeElement* element = static_cast<FreeElement*>(mem);
element->next_element = free_element;
free_element = element;
}
void swap(FixedAlloc& other)
{
std::swap(free_element, other.free_element);
std::swap(root_block, other.root_block);
std::swap(type_size, other.type_size);
std::swap(block_size, other.block_size);
std::swap(block_num, other.block_num);
}
private:
struct Block
{
Block* next;
char mem[1];
};
struct FreeElement
{
struct FreeElement* next_element;
};
// Disable copying.
FixedAlloc(const FixedAlloc&);
FixedAlloc& operator=(const FixedAlloc&);
struct Block* root_block;
struct FreeElement* free_element;
int type_size;
int block_size;
int block_num;
};
static double sys_time()
{
return static_cast<double>(clock()) / CLOCKS_PER_SEC;
}
static int random_level()
{
int lvl = 1;
while (rand()%2 == 0 && lvl < max_level)
++lvl;
return lvl;
}
template <class T>
class SkipSet
{
public:
SkipSet(): head(0)
{
for (int j=0; j < max_level; ++j)
allocs[j].init(sizeof(Node) + (j+1)*sizeof(Node*), 4096);
head = create_node(max_level, T());
level = 0;
}
~SkipSet()
{
while (head)
{
Node* to_destroy = head;
head = head->next[0];
destroy_node(to_destroy);
}
}
bool contains(const T& value) const
{
const Node* node = head;
for (int i=level; i >= 0; --i)
{
while (node->next[i] && node->next[i]->value < value)
node = node->next[i];
}
node = node->next[0];
return node && node->value == value;
}
void insert(const T& value)
{
Node* node = head;
Node* update[max_level + 1] = {0};
for (int i=level; i >= 0; --i)
{
while (node->next[i] && node->next[i]->value < value)
node = node->next[i];
update[i] = node;
}
node = node->next[0];
if (!node || node->value != value)
{
const int lvl = random_level();
assert(lvl >= 0);
if (lvl > level)
{
for (int i = level + 1; i <= lvl; ++i)
update[i] = head;
level = lvl;
}
node = create_node(lvl, value);
for (int i = 0; i <= lvl; ++i)
{
node->next[i] = update[i]->next[i];
update[i]->next[i] = node;
}
}
}
bool erase(const T& value)
{
Node* node = head;
Node* update[max_level + 1] = {0};
for (int i=level; i >= 0; --i)
{
while (node->next[i] && node->next[i]->value < value)
node = node->next[i];
update[i] = node;
}
node = node->next[0];
if (node->value == value)
{
for (int i=0; i <= level; ++i) {
if (update[i]->next[i] != node)
break;
update[i]->next[i] = node->next[i];
}
destroy_node(node);
while (level > 0 && !head->next[level])
--level;
return true;
}
return false;
}
void swap(SkipSet<T>& other)
{
for (int j=0; j < max_level; ++j)
allocs[j].swap(other.allocs[j]);
std::swap(head, other.head);
std::swap(level, other.level);
}
private:
struct Node
{
T value;
int num;
struct Node* next[1];
};
Node* create_node(int level, const T& new_value)
{
void* node_mem = allocs[level-1].allocate();
Node* new_node = static_cast<Node*>(node_mem);
new (&new_node->value) T(new_value);
new_node->num = level;
for (int j=0; j < level+1; ++j)
new_node->next[j] = 0;
return new_node;
}
void destroy_node(Node* node)
{
node->value.~T();
allocs[node->num-1].deallocate(node);
}
FixedAlloc allocs[max_level];
Node* head;
int level;
};
template <class T>
bool contains(const std::set<T>& cont, const T& val)
{
return cont.find(val) != cont.end();
}
template <class T>
bool contains(const SkipSet<T>& cont, const T& val)
{
return cont.contains(val);
}
template <class Set, class T>
void benchmark(int num, const T* elements, const T* search_elements)
{
const double start_insert = sys_time();
Set element_set;
for (int j=0; j < num; ++j)
element_set.insert(elements[j]);
cout << "-- Inserted " << num << " elements in " << (sys_time() - start_insert) << " secs" << endl;
const double start_search = sys_time();
int num_found = 0;
for (int j=0; j < num; ++j)
{
if (contains(element_set, search_elements[j]))
++num_found;
}
cout << "-- Found " << num_found << " elements in " << (sys_time() - start_search) << " secs" << endl;
const double start_erase = sys_time();
int num_erased = 0;
for (int j=0; j < num; ++j)
{
if (element_set.erase(search_elements[j]))
++num_erased;
}
cout << "-- Erased " << num_found << " elements in " << (sys_time() - start_erase) << " secs" << endl;
}
int main()
{
const int num_elements = 200000;
vector<int> elements(num_elements);
for (int j=0; j < num_elements; ++j)
elements[j] = j;
random_shuffle(elements.begin(), elements.end());
vector<int> search_elements = elements;
random_shuffle(search_elements.begin(), search_elements.end());
typedef std::set<int> Set1;
typedef SkipSet<int> Set2;
cout << fixed << setprecision(3);
for (int j=0; j < 2; ++j)
{
cout << "std::set" << endl;
benchmark<Set1>(num_elements, &elements[0], &search_elements[0]);
cout << endl;
cout << "SkipSet" << endl;
benchmark<Set2>(num_elements, &elements[0], &search_elements[0]);
cout << endl;
}
}
* También hice un pequeño cambio en random_level para que asumiera una probabilidad del 50% después de descubrir que esto parece funcionar bastante bien.
Al usar un asignador fijo, podemos asignar y desasignar rápidamente los elementos utilizando una estrategia de tiempo constante muy simple y, lo que es más importante, asignar nodos de una manera tal que los nodos con la misma altura (los más a los que se accede con mayor frecuencia) se asignen de manera más contigua con respeto entre sí (aunque no en un orden secuencial ideal). Esto mejora los tiempos para:
Insertion
-- std::set: 0.104869 secs
-- SkipList: 0.103632 secs
Search:
-- std::set: 0.078351 secs
-- SkipList: 0.089910 secs
Removal:
-- std::set: 0.098208 secs
-- SkipList: 0.089224 secs
... lo que no está mal durante unos 40 minutos de trabajo contra std::set que ha sido pinchado y mejorado por expertos de toda la industria. También tenemos eliminaciones más rápidas que std::set (los tiempos de inserción fluctúan un poco en mi máquina, yo diría que están aproximadamente a la par).
Por supuesto que hicimos trampa para aplicar este último paso. El uso de un asignador personalizado inclina las cosas a nuestro favor y también cambia las características del contenedor de tal manera que su memoria no se puede liberar hasta que se borra, se destruye o se compacta. Puede marcar la memoria como no utilizada y recuperarla en inserciones posteriores, pero no puede hacer que la memoria que utiliza esté disponible para aquellos que se encuentran fuera de la lista de omisión. Tampoco me molesté en prestar atención a la alineación adecuada para todos los tipos posibles de T que serían necesarios para generalizarla de verdad.
Entrada ordenada
Intentemos usar esto contra la entrada ordenada. Para hacerlo, simplemente comente las dos declaraciones random_shuffle . Por mi parte, ahora tengo estos tiempos:
std::set
-- Inserted 200000 elements in 0.044 secs
-- Found 200000 elements in 0.023 secs
-- Erased 200000 elements in 0.019 secs
SkipSet
-- Inserted 200000 elements in 0.027 secs
-- Found 200000 elements in 0.023 secs
-- Erased 200000 elements in 0.016 secs
... y ahora nuestro SkipSet supera a std::set en todas las áreas, aunque solo para este tipo de caso excepcional.
Conclusión
Así que no sé exactamente lo que esto dice sobre las listas de omisión. Con casi ningún tiempo y esfuerzo, estuvimos muy cerca de competir con std::set *. Sin embargo, no lo superamos y tuvimos que hacer trampa con un asignador de memoria para estar realmente cerca.
* Tenga en cuenta que el kilometraje puede variar entre máquinas, implementaciones de proveedores de std::set , etc.
Los tiempos han cambiado bastante desde que el periódico Pugh escribió en 1989.
Hoy en día, los beneficios de la localidad de referencia dominan las cosas hasta un punto en el que incluso un algoritmo de complejidad linearítmica puede superar a uno lineal, siempre que el primero sea considerablemente más caché o amigable con las páginas. Prestar mucha atención a la forma en que el sistema toma trozos de memoria de los niveles superiores de la jerarquía de memoria (por ejemplo, etapa secundaria) con memoria más lenta pero más grande y hasta la pequeña línea de caché L1 y el registro de adolescentes es más importante que nunca, y Ya no es "micro" si me preguntas cuándo los beneficios pueden rivalizar con las mejoras algorítmicas.
La lista de omisiones está potencialmente dañada aquí dado el tamaño considerablemente mayor de los nodos y, lo que es más importante, el tamaño variable de los nodos (lo que dificulta su asignación de manera muy eficiente).
Una cosa que no observamos es la naturaleza localizada en la que una lista de omisiones se actualiza en la inserción. Esto tiende a afectar a muchas menos áreas de las que requiere un árbol de balanceo para reequilibrar girando los nodos principales. Como resultado, una lista de omisión puede ofrecer una implementación potencialmente más eficiente de un conjunto o mapa concurrente.
Otra característica prometedora de una lista de omisión es que es simplemente una lista vinculada al nivel más bajo. Como resultado, ofrece un recorrido secuencial de tiempo lineal muy simple sin tener que descender por las ramas del árbol con complejidad linealitmica, por lo que es potencialmente muy bueno si queremos hacer muchas iteraciones de tiempo lineal a través de todos los elementos contenidos .
Pero siempre recuerda:
Una técnica es tan buena como puede ser aplicada en manos del implementador.
Estoy tratando de implementar una lista de omitir que funcione tan bien como una BST utilizando una sobrecarga de memoria adicional mínima, por el momento, incluso sin considerar ninguna restricción de memoria, el rendimiento de mi implementación de SkipList está muy lejos incluso de una implementación muy equilibrada de BST balanceada - por así decirlo, hecho a mano BTS :) -
Como referencia, estoy usando el documento original de William Pugh PUG89 y la implementación que encontré en los algoritmos en C de Sedgewick -13.5-. Mi código es una implementación recursiva, aquí está la pista de la operación de inserción y búsqueda:
sl_node* create_node()
{
short lvl {1};
while((dist2(en)<p)&&(lvl<max_level))
++lvl;
return new sl_node(lvl);
}
void insert_impl(sl_node* cur_node,
sl_node* new_node,
short lvl)
{
if(cur_node->next_node[lvl]==nullptr || cur_node->next_node[lvl]->value > new_node->value){
if(lvl<new_node->lvl){
new_node->next_node[lvl] = cur_node->next_node[lvl];
cur_node->next_node[lvl] = new_node;
}
if(lvl==0) return;
insert_impl(cur_node,new_node,lvl-1);
return;
}
insert_impl(cur_node->next_node[lvl],new_node,lvl);
}
sl_node* insert(long p_val)
{
sl_node* new_node = create_node();
new_node->value = p_val;
insert_impl(head, new_node,max_level-1);
return new_node;
}
Y este es el código para la operación de búsqueda:
sl_node* find_impl(sl_node* cur_node,
long p_val,
int lvl)
{
if(cur_node==nullptr) return nullptr;
if(cur_node->value==p_val) return cur_node;
if(cur_node->next_node[lvl] == nullptr || cur_node->next_node[lvl]->value>p_val){
if(lvl==0) return nullptr;
return find_impl(cur_node,p_val,lvl-1);
}
return find_impl(cur_node->next_node[lvl],p_val,lvl);
}
sl_node* find(long p_val)
{
return find_impl(head,p_val,max_level-1);
}
Un sl_node -skip list node- tiene este aspecto:
struct sl_node
{
long value;
short lvl;
sl_node** next_node;
sl_node(int l) : lvl(l)
{
next_node = new sl_node*[l];
for(short i{0};i<l;i++)
next_node[i]=nullptr;
}
~sl_node()
{
delete[] next_node;
}
};
Como puede ver, esta implementación no tiene nada especial ni avanzada si se compara con la implementación del libro, no compartiré el código BTS Balaced ya que no creo que sea necesario aquí, pero es un BTS muy básico con una función de rebalance activada durante el inserción cuando la nueva altura del nodo es mayor a 16 * lg (n) donde n es el número de nodos.
Por decirlo así, reequilibrio de los tres solo si la altura máxima es 16 veces mayor que la mejor teórica, como dije, este BST casero sencillo funciona mucho mejor que el Skip List casero.
Pero primero, echemos un vistazo a algunos datos, usando p = .5 y n = 262144 el nivel de los nodos en la Lista de Saltos tiene la siguiente distribución:
1:141439, 53.9547%
2:65153, 24.8539%
3:30119, 11.4895%
4:13703, 5.22728%
5:6363, 2.42729%
6:2895, 1.10435%
7:1374, 0.524139%
8:581, 0.221634%
9:283, 0.107956%
10:117, 0.044632%
11:64, 0.0244141%
12:31, 0.0118256%
13:11, 0.00419617%
14:5, 0.00190735%
15:1, 0.00038147%
16:5, 0.00190735%
Lo cual es casi perfecto -oh, ¡este es uno grande! - coincide con la teoría del artículo, es decir: 50% nivel 1, 25% nivel 2 y así sucesivamente. Los datos de entrada provinieron de mi mejor generador pseudoaleatorio disponible, también conocido como std :: random_device con std :: default_random_engine y una distribución int uniforme. La entrada me parece bastante aleatoria :)!
El tiempo requerido para buscar ''todos'' los 262144 elementos en la Lista de Saltos (en orden aleatorio) es de 315 ms en mi máquina, mientras que para la misma operación de búsqueda en el BTS ingenuo, el tiempo requerido es de 134 ms, por lo que el BTS es casi dos veces más rápido que la SkipList. Eso no es exactamente lo que esperaba de "Los algoritmos de lista de saltos tienen los mismos límites de tiempo esperados asintóticos que los árboles balanceados y son simples, más rápidos y usan menos espacio" PUG89 .
El tiempo requerido para la "inserción" de los nodos es de 387 ms para la lista de saltos y de 143 ms para la BTS, nuevamente, una BST ingenua funciona mejor.
Las cosas se ponen un poco más interesantes si, en lugar de usar una secuencia aleatoria de números de entrada, uso una secuencia ordenada, aquí mi pobre BST hecha en casa se vuelve lenta, y la inserción de 262144 int ordenados toma 2866 ms, mientras que la Lista de saltos requiere solo 168 ms.
Pero, cuando se llega al tiempo de búsqueda, ¡el BST es aún más rápido! para la entrada ordenada tenemos 234 ms frente a 77 ms, este BST es 3 veces más rápido.
Con diferentes valores del factor p obtuve resultados de rendimiento ligeramente diferentes:
Y por último, pero no menos importante, el gráfico de uso de la memoria, que como puede esperar, confirma que si aumentamos la cantidad de niveles por nodo, impactamos significativamente la huella digital de la memoria. El uso de la memoria se calcula solo como una suma del espacio requerido para almacenar los punteros adicionales para todo el nodo.
Después de todo esto, ¿alguien de ustedes me puede proporcionar un comentario sobre cómo implementar una SkipList que funcione tan bien como un BTS (sin contar la sobrecarga de memoria adicional)?
Conozco el artículo de DrDobbs LINK sobre SkipList, y revisé todo el documento, el código para la operación de búsqueda e inserción coincide exactamente con la implementación original de PUG89 por lo que debería ser tan bueno como el mío, y el artículo no proporciona ningún rendimiento. Análisis de todos modos, no encontré ninguna otra fuente. ¿Me puedes ayudar?
Cualquier comentario es muy apreciado!
¡Gracias! :)
Dudo que la lista de omisiones fuera la mejor opción que un árbol AVL incluso en 1989. En 1989 o 1990, como estudiante implementé ambas: no fue una buena implementación de la lista de omisiones, debo admitir que era un novato. en ese momento.
Sin embargo, el árbol AVL ya no era difícil de implementar. Por el contrario, tuve dificultades con los punteros hacia adelante de longitud variable del salto en la lista implementada en la modula 2, que resolví principalmente utilizando siempre un máximo de 16 punteros siguientes.
La ventaja de menos operaciones en la inserción, nunca vi. El árbol AVL, si recuerdo correctamente, tenía un promedio de no más de 2 ó 3 operaciones. Así que el reequilibrio caro sucede no a menudo.
Creo que fue más una exageración.