Lista de pases

Una  lista de salto es una estructura de datos probabilística basada en varias listas enlazadas ordenadas en paralelo con una eficiencia comparable a un árbol binario (del orden de O (log n) tiempo promedio para la mayoría de las operaciones).

Una lista de omisión se basa en extender una lista enlazada ordenada con enlaces adicionales agregados en rutas aleatorias con una distribución binomial geométrica /negativa [1] para que una búsqueda de lista pueda omitir rápidamente partes de la lista. La inserción, búsqueda y eliminación se realizan en tiempo aleatorio logarítmico.

Descripción

Una lista de saltos consta de varias capas. La capa inferior es una lista enlazada ordenada normal . Cada capa superior representa un "carril dedicado" para las listas siguientes, donde el elemento de la i-ésima capa aparece en la i+1-ésima capa con alguna probabilidad p fija (los dos valores más utilizados para p  son 1 /2 y 1/ cuatro). En promedio, cada elemento aparece en las listas 1/(1- p ), y el elemento superior (generalmente el elemento principal especial al comienzo de la lista con espacios en blanco) en las listas.

La búsqueda del elemento deseado comienza con el elemento de cabeza de la lista superior y se realiza horizontalmente hasta que el elemento actual es mayor o igual que el objetivo. Si el elemento actual es igual al objetivo, se encuentra. Si el elemento actual es mayor que el objetivo, el procedimiento se repite después de volver al elemento anterior y descender verticalmente hasta la siguiente lista inferior. El número esperado de pasos en cada lista enlazada es 1/ p , que se puede ver mirando hacia atrás desde el elemento de destino hasta que se alcanza el elemento que aparece en la siguiente lista superior. Por lo tanto, el costo total esperado de búsqueda es igual a en el caso de una constante p . Al elegir diferentes valores de p , es posible elegir el equilibrio necesario entre el costo del tiempo de búsqueda y el costo de almacenamiento de la lista en memoria.

Detalles de implementación

Los elementos utilizados en una lista de omisión pueden contener más de un puntero, por lo que pueden estar en más de una lista.

Las operaciones de eliminación e inserción se implementan de manera muy similar a sus operaciones de lista enlazada, con la excepción de que "alto" debe insertarse o eliminarse de más de una lista enlazada.

Sin embargo, sin la aleatorización, estas operaciones darían como resultado un rendimiento muy bajo, ya que la lista tendría que barajarse por completo cuando se agregara un nuevo elemento para mantener constante el número de omisiones en el nivel superior. William Pugh propuso el siguiente algoritmo para decidir qué tan alto se debe empujar un nuevo elemento. Este algoritmo requiere solo cambios locales en la lista al agregar nuevos elementos y le permite ahorrar la eficiencia de las "líneas rápidas" (l es el valor resultante del nivel en el que desea colocar el elemento):

l = 1 mientras que el valor aleatorio está en el rango [0,1] < p y l < nivel máximo l = l + 1

Como resultado, el elemento se inserta en el nivel l-ésimo y, en consecuencia, en todos los niveles inferiores a l.

Las operaciones Θ(n) que necesitamos para visitar cada nodo en orden ascendente (p. ej., imprimir la lista completa) brindan la oportunidad de desaleatorizar sutilmente la estructura de niveles de la lista con espacios de forma óptima, alcanzando el tiempo de búsqueda de la lista enlazada . (eligiendo el i-ésimo nivel de nodo final 1 más el número de veces que podemos dividir i por 2 hasta que se vuelve impar. También i=0 para un encabezado infinito negativo como tenemos, el caso especial habitual, eligiendo el nivel más alto posible para nodos infinitos negativos y/o positivos). Sin embargo, esto le permite a alguien saber dónde están todos los nodos con un nivel mayor que 1 y luego eliminarlos.

Alternativamente, podemos hacer que la estructura de nivel sea casi aleatoria de la siguiente manera:

crear todos los nodos de nivel 1 j = 1 mientras que el número de nodos en el nivel j > 1 para cada i-ésimo nodo en el nivel j si soy raro si i no es el último nodo en el nivel j elegir al azar si promocionarlo al nivel j+1 de lo contrario no promover condición final de lo contrario, si incluso el nodo i-1 no se promueve avanzar al nivel j+1 condición final final del bucle para j = j + 1 fin de ciclo por ahora

