En informática , una lista de omisión es una estructura de datos probabilística que permite complejidad de búsqueda, así como complejidad de inserción dentro de una secuencia ordenada deelementos. Por lo tanto, puede obtener las mejores características de una matriz ordenada (para buscar) mientras mantiene una estructura similar a una lista enlazada que permite la inserción, lo que no es posible en una matriz. La búsqueda rápida es posible al mantener una jerarquía vinculada de subsecuencias, con cada subsecuencia sucesiva omitiendo menos elementos que la anterior (vea la imagen a continuación a la derecha). La búsqueda comienza en la subsecuencia más dispersa hasta que se han encontrado 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 estamos buscando en la secuencia completa. Los elementos que se saltan pueden elegirse probabilísticamente[2] o determinista, [3] siendo el primero más común.
Lista de omisión | |||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Tipo | Lista | ||||||||||||||||||||
Inventado | 1989 | ||||||||||||||||||||
Inventado por | W. Pugh | ||||||||||||||||||||
Complejidad del tiempo en notación O grande | |||||||||||||||||||||
|
Descripción
Una lista de omisión se crea 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 la capa aparece en la capa con alguna probabilidad fija (dos valores de uso común para están o ). En promedio, cada elemento aparece enlistas y el elemento más alto (generalmente un elemento principal especial al principio de la lista de omisión) 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 es 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 volver al elemento anterior y descender verticalmente a la siguiente lista inferior. El número esperado de pasos en cada lista enlazada es como máximo, 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 principio de la lista actual. Por lo tanto, el costo total esperado de una búsqueda es cual es , Cuándo es una constante. Al elegir diferentes valores de, es posible intercambiar los costos de búsqueda con los costos de almacenamiento.
Detalles de implementacion
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 correspondientes de la lista vinculada, 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 desaleatorización detrás de escena de la estructura de niveles de la lista de omisión de una manera óptima, lo que lleva a la omisión lista para tiempo de búsqueda. (Elija que el nivel del i-ésimo nodo finito sea 1 más el número de veces que podemos dividir i entre 2 repetidamente antes de que se vuelva impar. Además, i = 0 para el encabezado infinito negativo, ya que tenemos el caso especial habitual de elegir el nivel más alto posible para los nodos infinitos negativos y / o positivos). Sin embargo, esto también le permite a alguien saber dónde están todos los nodos superiores al nivel 1 y eliminarlos.
Alternativamente, podríamos hacer que la estructura de niveles sea cuasialeatoria de la siguiente manera:
hacer que todos los nodos sean de 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 sí lo hace si i es impar y no es el último nodo en el nivel j elige al azar si quieres promoverlo al nivel j + 1 de lo contrario, si i es par y no se promovió el nodo i-1 promoverlo al nivel j + 1 terminar si se repite j ← j + 1repetir
Al igual que la versión desaleatorizada, la cuasialeatoria solo se realiza cuando hay alguna otra razón para ejecutar un operación (que visita cada nodo).
La ventaja de este cuasialeatorio es que no revela tanta información relacionada con la estructura de niveles a un usuario adversario como el desaleatorizado. Esto es deseable porque un usuario adversario que puede decir qué nodos no están en el nivel más bajo puede pesimizar el rendimiento simplemente eliminando los nodos de nivel superior. (Bethea y Reiter, sin embargo, sostienen que, no obstante, un adversario puede utilizar métodos probabilísticos y de sincronización para forzar la degradación del rendimiento. [4] ) El rendimiento de la búsqueda todavía está garantizado para ser logarítmico.
Sería tentador hacer la siguiente "optimización": En la parte que dice: "A continuación, para cada i l ...", se olvide de hacer un cara o cruz para cada par de par-impar. Simplemente lanza una moneda una vez para decidir si promover solo los pares o solo los impares. En vez de lanzamientos de moneda, solo habría de ellos. Desafortunadamente, esto le da al usuario adversario una probabilidad de 50/50 de estar en lo correcto al adivinar que todos los nodos pares (entre los del nivel 1 o superior) son más altos que el nivel uno. Esto es a pesar de la propiedad de que hay una muy baja probabilidad de adivinar que un nodo en particular está en el nivel N para algún entero N .
Una lista de omisión no proporciona las mismas garantías de rendimiento en el peor de los casos absolutos que las estructuras de datos de árbol equilibrado más tradicionales , porque siempre es posible (aunque con muy baja probabilidad [5] ) que las monedas utilizadas 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 árboles de búsqueda binarios equilibrados. Las listas de omisión también son útiles en la computación en paralelo , 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. Tal 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 resistente a la pérdida de cualquier nodo. [6]
Lista de omisión indexable
Como se describió anteriormente, una lista de omisión es capaz de inserción y eliminación de valores de una secuencia ordenada, pero solo tiene búsquedas de valores en una posición determinada en la secuencia (es decir, devuelve el valor 500); sin embargo, con una pequeña modificación, la velocidad de las búsquedas indexadas de acceso aleatorio se puede mejorar para.
Para cada enlace, también almacene 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 del "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 1o 2o 3o 4o 5o 6o 7o 8o 9o 10o NIL Nodo Nodo Nodo Nodo Nodo Nodo Nodo Nodo Nodo
Observe que el ancho de un enlace de nivel superior es la suma de los enlaces componentes debajo de él (es decir, el enlace de ancho 10 abarca los enlaces de los anchos 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 i-ésimo valor, recorra la lista de omisión mientras cuenta los anchos de cada enlace atravesado. Baje un nivel siempre que el ancho próximo sea demasiado grande.
Por ejemplo, para encontrar el nodo en la quinta posición (Nodo 5), atraviese 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, que 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, desplácese hasta el nivel inferior. Ahora atraviesa el enlace final de ancho 1 para alcanzar el total acumulado objetivo de 5 (1 + 3 + 1).
función lookupByPositionIndex (i) nodo ← cabeza i ← i + 1 # no cuente la cabeza como un paso para el nivel de arriba a abajo do mientras i ≥ node.width [level] do # si el siguiente paso no está demasiado lejos i ← i - node.width [level] # restar el nodo de ancho actual ← nodo.siguiente [nivel] # recorrer hacia adelante en el nivel actual repetir repetir retorno nodo.valor función final
Este método de implementación de la indexación se detalla en "Un libro de recetas de lista de omisión" de William Pugh [7].
Historia
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 suplante a los árboles equilibrados como método de implementación de elección para muchas aplicaciones. Los algoritmos de lista de omisión tienen los mismos límites de tiempo esperados asintóticos que los árboles balanceados y son más simples, más rápidos y usan menos espacio.
- William Pugh, Mantenimiento concurrente de listas de omisión (1989)
Usos
Lista de aplicaciones y marcos que usan listas de omisión:
- Apache Portable Runtime implementa listas de omisión. [9]
- MemSQL utiliza listas de omisión sin bloqueo como su estructura de indexación principal para su tecnología de base de datos.
- El servidor Cyrus IMAP ofrece una implementación de base de datos backend "lista de omisión" [10]
- Lucene utiliza listas de omisión para buscar listas de publicación codificadas en delta en tiempo logarítmico. [ cita requerida ]
- La clase de plantilla del diccionario de clave / valor "QMap" (hasta Qt 4) de Qt se implementa con listas de omisión. [11]
- Redis , un almacén de clave / valor persistente de código abierto ANSI-C para sistemas Posix, utiliza listas de omisión en su implementación de conjuntos ordenados. [12]
- "nessDB", un motor de almacenamiento de base de datos integrado de valor clave muy rápido (que utiliza árboles de combinación estructurada de registros (LSM)), utiliza listas de omisión para su tabla de memoria. [13]
- "skipdb" es una implementación de código abierto de una base de datos clave / valor ordenada ACID, implementada con una lista de omisión en lugar de un árbol b. [14]
- ConcurrentSkipListSet y ConcurrentSkipListMap en la API de Java 1.6. [15] Utilizado por Apache HBase .
- Las tablas de velocidad son un almacén de datos de clave-valor rápido para Tcl que usa skiplists para índices y memoria compartida sin bloqueo.
- "leveldb" es una biblioteca de almacenamiento de clave-valor rápida escrita en Google que proporciona una asignación ordenada de claves de cadena a valores de cadena [16]
- El programador MuQSS [17] de Con Kolivas para el kernel de Linux utiliza listas de omisión
- SkiMap utiliza listas de omisión como estructura de datos base para construir una cuadrícula dispersa 3D más compleja para sistemas de mapeo de robots. [18]
- "IOWOW" es una biblioteca de almacenamiento de clave / valor C11 persistente que utiliza listas de omisión como estructura de datos principal. [19]
Las listas de omisión se utilizan para cálculos estadísticos eficientes de las medianas corrientes (también conocidas como medianas móviles). [20]
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, [21] o incluso sin bloqueo , [22] [23] [ 24] , así como diccionarios simultáneos sin bloqueo . [25] También hay varias patentes de EE. UU. Para el uso de listas de omisión para implementar colas de prioridad (sin bloqueo) y diccionarios simultáneos. [26]
Ver también
- Filtro de floración
- Saltar gráfico
Referencias
- ↑ a b Papadakis, Thomas (1993). Listas de omisión y análisis probabilístico de algoritmos (PDF) (Ph.D.). Universidad de Waterloo.
- ^ Pugh, W. (1990). "Listas de omisión: una alternativa probabilística a los árboles equilibrados" (PDF) . Comunicaciones de la ACM . 33 (6): 668–676. doi : 10.1145 / 78973.78977 .
- ^ Munro, J. Ian ; Papadakis, Thomas; Sedgewick, Robert (1992). "Listas de salto deterministas" (PDF) . Actas del tercer simposio anual ACM-SIAM sobre algoritmos discretos (SODA '92) . Orlando, Florida, EE. UU .: Sociedad de Matemáticas Industriales y Aplicadas, Filadelfia, PA, EE. UU. págs. 367–375. doi : 10.1145 / 139404.139478 .
- ^ Bethea, Darrell; Reiter, Michael K. (21 al 23 de septiembre de 2009). Estructuras de datos con tiempos impredecibles (PDF) . ESORICS 2009, XIV Simposio Europeo de Investigación en Seguridad Informática. Saint-Malo, Francia. págs. 456–471, §4 "Listas de omisión". doi : 10.1007 / 978-3-642-04444-1_28 . ISBN 978-3-642-04443-4.
- ^ Sen, Sandeep (1991). "Algunas observaciones sobre listas de omisión". Cartas de procesamiento de información . 39 (4): 173-176. doi : 10.1016 / 0020-0190 (91) 90175-H .
- ^ Shah, Gauri (2003). Estructuras de datos distribuidos para sistemas peer-to-peer (PDF) (tesis doctoral). Universidad de Yale.
- ^ William Pugh. "Un libro de cocina de lista de omisión" . 1990. Sección 3.4 Operaciones de lista lineal .
- ^ Pugh, William (abril de 1989). Mantenimiento concurrente de listas de omisión (PS, PDF) (informe técnico). Departamento de Ciencias de la Computación, U. Maryland. CS-TR-2222.
- ^ Documentación de Apache Portable Runtime APR 1.6
- ^ Servidor IMAP Cyrus. archivo de origen de lista de omisión
- ^ QMap
- ^ "Implementación del conjunto ordenado de Redis" .
- ^ nessDB
- ^ skipdb
- ^ ConcurrentSkipListSet y ConcurrentSkipListMap
- ^ leveldb
- ^ "LKML: Con Kolivas: [ANUNCIO] Programador de lista de exclusión de múltiples colas versión 0.120" . lkml.org . Consultado el 11 de mayo de 2017 .
- ^ Gregorio, Daniele De; Stefano, Luigi Di (2017). "SkiMap: un marco de mapeo eficiente para la navegación de robots". arXiv : 1704.05832 [ cs.CV ].
- ^ IOWOW
- ^ Raymond Hettinger. "Mediana de ejecución eficiente usando una lista de omisión indexable (Python)" . 2009.
- ^ Shavit, N .; Lotan, I. (2000). "Colas de prioridad simultáneas basadas en listas de omisión" (PDF) . Actas XIV Simposio internacional de procesamiento paralelo y distribuido. IPDPS 2000 . pag. 263. CiteSeerX 10.1.1.116.3489 . doi : 10.1109 / IPDPS.2000.845994 . ISBN 978-0-7695-0574-9.
- ^ Sundell, H .; Tsigas, P. (2003). "Colas de prioridad simultáneas rápidas y sin bloqueos para sistemas multiproceso". Proceedings International Parallel and Distributed Processing Symposium . pag. 11. CiteSeerX 10.1.1.113.4552 . doi : 10.1109 / IPDPS.2003.1213189 . ISBN 978-0-7695-1926-5.
- ^ Fomitchev, Mikhail; Ruppert, Eric (2004). Listas enlazadas sin bloqueo y listas de omisión (PDF) . Proc. Anual ACM Symp. sobre Principios de Computación Distribuida (PODC). págs. 50–59. doi : 10.1145 / 1011767.1011776 . ISBN 1581138024.
- ^ Bajpai, R .; Dhara, KK; Krishnaswamy, V. (2008). "QPID: una cola de prioridad distribuida con la localidad del artículo". Simposio internacional de IEEE 2008 sobre procesamiento paralelo y distribuido con aplicaciones . pag. 215. doi : 10.1109 / ISPA.2008.90 . ISBN 978-0-7695-3471-8.
- ^ Sundell, HK; Tsigas, P. (2004). "Diccionarios concurrentes escalables y sin bloqueo" (PDF) . Actas del simposio 2004 ACM sobre informática aplicada - SAC '04 . pag. 1438. doi : 10.1145 / 967900.968188 . ISBN 978-1581138122.
- ^ Patente de EE. UU. 7937378
enlaces externos
- Entrada "Lista de omisión" en el Diccionario de algoritmos y estructuras de datos
- Listas de omisión: una lista vinculada con propiedades similares a BST de equilibrio automático en MSDN en C # 2.0
- ¿Por qué omitir listas?
- Conferencia sobre listas de omisiones (MIT OpenCourseWare: Introducción a los algoritmos)
- Estructuras de datos abiertos - Capítulo 4 - Skiplists , Pat Morin
- Omitir árboles, una estructura de datos alternativa para omitir listas en un enfoque concurrente
- Gráficos de árbol de omisión, una versión distribuida de árboles de omisión
- Más sobre gráficos de árboles de salto, una versión distribuida de árboles de salto