¿Cómo funciona una lista de omisión?

Para una tarea, necesito entender cómo funciona una lista de omisión .

He estado programando durante un poco más de 2 años (sé que en realidad no es tan largo), y nunca he oído hablar de una lista de omisión.

He revisado todas las guías que puedo encontrar, y todavía apenas entiendo cómo funcionan. Incluso busqué Code Review para una implementación de ejemplo, y encontré solo una revisión; y ni siquiera es una implementación completa. Revisé la implementación de muestra proporcionada por el curso, y es absolutamente atroz. Entre la falta de métodos adecuados y los nombres de variables de una letra, no tengo idea de cómo funciona.

¿Cómo funciona una lista de omisión? ¿Se requiere el conocimiento de una lista de omisión para comprender estructuras de datos más avanzadas?

En días antiguos, en la clase de estructuras de datos, aprendimos cómo funcionaban los árboles AVL . Hubiera tenido eso en una de mis clases, pero el instructor dijo "nunca usarás esto" y en su lugar nos hizo aprender 2-3 árboles y b * árboles. Eran días en que la memoria era escasa y los procesos estaban enhebrados individualmente. No usaste una deque cuando una lista enlazada individualmente funcionaría igual de bien.

La lista de omisión es mucho más común hoy en día con más memoria disponible y la concurrencia es un problema (no es necesario bloquear mucho para actuar como escritor en una lista de omisión, en comparación con todo con un árbol AVL).

Francamente, es mi estructura de datos favorita ahora que es algo que puedo razonar fácilmente sobre cómo funciona debajo y dónde será ventajoso o desventajoso usarlo.

No necesitará escribir uno desde cero (a menos que lo obtenga como una pregunta de entrevista, pero es muy probable que implemente un árbol AVL).

Usted está va a tener que entender por qué desea seleccionar una ConcurrentSkipListMapen Java en lugar de una HashMapo TreeMapo cualquiera de las otras implementaciones mapa.

Para comprender cómo funciona, debe comprender cómo funciona un árbol binario. Espera, déjame enmendar eso. Debe comprender cómo funciona un árbol binario equilibrado . Sin equilibrar un árbol binario, no obtienes ninguna ventaja real con su búsqueda.

Digamos que tenemos este árbol:

E insertamos un '8' en él. Ahora tenemos:

Y eso no está equilibrado. Entonces, vamos y hacemos la magia de equilibrarlo a través de alguna implementación ...

Y tienes un árbol equilibrado de nuevo. Pero eso fue mucha magia. Agité mi mano.

Tomemos una lista de omisión.

Este resulta ser uno idealizado. Pocos lo son, pero muestra la naturaleza equilibrada del árbol binario que el ideal de skiplist se aproxima.

Ahora, queremos insertar un 6 allí. Esto lo está insertando como una lista vinculada. Sin embargo, comenzamos en la parte superior y bajamos. Los puntos superiores a 5. ¿Es 6> 5? Si. De acuerdo, los puntos más altos ahora están hasta el final, así que bajamos la pila (estamos en el 5). El siguiente es 7. ¿Es 6> 7? No Entonces bajamos un nivel y estamos en el nivel base, así que insertamos 6 a la derecha del 5.

Lanzamos una moneda: cabezas que construimos, colas que nos quedamos. Cruz. No se necesita hacer nada más.

Inserte ese 8 ahora. 8> 5? Sí. 8> 7? Sí. ¿Y ahora estamos nuevamente en el nivel inferior después de seguir las flechas y la pila y probar 8> 11? No Entonces insertamos el 8 a la derecha del 7.

Lanzamos una moneda: cabezas que construimos, colas que nos quedamos. Cruz. No se necesita hacer nada más.

En el árbol equilibrado, estaríamos muy preocupados porque el árbol no está equilibrado ahora. Pero esto no es un árbol, es una lista de omisión. Nos aproximamos a un árbol equilibrado.

Ahora insertemos un 10. Evitaré todas las comparaciones.

Lanzamos una moneda: cabezas que construimos, colas que nos quedamos. Cabezas! ¡Y voltéalo otra vez, Jefes otra vez! Voltéalo de nuevo, está bien, hay colas. Dos niveles por encima de la lista vinculada base.

La ventaja aquí es que ahora, si vamos a insertar un 12, podemos saltar de 5 a 10 sin hacer todas esas otras comparaciones. Podemos omitirlos con la lista de omisión. Y no tenemos que preocuparnos por el árbol equilibrado: la naturaleza probabilística del apilamiento lo hace por nosotros.

¿Por qué es esto tan útil? Porque al insertar el 10 puedo hacerlo bloqueando la escritura en los punteros 5 y 7 y 8 en lugar de toda la estructura. Y mientras lo hago, los lectores pueden seguir revisando la lista de omisión sin tener un estado inconsistente. Para uso concurrente, es más rápido no tener que bloquear. Para iterar sobre la capa inferior, es más rápido que un árbol (las alegrías de los algoritmos BFS y DFS para la navegación del árbol, no tiene que preocuparse por ellos).

¿Lo encontrarás? Probablemente lo verá en uso en algunos lugares. Y entonces sabrás por qué el autor eligió esa implementación en lugar de una TreeMapo HashMappara la estructura.

Gran parte de esto ha sido tomado de mi blog: The Skip List