data-structures binary-tree skip-lists

data structures - Omitir listas: ¿alguna vez las usó?



data-structures binary-tree (6)

Java 1.6 (Java SE 6) introdujo ConcurrentSkipListSet y ConcurrentSkipListMap en el marco de colecciones. Por lo tanto, especulo que alguien por ahí realmente los está usando.

Las listas salteadas tienden a ofrecer mucha menos contención para las cerraduras en una situación multiproceso, y (probabilísticamente) tienen características de rendimiento similares a los árboles.

Ver el documento original [pdf] por William Pugh

Me pregunto si alguien aquí alguna vez ha usado una lista de omisiones . Parece tener más o menos las mismas ventajas que un árbol binario equilibrado, pero es más fácil de implementar. Si lo has hecho, ¿has escrito el tuyo propio o has usado una biblioteca preescrita (y si es así, cómo se llamaba)?

Hace años implementé el mío para una clase de algoritmos probabilísticos. No conozco ninguna implementación de biblioteca, pero ha pasado mucho tiempo. Es bastante simple de implementar. Según recuerdo, tenían algunas propiedades realmente buenas para grandes conjuntos de datos y evitaban algunos de los problemas del reequilibrio. Creo que la implementación también es más simple que los intentos binarios en general. Hay una buena discusión y algunos ejemplos de código de C ++ aquí:

http://www.ddj.us/cpp/184403579?pgno=1

También hay un applet con una demostración en ejecución. Lindo brillo de Java de los años 90 aquí:

http://www.geocities.com/siliconvalley/network/1854/skiplist.html

Implementé una variante que denominé una Lista de saltos inversos para un motor de reglas hace unos años. Casi lo mismo, pero los enlaces de referencia van hacia atrás desde el último elemento.

Esto se debe a que fue más rápido para insertar elementos ordenados que eran más probables hacia el back-end de la colección.

Fue escrito en C # y tomó algunas iteraciones para trabajar con éxito.

Tengo entendido que no son tanto una alternativa útil a los árboles binarios (por ejemplo, árboles rojo-negro) como a B-trees para el uso de bases de datos, por lo que puede mantener el n. ° de niveles a un mínimo factible y tratar w / registros de base K en lugar de registros de base 2 para las características de rendimiento. Los algoritmos para listas de omisiones probabilísticas son (IMHO) más fáciles de obtener a la derecha que los algoritmos de árbol B correspondientes. Además, hay algo de literatura sobre listas de omisiones sin bloqueo. Miré su uso hace unos meses, pero luego abandoné el esfuerzo de descubrir la biblioteca HDF5 .

literatura sobre el tema:

Papeles de Bill Pugh:

documentos / tutoriales no académicos:

Las listas de salto son fáciles de implementar. Pero, ajustando los punteros en una lista de omisiones en caso de inserción y eliminación, debe tener cuidado. No lo he usado en un programa real pero he usado algunos perfiles de tiempo de ejecución. Las listas de omisiones son diferentes de los árboles de búsqueda. La similitud es que proporciona un registro promedio (n) para un período de operaciones del diccionario como el árbol de distribución. Es mejor que un árbol de búsqueda desequilibrado, pero no es mejor que un árbol equilibrado.

Cada nodo de la lista de omisiones tiene punteros hacia delante que representan las conexiones actuales-> siguiente () con los diferentes niveles de la lista de omisiones. Por lo general, este nivel está limitado a un máximo de ln (N). Entonces, si N = 1million el nivel es 13. Habrá muchos punteros y en Java esto significa el número de punteros para implementar tipos de datos de referencia. donde como un árbol de búsqueda equilibrada tiene menos y da el mismo tiempo de ejecución !!.

SkipList Vs Splay Tree Vs Hash Como se describe para las operaciones de búsqueda de diccionario, una tabla hash eliminada dará como resultado menos de 0.010 ms, mientras que un árbol desplegable da ~ 1 ms y omite una lista de ~ 720ms.

En realidad, para uno de mis proyectos estoy implementando mi propio STL completo. Y utilicé un skiplist para implementar mi std::map . La razón por la que lo hice es porque es un algoritmo simple que está muy cerca del rendimiento de un árbol balanceado pero tiene capacidades de iteración mucho más simples.

Además, el QMap de QT4 también fue una lista de skiplist, que fue la inspiración original para mi uso en my std::map .