Me pregunto si alguien aquí alguna vez ha usado skip list. 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)?Omitir listas: ¿alguna vez las usaste?
Hace años implementé el mío propio 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 bonita discusión y algo de código C++ muestra aquí:
http://www.ddj.us/cpp/184403579?pgno=1
También hay un applet con una demostración en funcionamiento. Linda del 90 de Java brillo aquí:
http://www.geocities.com/siliconvalley/network/1854/skiplist.html
Estoy aceptando esta por el artículo DDJ al que hace referencia. Disculpas a Even y Steve, aceptaría las tres respuestas si pudiera. –
Implementé una variante que denominé una Lista de salto inverso para un motor de reglas hace algunos 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 propensos a la parte de atrás de la colección.
Fue escrito en C# y tomó algunas iteraciones para funcionar correctamente.
¿No podría invertir la comparación para el tipo y utilizar una lista de reproducción estándar para obtener el mismo resultado? –
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 mucho capacidades de iteración más simples.
Además, QT4's QMap también fue una lista de skiplist, que fue la inspiración original para mi uso en mi std::map.
Evan, ¿ha hecho que su código de skiplist esté disponible en cualquier lugar? Gracias – dkantowitz
aún no del todo, pero las cosas están casi al punto donde puedo lanzar mi STL. Pero hay muchas implementaciones de ejemplos de listas de omisiones. –
Sí, hay un montón de código de lista de saltos disponible. Estaba buscando algo que cumpla específicamente con la interfaz std :: map <>. QMap se ve bastante cerca, así que intentaré eso. Gracias – dkantowitz
Java 1.6 (Java SE 6) introdujo ConcurrentSkipListSetConcurrentSkipListMap y al marco de las colecciones. Por lo tanto, especulo que alguien por ahí realmente los está usando.
Las listas saltadas tienden a ofrecer una contención mucho menor para las cerraduras en una situación multiproceso, y (probabilísticamente) tienen características de rendimiento similares a los árboles.
Ver the original paper [pdf] de William Pugh
Mi opinión es que no lo son tanto una alternativa útil a los árboles binarios (por ejemplo, árboles rojo-negro), ya que se van a árboles B para el uso de la base de datos, para que pueda mantener el n. ° de niveles a un mínimo factible y repartir los registros de w/base-K en lugar de los 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 por Bill Pugh:
no académicos papeles/tutoriales:
Saltar Las listas 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 adelante 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, ya que el árbol de splay da ~ 1 ms y la lista de omisiones ~ 720ms.
Véase también http://stackoverflow.com/questions/256511/skip-list-vs-binary-tree –