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

12

Para una tarea, necesito entender cómo funciona una omitir lista .

He estado programando por un poco más de 2 años (sé que no es tan largo en la realidad), 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é en Code Review para una implementación de ejemplo, y encontré una sola 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 sola letra, no tengo ni 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?

    
pregunta Carcigenicate 19.06.2015 - 01:13

1 respuesta

27

En días pasados, en la clase de estructuras de datos aprendimos cómo árboles AVL . Hubiera tenido eso en una de mis clases, pero el instructor dijo "en realidad nunca usarás esto" y en vez de eso, aprendimos 2-3 árboles y b * árboles. Esos eran días en los que la memoria estaba apretada y los procesos se enlazaban individualmente. No usaste un 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, ya que hay más memoria disponible y la concurrencia es un problema (no es necesario que se bloquee mucho al actuar como escritor en una lista de omisión, en comparación con todo lo que tiene 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 de usar.

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

Usted necesitará entender por qué desea seleccionar un ConcurrentSkipListMap en Java en lugar de un HashMap o TreeMap o cualquiera de las otras implementaciones de mapas.

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 obtiene ninguna ventaja real con su búsqueda.

Digamos que tenemos este árbol:

Yinsertamosun'8'enél.Ahoratenemos:

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

Ytienesunárbolequilibradodenuevo.Peroesofuemuchamagiaconlaqueagitémimano.

Permitetomarunalistadeomisión.

Este es uno idealizado. Pocos lo son, pero muestra la naturaleza equilibrada del árbol binario a la que se aproxima el ideal de lista de saltos.

Ahora, queremos insertar un 6 en allí. Esto lo está insertando como una lista enlazada. Sin embargo, comenzamos por la parte superior y bajamos. Los puntos superiores a 5. Es 6 > 5? Sí. Ok, la parte superior apunta hacia el final ahora, así que bajamos la pila (estamos en el 5). El siguiente es 7. Es 6 > 7? No Así que bajamos un nivel y estamos en el nivel base, por lo 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.

Permiteinsertarese8ahora.8>5?Sí.8>7?Sí.Yahoraestamosnuevamenteenelnivelinferiordespuésdeseguirlasflechasylapilaalrededoryprobamos8>11?NoAsíqueinsertamosel8aladerechadel7.

Lanzamosunamoneda:cabezasqueconstruimos,colasquenosquedamos.Cruz.Nosenecesitahacernadamás.

En el árbol equilibrado, estaríamos preocupados por el hecho de que el árbol no esté equilibrado ahora. Pero esto no es un árbol, es una lista de saltos. aproximamos 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 de nuevo, cabezas otra vez! Dale la vuelta otra vez, está bien, hay una cola. Dos niveles por encima de la lista vinculada base.

Laventajaaquíesqueahorasivamosainsertarun12,podemosskipde5a10sinhacertodasesasotrascomparaciones.Podemossaltarsobreellosconlalistadesaltos.Ynotenemosquepreocuparnosporelárbolequilibrado,lanaturalezaprobabilísticadelapilamientolohacepornosotros.

¿Porquéesestotanútil?Porquealinsertarel10puedohacerlobloqueandolaescrituraenlospunteros5y7y8enlugardetodalaestructura.Ymientrashagoeso,loslectorespuedenseguirrevisandolalistadeomisionessintenerunestadoinconsistente.Parausoconcurrente,esmásrápidonotenerquebloquear.Pararecorrerlacapainferior,esmásrápidoqueunárbol(lasalegríasdelosalgoritmosBFSyDFSparalanavegaciónenárbol,notienequepreocuparseporellos).

¿Loencontrarás?Probablementeloverásenusoenlugares.YluegosabrásporquéelautoreligióesaimplementaciónenlugardeunTreeMapoHashMapparalaestructura.

Granpartedeestohasidotomadodemiblog: The Skip List

    
respondido por el user40980 19.06.2015 - 01:56

Lea otras preguntas en las etiquetas