En informática , una lista de omisión (o skiplist ) es una estructura de datos probabilística que permite una complejidad promedio para la búsqueda, así como una complejidad promedio para la inserción dentro de una secuencia ordenada de elementos. Por lo tanto, puede obtener las mejores características de una matriz ordenada (para búsqueda) mientras mantiene una estructura similar a una lista vinculada que permite la inserción, lo cual no es posible con una matriz estática. La búsqueda rápida es posible manteniendo una jerarquía vinculada de subsecuencias, donde cada subsecuencia sucesiva omite menos elementos que la anterior (consulte la imagen a continuación a la derecha). La búsqueda comienza en la subsecuencia más escasa hasta que se encuentran dos elementos consecutivos, uno más pequeño y otro más grande o igual que el elemento buscado. A través de la jerarquía vinculada, estos dos elementos se vinculan a elementos de la siguiente subsecuencia más dispersa, donde la búsqueda continúa hasta que finalmente se busca en la secuencia completa. Los elementos que se omiten pueden elegirse de forma probabilística [2] o determinista [3] , siendo el primero más común.
Una lista de omisión se construye en capas. La capa inferior es una lista enlazada ordenada ordinaria . Cada capa superior actúa como un "carril rápido" para las listas siguientes, donde un elemento de una capa aparece en una capa con una probabilidad fija (dos valores comúnmente utilizados para son o ). En promedio, cada elemento aparece en listas y el elemento más alto (normalmente un elemento principal especial al principio de la lista de omisión) aparece en todas las listas. La lista de omisión contiene (es decir, base logarítmica de ) listas.
La búsqueda de un elemento objetivo comienza en el elemento principal de la lista superior y continúa horizontalmente hasta que el elemento actual sea mayor o igual que el objetivo. Si el elemento actual es igual al objetivo, se ha encontrado. Si el elemento actual es mayor que el objetivo, o la búsqueda llega al final de la lista vinculada, el procedimiento se repite después de regresar al elemento anterior y descender verticalmente a la siguiente lista inferior. El número esperado de pasos en cada lista vinculada es como máximo , lo que se puede ver rastreando la ruta de búsqueda hacia atrás desde el objetivo hasta llegar a un elemento que aparece en la siguiente lista superior o llegar al comienzo de la lista actual. Por tanto, el coste total esperado de una búsqueda es cuál es , cuando es una constante. Al elegir diferentes valores de , es posible intercambiar los costos de búsqueda con los costos de almacenamiento.
Los elementos utilizados para una lista de omisión pueden contener más de un puntero ya que pueden participar en más de una lista.
Las inserciones y eliminaciones se implementan de manera muy similar a las operaciones de lista vinculada correspondientes, excepto que los elementos "altos" deben insertarse o eliminarse de más de una lista vinculada.
Las operaciones, que nos obligan a visitar cada nodo en orden ascendente (como imprimir la lista completa), brindan la oportunidad de realizar una desrandomización detrás de escena de la estructura de niveles de la lista de omisión de una manera óptima, trayendo la omisión lista para buscar el tiempo. (Elija que el nivel del i-ésimo nodo finito sea 1 más el número de veces que es posible dividir i entre 2 repetidamente antes de que se vuelva impar. Además, i=0 para el encabezado infinito negativo, ya que existe el caso especial habitual de elegir el nivel más alto posible para nodos infinitos negativos y/o positivos). Sin embargo, esto también permite que alguien sepa dónde están todos los nodos superiores al nivel 1 y los elimine.
Alternativamente, la estructura de niveles podría hacerse casi aleatoria de la siguiente manera:
hacer que todos los nodos sean nivel 1j ← 1mientras que el número de nodos en el nivel j > 1 lo hace para cada i-ésimo nodo en el nivel j si i es impar y no es el último nodo en el nivel j elige aleatoriamente si promocionarlo al nivel j+1 de lo contrario, si i es par y el nodo i-1 no fue promovido promoverlo al nivel j+1 terminar si se repite j ← j + 1repetir
Al igual que la versión desaleatorizada, la cuasi-aleatorización solo se realiza cuando hay alguna otra razón para ejecutar una operación (que visita todos los nodos).
La ventaja de esta cuasi aleatoriedad es que no revela tanta información relacionada con la estructura de niveles a un usuario adversario como el usuario no aleatorizado. Esto es deseable porque un usuario adversario que es capaz de saber qué nodos no están en el nivel más bajo puede pesimizar el rendimiento simplemente eliminando nodos de nivel superior. (Bethea y Reiter, sin embargo, argumentan que, no obstante, un adversario puede utilizar métodos probabilísticos y de sincronización para forzar la degradación del rendimiento. [4] ) Aún se garantiza que el rendimiento de la búsqueda será logarítmico.
Sería tentador hacer la siguiente "optimización": En la parte que dice "Siguiente, para cada i ésimo...", olvídate de lanzar una moneda al aire para cada par par-impar. Simplemente lanza una moneda una vez para decidir si promocionas solo las pares o solo las impares. En lugar de lanzamientos de monedas, solo habría ellos. Desafortunadamente, esto le da al usuario adversario una probabilidad de 50/50 de acertar al adivinar que todos los nodos pares (entre los de nivel 1 o superior) son superiores al nivel uno. Esto a pesar de la propiedad de que existe una probabilidad muy baja de adivinar que un nodo particular está en el nivel N para algún número entero N.
Una lista de omisión no proporciona las mismas garantías absolutas de rendimiento en el peor de los casos que las estructuras de datos de árbol balanceadas más tradicionales , porque siempre es posible (aunque con una probabilidad muy baja [5] ) que los lanzamientos de monedas utilizados para construir la lista de omisión produzcan una estructura mal equilibrada. Sin embargo, funcionan bien en la práctica y se ha argumentado que el esquema de equilibrio aleatorio es más fácil de implementar que los esquemas de equilibrio deterministas utilizados en los árboles de búsqueda binarios equilibrados. Las listas de omisión también son útiles en computación paralela , donde las inserciones se pueden realizar en diferentes partes de la lista de omisión en paralelo sin ningún reequilibrio global de la estructura de datos. Este paralelismo puede ser especialmente ventajoso para el descubrimiento de recursos en una red inalámbrica ad-hoc porque una lista de omisión aleatoria puede hacerse robusta ante la pérdida de un solo nodo. [6]
Como se describió anteriormente, una lista de omisión es capaz de insertar y eliminar rápidamente valores de una secuencia ordenada, pero sólo tiene búsquedas lentas de valores en una posición determinada de la secuencia (es decir, devuelve el valor número 500); sin embargo, con una pequeña modificación, la velocidad de las búsquedas indexadas de acceso aleatorio se puede mejorar a .
Para cada enlace, almacene también el ancho del enlace. El ancho se define como el número de enlaces de la capa inferior que atraviesa cada uno de los enlaces de "carril rápido" de la capa superior.
Por ejemplo, aquí están los anchos de los enlaces en el ejemplo en la parte superior de la página:
1 10 o---> o-------------------------------------------- -------------> o Nivel superior 1 3 2 5 o---> o---------------> o---------> o---------------- -----------> o Nivel 3 1 2 1 2 3 2 o---> o---------> o---> o---------> o---------------> o ---------> o Nivel 2 1 1 1 1 1 1 1 1 1 1 1 o---> o---> o---> o---> o---> o---> o---> o---> o---> o---> o---> o Nivel inferiorCabeza 1.º 2.º 3.º 4.º 5.º 6.º 7.º 8.º 9.º 10.º NINGUNO Nodo Nodo Nodo Nodo Nodo Nodo Nodo Nodo Nodo Nodo
Observe que el ancho de un vínculo de nivel superior es la suma de los vínculos que lo componen debajo (es decir, el vínculo de ancho 10 abarca los vínculos de ancho 3, 2 y 5 inmediatamente debajo de él). En consecuencia, la suma de todos los anchos es la misma en todos los niveles (10 + 1 = 1 + 3 + 2 + 5 = 1 + 2 + 1 + 2 + 3 + 2).
Para indexar la lista de omisión y encontrar el valor i-ésimo, recorra la lista de omisión mientras cuenta regresivamente los anchos de cada enlace atravesado. Desciende un nivel siempre que el ancho próximo sea demasiado grande.
Por ejemplo, para encontrar el nodo en la quinta posición (Nodo 5), recorra un enlace de ancho 1 en el nivel superior. Ahora se necesitan cuatro pasos más, pero el siguiente ancho en este nivel es diez, lo cual es demasiado grande, así que baje un nivel. Atraviese un eslabón de ancho 3. Dado que otro paso de ancho 2 sería demasiado largo, baje al nivel inferior. Ahora recorra el enlace final de ancho 1 para alcanzar el total objetivo de 5 (1+3+1).
función de búsqueda por índice de posición (i) nodo ← cabeza i ← i + 1 # no cuente la cabeza como un paso para el nivel de arriba a abajo , hágalo mientras i ≥ node.width[nivel] haga # si el siguiente paso no está demasiado lejos i ← i - node.width[level] # restar el ancho actual nodo ← node.next[level] # recorrer hacia adelante en el nivel actual repetir repetir regresar node.value función final
Este método de implementación de indexación se detalla en "Un libro de cocina con lista de omisión" de William Pugh [7].
Las listas de omisión fueron descritas por primera vez en 1989 por William Pugh . [8]
Para citar al autor:
Las listas de omisión son una estructura de datos probabilística que parece probable que sustituya a los árboles equilibrados como método de implementación elegido para muchas aplicaciones. Los algoritmos de lista de omisión tienen los mismos límites de tiempo esperados asintóticos que los árboles equilibrados y son más simples, más rápidos y utilizan menos espacio.
— William Pugh, Mantenimiento concurrente de listas de omisión (1989)
Lista de aplicaciones y marcos que utilizan listas de omisión:
Las listas de omisión también se utilizan en aplicaciones distribuidas (donde los nodos representan computadoras físicas y los punteros representan conexiones de red) y para implementar colas de prioridad concurrentes altamente escalables con menos contención de bloqueo, [17] o incluso sin bloqueo , [18] [19] [ 20] así como diccionarios concurrentes sin bloqueo . [21] También existen varias patentes estadounidenses para el uso de listas de omisión para implementar colas de prioridad (sin bloqueo) y diccionarios concurrentes. [22]
