Hispanopedia Wiki
Articulo de referencia

Lista de saltos

\\mathcal O(n) "},"space_worst":{"wt":" \\mathcal O(n\\log n) {{cite thesis |title=Skip Lists and Probabilistic Analysis of Algorithms |first=Thomas |last=Papadakis |type=Ph.D. ...

Hispanopedia WikiContenido en espanolLectura gratuita

En informática , una lista de saltos (o skiplist ) es una estructura de datos probabilística que permiteO(registro⁡norte){\displaystyle {\mathcal {O}}(\log n)}complejidad promedio para la búsqueda así comoO(registro⁡norte){\displaystyle {\mathcal {O}}(\log n)}complejidad promedio para la inserción dentro de una secuencia ordenada denorte{\displaystyle n}elementos. De esta forma, puede obtener las mejores características de un arreglo ordenado (para búsquedas) manteniendo una estructura similar a una lista enlazada que permite la inserción, lo cual no es posible con un arreglo estático. La búsqueda rápida es posible gracias al mantenimiento de una jerarquía enlazada de subsecuencias, donde cada subsecuencia sucesiva omite menos elementos que la anterior (ver la imagen a continuación) . La búsqueda comienza en la subsecuencia más dispersa hasta que se encuentran dos elementos consecutivos, uno menor y otro mayor o igual que el elemento buscado. A través de la jerarquía enlazada, estos dos elementos se enlazan con 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 la primera más común.

Descripción

Representación esquemática de la estructura de datos de la lista de saltos. Cada recuadro con una flecha representa un puntero y cada fila es una lista enlazada que proporciona una subsecuencia dispersa; los recuadros numerados (en amarillo) en la parte inferior representan la secuencia de datos ordenada. La búsqueda se realiza hacia abajo, desde la subsecuencia más dispersa en la parte superior, hasta encontrar elementos consecutivos que enmarquen el elemento buscado.

Una lista de saltos se construye en capas. La capa inferior1{\displaystyle 1}es una lista enlazada ordenada ordinaria . Cada capa superior actúa como un "carril exprés" para las listas inferiores, donde un elemento en la capai{\displaystyle i}aparece en la capai+1{\displaystyle i+1}con alguna probabilidad fijapag{\displaystyle p}(dos valores comúnmente utilizados parapag{\displaystyle p}son1/2{\displaystyle 1/2}o1/4{\displaystyle 1/4}). En promedio, cada elemento aparece en1/(1−pag){\displaystyle 1/(1-p)}listas, y el elemento más alto (normalmente un elemento de cabeza especial al principio de la lista de saltos) aparece en todas las listas. La lista de saltos contieneregistro1/pag⁡norte{\displaystyle \log _{1/p}n\,}(es decir, base logarítmica)1/pag{\displaystyle 1/p}denorte{\displaystyle n}) listas.

La búsqueda de un elemento objetivo comienza en el primer elemento de la lista superior y avanza 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 enlazada, 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áximo1/pag{\displaystyle 1/p}, lo cual se puede observar al rastrear 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 es1pagregistro1/pag⁡norte{\displaystyle {\tfrac {1}{p}}\log _{1/p}n}que esO(registro⁡norte){\displaystyle {\mathcal {O}}(\log n)\,}, cuandopag{\displaystyle p}es una constante. Al elegir diferentes valores depag{\displaystyle p}, es posible intercambiar los costos de búsqueda por los costos de almacenamiento. Por ejemplo, el valorpag=1/mi{\displaystyle p=1/e}minimiza el tiempo promedio de búsqueda de las listas de salto, mientras que el valorpag=1/2{\displaystyle p=1/2}simplifica su implementación.

Detalles de implementación

Insertar elementos en una lista de saltos

Los elementos utilizados para una lista de salto pueden contener más de un puntero, ya que pueden participar en más de una lista.

Las inserciones y eliminaciones se implementan de forma muy similar a las operaciones correspondientes en listas enlazadas, con la excepción de que los elementos "altos" deben insertarse o eliminarse de más de una lista enlazada.

O(norte){\displaystyle {\mathcal {O}}(n)}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 entre bastidores de la estructura de niveles de la lista de saltos de manera óptima, llevando la lista de saltos aO(registro⁡norte){\displaystyle {\mathcal {O}}(\log n)}Tiempo de búsqueda. (Elija el nivel del i-ésimo nodo finito como 1 más el número de veces que es posible dividir i repetidamente entre 2 antes de que se vuelva impar. Además, i=0 para el encabezado de 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 de nivel superior a 1 y los elimine.

Alternativamente, la estructura de niveles podría hacerse cuasialeatoria de la siguiente manera:

establecer todos los nodos en nivel 1 j ← 1 mientras el número de nodos en el nivel j > 1 hacer para cada i-ésimo nodo en el nivel j hacer si i es impar y i no es el último nodo en el nivel j elegir aleatoriamente si ascenderlo al nivel j+1 de lo contrario, si i es par y el nodo i-1 no fue promovido ascenderlo al nivel j+1 fin si se repite j ← j + 1 repetir

Al igual que la versión desaleatorizada, la cuasialeatorización solo se realiza cuando hay alguna otra razón para ejecutar unaO(norte){\displaystyle {\mathcal {O}}(n)}operación (que visita cada nodo).

La ventaja de esta cuasi-aleatoriedad es que no revela tanta información relacionada con la estructura de niveles a un usuario adversario como la que no está aleatorizada. Esto es deseable porque un usuario adversario que pueda identificar qué nodos no están en el nivel más bajo puede reducir el rendimiento simplemente eliminando nodos de nivel superior. (Bethea y Reiter, sin embargo, argumentan que un adversario puede utilizar métodos probabilísticos y de temporización para forzar la degradación del rendimiento. [ 4 ] ) El rendimiento de la búsqueda sigue garantizado que será logarítmico.

Sería tentador hacer la siguiente "optimización": En la parte que dice "A continuación, para cada i- ésimo...", olvídese de lanzar una moneda para cada par par-impar. Simplemente lance una moneda una vez para decidir si promover solo los pares o solo los impares. En lugar deO(norteregistro⁡norte){\displaystyle {\mathcal {O}}(n\log n)}lanzamientos de moneda, solo habríaO(registro⁡norte){\displaystyle {\mathcal {O}}(\log n)}Desafortunadamente, esto le da al usuario adversario una probabilidad del 50/50 de acertar al adivinar que todos los nodos pares (entre los que están en el nivel 1 o superior) están por encima del nivel uno. Esto a pesar de la propiedad de que hay una probabilidad muy baja de adivinar que un nodo en particular está en el nivel N para algún entero N.

Una lista de saltos no proporciona las mismas garantías de rendimiento en el peor de los casos que las estructuras de datos de árboles balanceados más tradicionales, ya que siempre es posible (aunque con muy baja probabilidad [ 5 ] ) que los lanzamientos de moneda utilizados para construir la lista de saltos produzcan una estructura mal balanceada. Sin embargo, funcionan bien en la práctica, y se ha argumentado que el esquema de balanceo aleatorio es más fácil de implementar que los esquemas de balanceo deterministas utilizados en los árboles de búsqueda binaria balanceados. Las listas de saltos también son útiles en la computación paralela , donde las inserciones se pueden realizar en diferentes partes de la lista de saltos en paralelo sin ningún rebalanceo 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 saltos aleatoria puede hacerse robusta ante la pérdida de cualquier nodo individual. [ 6 ]

Lista de saltos indexable

Como se describió anteriormente, una lista de saltos es capaz de...O(registro⁡norte){\displaystyle {\mathcal {O}}(\log n)}inserción y eliminación de valores de una secuencia ordenada, pero solo tiene una lentaO(norte){\displaystyle {\mathcal {O}}(n)}búsquedas de valores en una posición determinada en la secuencia (es decir, devolver 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 O(registro⁡norte){\displaystyle {\mathcal {O}}(\log n)}.

Para cada enlace, almacene también su ancho. El ancho se define como el número de enlaces de la capa inferior que atraviesa cada uno de los enlaces de la capa superior que funcionan como "carril exprés".

Por ejemplo, aquí están los anchos de los enlaces en el ejemplo que aparece 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 inferior Cabeza 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 enlace de nivel superior es la suma de los anchos de los enlaces que se encuentran debajo (es decir, el enlace de ancho 10 abarca los enlaces de anchos 3, 2 y 5 que están inmediatamente debajo). Por consiguiente, la suma de todos los anchos es la misma en cada nivel (10 + 1 = 1 + 3 + 2 + 5 = 1 + 2 + 1 + 2 + 3 + 2).

Para indexar la lista de saltos y encontrar el i-ésimo valor, recorra la lista de saltos mientras cuenta hacia atrás el ancho de cada enlace recorrido. Descienda un nivel cuando el siguiente ancho 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, que es demasiado grande, así que baje un nivel. Recorra un enlace de ancho 3. Como otro paso de ancho 2 sería demasiado lejos, baje al nivel inferior. Ahora recorra el último enlace de ancho 1 para alcanzar el total acumulado objetivo de 5 (1+3+1).

función lookupByPositionIndex(i) nodo ← cabeza i ← i + 1 # no contar la cabeza como un paso para nivel de arriba a abajo hacer mientras i ≥ nodo.ancho[nivel] hacer # si el siguiente paso no está demasiado lejos i ← i - nodo.ancho[nivel] # restar el ancho actual nodo ← nodo.siguiente[nivel] # avanzar en el nivel actual repetir repetir devolver nodo.valor fin de la función

Este método de implementación de la indexación se detalla en "A skip list cookbook" de William Pugh [ 7 ].

Historia

Las listas de salto fueron descritas por primera vez en 1989 por William Pugh . [ 8 ]

Para citar al autor:

Las listas de salto son una estructura de datos probabilística que probablemente reemplazará a los árboles equilibrados como método de implementación preferido para muchas aplicaciones. Los algoritmos de listas de salto tienen los mismos límites de tiempo esperados asintóticos que los árboles equilibrados y son más simples, rápidos y consumen menos espacio.

— William Pugh, Mantenimiento concurrente de listas de salto (1989)

Usos

Lista de aplicaciones y frameworks que utilizan listas de salto:

  • Apache Portable Runtime implementa listas de salto. [ 9 ]
  • MemSQL utiliza listas de salto sin bloqueo como su principal estructura de indexación para su tecnología de base de datos.
  • MuQSS , para el kernel de Linux , es un planificador de CPU basado en listas de salto. [ 10 ] [ 11 ]
  • El servidor Cyrus IMAP ofrece una implementación de base de datos backend de "lista de saltos" [ 12 ].
  • IBM DOORS ofrece listas de salto como un tipo de dato en su lenguaje de scripting DOORS/DXL (DOORS eXtension Language).
  • Lucene utiliza listas de salto para buscar en listas de publicaciones codificadas con delta en tiempo logarítmico.
  • La clase plantilla de diccionario clave/valor "QMap" (hasta Qt 4) de Qt se implementa con listas de salto. [ 13 ]
  • Redis , un almacén persistente de clave/valor de código abierto ANSI-C para sistemas Posix, utiliza listas de salto en su implementación de conjuntos ordenados. [ 14 ]
  • Discord utiliza listas de salto para gestionar el almacenamiento y la actualización de la lista de miembros en un servidor . [ 15 ]
  • RocksDB utiliza listas de salto para su implementación predeterminada de Memtable. [ 16 ]
  • Java utiliza listas de salto para sus funciones ConcurrentSkipListSet y ConcurrentSkipListMap .

Las listas de salto 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 menor 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 salto para implementar colas de prioridad (sin bloqueo) y diccionarios concurrentes. [ 22 ]

Véase también

Referencias

  1. 1 2 Papadakis, Thomas (1993). Listas de salto y análisis probabilístico de algoritmos (PDF) (Ph.D.). Universidad de Waterloo.
  2. ↑ Pugh, W. (1990). "Listas de salto: una alternativa probabilística a los árboles equilibrados" (PDF) . Communications of the ACM . 33 (6): 668– 676. doi : 10.1145/78973.78977 . S2CID 207691558 . 
  3. ↑ 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.: Society for Industrial and Applied Mathematics, Filadelfia, PA, EE. UU. pp. 367–375 . S2CID 7477119 .  
  4. ↑ Bethea, Darrell; Reiter, Michael K. (21-23 de septiembre de 2009). Estructuras de datos con sincronización impredecible (PDF) . ESORICS 2009, 14.º Simposio Europeo sobre Investigación en Seguridad Informática. Saint-Malo, Francia. págs. 456-471, §4 «Listas de salto». doi : 10.1007/978-3-642-04444-1_28 . ISBN 978-3-642-04443-4.
  5. ↑ Sen, Sandeep (1991). "Algunas observaciones sobre las listas de salto". Information Processing Letters . 39 (4): 173– 176. doi : 10.1016/0020-0190(91)90175-H .
  6. ↑ Shah, Gauri (2003). Estructuras de datos distribuidas para sistemas peer-to-peer (PDF) (tesis doctoral). Universidad de Yale.
  7. ↑ William Pugh. "Un libro de cocina de listas de salto" . 1990. Sección 3.4 Operaciones con listas lineales .
  8. ↑ Pugh, William (abril de 1989). Mantenimiento concurrente de listas de salto (PS, PDF) (Informe técnico). Departamento de Ciencias de la Computación, Universidad de Maryland. CS-TR-2222.
  9. ↑ Documentación de Apache Portable Runtime APR 1.6
  10. ↑ Artículo de LWN
  11. ↑ "LKML: Con Kolivas: [ ANUNCIO ] Programador de lista de salto de múltiples colas versión 0.120" . lkml.org . Consultado el 11 de mayo de 2017 .
  12. ↑ Servidor IMAP Cyrus. Archivo fuente skiplist
  13. ↑ Mapa Q
  14. ↑ "Implementación de conjuntos ordenados de Redis" . GitHub .
  15. ↑ Nowack, Matt. "Usando Rust para escalar Elixir para 11 millones de usuarios concurrentes" . Blog de Discord . Consultado el 23 de julio de 2023 .
  16. ↑ "MemTable" . GitHub . Consultado el 12 de diciembre de 2023 .
  17. ↑ Shavit, N.; Lotan, I. (2000). "Colas de prioridad concurrentes basadas en listas de salto" (PDF) . Actas del 14.º Simposio Internacional de Procesamiento Paralelo y Distribuido. IPDPS 2000. pág. 263. CiteSeerX 10.1.1.116.3489 . doi : 10.1109/IPDPS.2000.845994 . ISBN   978-0-7695-0574-9. S2CID 8664407 . 
  18. ↑ Sundell, H.; Tsigas, P. (2003). "Colas de prioridad concurrentes rápidas y sin bloqueo para sistemas multihilo". Actas del Simposio Internacional de Procesamiento Paralelo y Distribuido . pág. 11. CiteSeerX 10.1.1.113.4552 . doi : 10.1109/IPDPS.2003.1213189 . ISBN   978-0-7695-1926-5. S2CID 20995116 . 
  19. ↑ Fomitchev, Mikhail; Ruppert, Eric (2004). Listas enlazadas sin bloqueo y listas de salto (PDF) . Actas del Simposio Anual de la ACM sobre Principios de Computación Distribuida (PODC). págs. 50–59 . doi : 10.1145/1011767.1011776 . ISBN  1581138024.
  20. ↑ Bajpai, R.; Dhara, KK; Krishnaswamy, V. (2008). "QPID: Una cola de prioridad distribuida con localidad de elementos". Simposio Internacional IEEE de 2008 sobre Procesamiento Paralelo y Distribuido con Aplicaciones . pág. 215. doi : 10.1109/ISPA.2008.90 . ISBN  978-0-7695-3471-8. S2CID 15677922 . 
  21. ↑ Sundell, HK; Tsigas, P. (2004). «Diccionarios concurrentes escalables y sin bloqueo» (PDF) . Actas del simposio ACM de 2004 sobre computación aplicada - SAC '04 . pág. 1438. doi : 10.1145/967900.968188 . ISBN  978-1581138122. S2CID 10393486 . 
  22. ↑ Patente estadounidense 7937378 
  • Entrada "Lista de saltos" en el Diccionario de algoritmos y estructuras de datos.
  • Clase sobre listas de salto (MIT OpenCourseWare: Introducción a los algoritmos)
  • Estructuras de datos abiertas - Capítulo 4 - Listas de salto , Pat Morin
  • Grafos de árbol de salto, una versión distribuida de árboles de salto
  • Más información sobre los grafos de árbol de salto, una versión distribuida de los árboles de salto.