Al igual que la versión desaleatorizada, la cuasialeatoria solo se realiza cuando existe alguna otra razón para realizar operaciones Θ(n) (que visitarán cada nodo).

Ejemplo de implementación

código de clase C++ utilizando std :: intercambio ; plantilla < nombre de tipo KEY_T , nombre de tipo DATA_T > clase SaltarLista { tamaño_t MaxLevel ; doble SaltoDivisor ; par de estructuras { KEY_T clave ; DATOS_T Datos ; Par * Anterior ; Matriz < Par *> Siguiente ; Par ( const KEY_T & InKey , const DATA_T & InData , Par * InPrevious , size_t InLevel ); Par ( size_t InLevel ); ~ par (); Par & operador = ( const Par & InPair ); Par * PreviousOnLevel ( size_t InLevel ); Par * NextOnLevel ( size_t InLevel ); }; Par Inicio ; Par * NewPrevious ( const KEY_T & InKey ); Par * ParPorClave ( const KEY_T & InKey ); tamaño_tNuevoNivel ( ); público : iterador de clase { SaltarLista * ListaActual ; Par * ParActual ; clase amiga SkipList < KEY_T , DATA_T > ; público : Iterador ( const Iterador & InIterador ); Iterador ( SkipList & InSkipList ); operador booleano (); Iterador y operador ++ (); Iterador y operador -- (); Operador iterador ++ ( int ); Operador iterador -- ( int ); Iterador y operador += ( size_t n ); Iterador y operador -= ( tamaño_t n ); Iterador y operador = ( const Iterador e InIterador ); Iterador y operador = ( const KEY_T & InKey ); DATA_T & operador * (); anular Eliminar (); }; SkipList ( size_t InNumberOfLanes = 3 , double InSkipDivisor = 1.0 / 4.0 ); ~ Omitir lista (); Iterador GetBegin (); Iterador GetEnd (); void Add ( const KEY_T & InKey , const DATA_T & InData ); anular Eliminar ( const KEY_T & InKey ); DATA_T & operador []( const KEY_T & InKey ); tamaño_t Cuenta (); vacíoLimpiar ( ); Búsqueda de iterador ( const DATA_T & Unknown ); bool está vacío (); }; plantilla < nombre de tipo KEY_T , nombre de tipo DATA_T > typename SkipList < KEY_T , DATA_T >:: Par * SkipList < KEY_T , DATA_T >:: Par :: PreviousOnLevel ( size_t InLevel ){ si ( ! esto ) devuelve NULL ; Par * Actual = Anterior ; for (; Actual && ! ( Actual -> Siguiente . Cuenta () >= InLevel + 1 ); Actual = Actual -> Anterior ){} volver actual ; } plantilla < nombre de tipo KEY_T , nombre de tipo DATA_T > typename SkipList < KEY_T , DATA_T >:: Par * SkipList < KEY_T , DATA_T >:: Par :: NextOnLevel ( size_t InLevel ){ si ( ! esto ) devuelve NULL ; Par * Actual = Siguiente [ InLevel -1 ]; for (; Actual && ! ( Actual -> Siguiente . Cuenta () >= InLevel + 1 ); Actual = Actual -> Siguiente [ InLevel -1 ]){} volver actual ; } plantilla < nombre de tipo KEY_T , nombre de tipo DATA_T > SkipList < KEY_T , DATA_T >:: Pair :: Pair ( const KEY_T & InKey , const DATA_T & InData , SkipList < KEY_T , DATA_T >:: Pair * InPrevious , size_t InLevel ) : Clave ( InKey ), Datos ( InData ), Anterior ( EnAnterior ){ Par * Actual = Anterior -> Siguiente [ 0 ]; siguiente _ AddLast ( actual ); para ( tamaño_t Contador = 1 ; Contador <= InLevel ; Contador ++ ){ Actual = NextOnLevel ( Contador ); siguiente _ AddLast ( actual ); } actual = anterior ; para ( tamaño_t Contador = 0 ; Contador <= InLevel ; Contador ++ ) if ( Actual = PreviousOnLevel ( Contador )) Actual -> Siguiente [ Contador ] = esto ; } plantilla < nombre de tipo KEY_T , nombre de tipo DATA_T > SkipList < KEY_T , DATA_T >:: Par :: Par ( size_t InLevel ) : Anterior ( NULL ){ para ( tamaño_t Contador = 0 ; Contador <= InLevel ; Contador ++ ) siguiente _ AgregarÚltimo ( NULL ); } plantilla < nombre de tipo KEY_T , nombre de tipo DATA_T > SkipList < KEY_T , DATA_T >:: Par ::~ Par (){ size_t OurLevel = Siguiente . Cuenta () -1 ; Par * Actual = esto ; for ( tamaño_t Contador = 0 ; Contador <= NuestroNivel ; Contador ++ ) if ( Actual = PreviousOnLevel ( Contador )) Actual -> Siguiente [ Contador ] = Siguiente [ Contador ]; } plantilla < nombre de tipo KEY_T , nombre de tipo DATA_T > SkipList < KEY_T , DATA_T >:: SkipList ( size_t InMaxLevel , doble InSkipDivisor ) : MaxLevel ( InMaxLevel ), SkipDivisor ( InSkipDivisor ), Inicio ( MaxLevel ){} plantilla < nombre de tipo KEY_T , nombre de tipo DATA_T > typename SkipList < KEY_T , DATA_T >:: Pair & SkipList < KEY_T , DATA_T >:: Pair :: operator = ( const SkipList < KEY_T , DATA_T >:: Pair & InPair ){ Clave = En Par . clave ; Datos = En Par . datos ; Anterior = En pareja . anterior ; size_t max = Siguiente . contar (); para ( tamaño_t i ; i < max ; ++ i ) siguiente _ AddLast ( Siguiente [ i ]); devolver * esto ; } plantilla < nombre de tipo KEY_T , nombre de tipo DATA_T > SaltarLista < KEY_T , DATA_T >::~ SaltarLista (){ claro (); } plantilla < nombre de tipo KEY_T , nombre de tipo DATA_T > typename SkipList < KEY_T , DATA_T >:: Par * SkipList < KEY_T , DATA_T >:: NewPrevious ( const KEY_T & InKey ){ Par * Anterior =& Inicio ; Par * Actual = Inicio . Siguiente [ MaxLevel ]; para ( tamaño_t Contador = MaxLevel ; Contador >= 0 ; Contador -- ){ while ( Actual && InKey > Actual -> Clave ){ anterior = actual ; Actual = Actual -> Siguiente [ Contador ]; } si ( ! Contador ) romper ; actual = anterior ; }; volver Anterior ; } plantilla < nombre de tipo KEY_T , nombre de tipo DATA_T > size_t SkipList < KEY_T , DATA_T >:: NewLevel (){ tamaño_t Nivel = 0 ; while ( rand () % 1000 < SkipDivisor * 1000 && Nivel <= MaxLevel ) Nivel ++ ; nivel de retorno ; _ } plantilla < nombre de tipo KEY_T , nombre de tipo DATA_T > void SkipList < KEY_T , DATA_T >:: Add ( const KEY_T & InKey , const DATA_T & InData ){ Par * Anterior = NuevoAnterior ( InKey ); Par * Siguiente = Anterior -> Siguiente [ 0 ]; if ( Siguiente && Siguiente -> Clave == InKey ) throw String ( "¡No es una clave única!" ); nuevo par ( InKey , InData , Previous , NewLevel ()); } plantilla < nombre de tipo KEY_T , nombre de tipo DATA_T > typename SkipList < KEY_T , DATA_T >:: Par * SkipList < KEY_T , DATA_T >:: PairByKey ( const KEY_T & InKey ){ Par * Actual = NuevoAnterior ( InKey ); if (( Actual = Actual -> Siguiente [ 0 ]) && Actual -> Clave == InKey ) volver actual ; throw String ( "¡No hay par para esta clave!" ); } plantilla < nombre de tipo KEY_T , nombre de tipo DATA_T > void SkipList < KEY_T , DATA_T >:: Eliminar ( const KEY_T & InKey ){ si ( está vacío ()) throw String ( "¡Hay una lista vacía!" ); eliminar PairByKey ( InKey ); } plantilla < nombre de tipo KEY_T , nombre de tipo DATA_T > DATA_T & SkipList < KEY_T , DATA_T >:: operador []( const KEY_T & InKey ){ si ( está vacío ()) throw String ( "¡La lista está vacía!" ); volver PairByKey ( InKey ) -> Datos ; } plantilla < nombre de tipo KEY_T , nombre de tipo DATA_T > size_t SkipList < KEY_T , DATA_T >:: Count (){ si ( está vacío ()) devolver 0 ; Par * Siguiente = Inicio . Siguiente [ 0 ]; tamaño_tn = 1 ; _ while ( Siguiente = Siguiente -> Siguiente [ 0 ]) n ++ ; devolver n ; } plantilla < nombre de tipo KEY_T , nombre de tipo DATA_T > void SkipList < KEY_T , DATA_T >:: Borrar (){ Par * Actual = Inicio . Siguiente [ 1 ]; Par * Anterior = NULL ; mientras ( actual ){ Actual -> Anterior = NULL ; anterior = actual ; Actual = Actual -> Siguiente [ 0 ]; borrar anterior ; } for ( tamaño_t i = 0 ; i <= Inicio . Siguiente . Cuenta () -1 ; i ++ ) empezar _ Siguiente [ i ] = NULL ; } plantilla < nombre de tipo KEY_T , nombre de tipo DATA_T > SkipList < KEY_T , DATA_T >:: Iterator :: Iterator ( const SkipList < KEY_T , DATA_T >:: Iterator & InIterator ) : CurrentList ( InIterator . CurrentList ), CurrentPair ( InIterator . CurrentPair ){} plantilla < nombre de tipo KEY_T , nombre de tipo DATA_T > SkipList < KEY_T , DATA_T >:: Iterator :: Iterator ( SkipList < KEY_T , DATA_T >& InSkipList ) : CurrentList ( & InSkipList ), CurrentPair ( InSkipList . Start . Next [ 0 ]){} plantilla < nombre de tipo KEY_T , nombre de tipo DATA_T > SkipList < KEY_T , DATA_T >:: Iterator :: operator bool (){ volver ListaActual && ParActual ; } plantilla < nombre de tipo KEY_T , nombre de tipo DATA_T > typename SkipList < KEY_T , DATA_T >:: Iterator & SkipList < KEY_T , DATA_T >:: Iterator :: operator ++ (){ si ( Par actual ) ParActual = ParActual -> Siguiente [ 0 ]; devolver * esto ; } plantilla < nombre de tipo KEY_T , nombre de tipo DATA_T > typename SkipList < KEY_T , DATA_T >:: Iterator & SkipList < KEY_T , DATA_T >:: Iterator :: operator -- (){ if ( CurrentPair && CurrentPair != CurrentList -> Start . Siguiente [ 0 ]) ParActual = ParActual -> Anterior ; más ParActual = NULL ; devolver * esto ; } plantilla < nombre de tipo KEY_T , nombre de tipo DATA_T > typename SkipList < KEY_T , DATA_T >:: Iterator SkipList < KEY_T , DATA_T >:: Iterator :: operador ++ ( int ){ Iterador Antiguo ( * esto ); ++* esto ; volver viejo ; } plantilla < nombre de tipo KEY_T , nombre de tipo DATA_T > typename SkipList < KEY_T , DATA_T >:: Iterator SkipList < KEY_T , DATA_T >:: Iterator :: operator -- ( int ){ Iterador Antiguo ( * esto ); --* esto ; volver viejo ; } plantilla < nombre de tipo KEY_T , nombre de tipo DATA_T > typename SkipList < KEY_T , DATA_T >:: Iterator & SkipList < KEY_T , DATA_T >:: Iterator :: operator = ( const SkipList < KEY_T , DATA_T >:: Iterator & InIterator ){ ListaActual = InIterador . ListaActual ; ParActual = InIterador . Pareja actual ; devolver * esto ; } plantilla < nombre de tipo KEY_T , nombre de tipo DATA_T > typename SkipList < KEY_T , DATA_T >:: Iterator & SkipList < KEY_T , DATA_T >:: Iterator :: operator = ( const KEY_T & InKey ){ CurrentPair = CurrentList -> PairByKey ( InKey ); devolver * esto ; } plantilla < nombre de tipo KEY_T , nombre de tipo DATA_T > DATA_T & SkipList < KEY_T , DATA_T >:: Iterador :: operador * (){ si ( !* esto ) throw String ( "¡Leyendo desde un iterador incorrecto!" ); volver CurrentPair -> Datos ; } plantilla < nombre de tipo KEY_T , nombre de tipo DATA_T > void SkipList < KEY_T , DATA_T >:: Iterator :: Delete (){ si ( !* esto ) throw String ( "¡Eliminando datos del iterador incorrecto!" ); borrar CurrentPair ; ParActual = NULL ; } plantilla < nombre de tipo KEY_T , nombre de tipo DATA_T > typename SkipList < KEY_T , DATA_T >:: Iterator & SkipList < KEY_T , DATA_T >:: Iterator :: operator += ( size_t n ){ para ( tamaño_t Contador = 0 ; Contador < n && CurrentPair ; Contador ++ ) ParActual = ParActual -> Siguiente [ 0 ]; devolver * esto ; } plantilla < nombre de tipo KEY_T , nombre de tipo DATA_T > typename SkipList < KEY_T , DATA_T >:: Iterator & SkipList < KEY_T , DATA_T >:: Iterator :: operator -= ( size_t n ){ para ( tamaño_t Contador = 0 ; Contador < n && CurrentPair ; Contador ++ ) ParActual = ParActual -> Anterior ; if ( PairActual ==& ListaActual -> Inicio ) devolver * esto ; } plantilla < nombre de tipo KEY_T , nombre de tipo DATA_T > nombre de tipo SkipList < KEY_T , DATA_T >:: Iterator SkipList < KEY_T , DATA_T >:: GetBegin ( ){ iterador de retorno ( * esto ); } plantilla < nombre de tipo KEY_T , nombre de tipo DATA_T > nombre de tipo SkipList < KEY_T , DATA_T >:: Iterator SkipList < KEY_T , DATA_T >:: GetEnd ( ){ Iterador ReturnValue ( * esto ); ValorRetorno += ValorRetorno . ListaActual -> Cuenta () -1 ; devolver ValorDevuelto ; } plantilla < nombre de tipo KEY_T , nombre de tipo DATA_T > typename SkipList < KEY_T , DATA_T >:: Iterator SkipList < KEY_T , DATA_T >:: Find ( const DATA_T & Unknown ){ Resultado del iterador ( * this ); while ( Resultado && ! ( * Resultado == Desconocido )) ++ resultado ; devolver resultado ; } plantilla < nombre de tipo KEY_T , nombre de tipo DATA_T > bool SkipList < KEY_T , DATA_T >:: IsEmpty (){ typename Array < Pair *>:: Iterator i ( Inicio . Siguiente ); mientras ( yo ) si ( * yo ++ ) devolver falso ; devolver verdadero ; }

Notas

  1. ↑ Pugh, William. Saltar listas: una alternativa probabilística a los árboles equilibrados  // Comunicaciones de la ACM  :  revista. - 1990. - junio ( vol. 33 , no. 6 ). - Pág. 668-676 . doi : 10.1145 / 78973.78977 .

Literatura

  • Guillermo Pugh. Saltar listas: una alternativa probabilística a los árboles balanceados / Taller sobre algoritmos y estructuras de datos. Springer Berlín Heidelberg, 1989; Comunicaciones de la ACM Archivo de la página principal del CACM Volumen 33 Número 6, junio de 1990 Páginas 668-676 doi: 10.1145/78973.78977  - trabajo original
  • Manning K., Raghavan P., Schütze H. Introducción a la recuperación de información. - Williams , 2011. - 512 págs. - ISBN 978-5-8459-1623-5 .

Enlaces

 Estructuras de datos
Liza
Árboles
cuenta
Otro