Skip list

Skip list
Instancia de lista probabilistic data structure (en)
Implicados  Inventor/a ou descubridor/a William Pugh (pt)
Datas  Fundación / creación 1989  Descuberta / invención 1989
Fontes e ligazóns Freebase /m/01xj5l
Wikidata C:Commons

Imaxe esquemática da estrutura de datos skip list. Cada caixa cunha frecha representa un punteiro, e cada fila é unha lista ligada que dá unha subsecuencia dispersa; as caixas numeradas (en amarelo) da parte inferior representan a secuencia de datos ordenada. A busca avanza cara abaixo desde a subsecuencia máis dispersa da parte superior ata atopar dous elementos consecutivos que enmarcan o elemento buscado.

En ciencias da computación, unha skip list é unha estrutura de datos probabilística que permite unha complexidade media de ${\mathcal {O}}(\log n)$ para a busca e tamén ${\mathcal {O}}(\log n)$ para a inserción dentro dunha secuencia ordenada de $n$ elementos. Así, obtén as mellores características dun vector ordenado (para a busca) mantendo unha estrutura semellante a unha lista ligada que permite a inserción, o que non é posible cun vector estático. A busca rápida faise posible mantendo unha xerarquía ligada de subsecuencias, na que cada subsecuencia sucesiva salta sobre menos elementos cá anterior (véxase a imaxe). A busca comeza na subsecuencia máis dispersa ata atopar dous elementos consecutivos, un menor e outro maior ou igual cá chave buscada. A través da xerarquía ligada, estes dous elementos ligazónanse a elementos da seguinte subsecuencia menos dispersa, onde a busca continúa ata chegar finalmente á secuencia completa. Os elementos saltados pódense escoller probabilisticamente ou de forma determinista.

Descrición

Unha skip list constrúese en capas. A inferior é unha lista ligada ordenada, e cada capa superior actúa como unha «vía rápida». Cada elemento ascende ao nivel seguinte cunha probabilidade fixa $0<p<1$, habitualmente $1/2$ ou $1/4$. Sen límite de altura, un elemento aparece de media en $1/(1-p)$ capas, e a altura máxima entre $n$ elementos é da orde de $\log _{1/p}n$ en esperanza, non unha igualdade exacta. A cabeceira dispón de ligazóns para todos os niveis. A cota de espazo $O(n\log n)$ no peor caso supón un límite de niveis $O(\log n)$; sen ese límite, a distribución xeométrica non ten unha altura máxima determinista.

A busca dun elemento obxectivo comeza na cabeceira do nivel superior. Avanza mentres a seguinte chave sexa menor ca o obxectivo e, antes de superalo, baixa un nivel. Ao chegar ao nivel inferior compróbase a seguinte chave. A análise do camiño cara atrás dá unha cota esperada de orde ${\tfrac {1}{p}}\log _{1/p}n$, é dicir, $O(\log n)$ para $p$ constante; esa expresión non é o custo exacto de toda busca. Escoller $p$ permite trocar custo de busca por almacenamento. O valor $p=1/e$ minimiza o coeficiente principal desa cota, pero non garante o mellor tempo práctico nunha implementación concreta.

Detalles de implementación

Inserción de elementos nunha skip list.

Os elementos dunha skip list poden conter máis dun punteiro, xa que poden participar en máis dunha lista.

As insercións e os borrados impleméntanse de forma moi parecida ás operacións correspondentes nunha lista ligada, agás que os elementos «altos» hai que inserilos ou borralos de máis dunha lista ligada.

As operacións ${\mathcal {O}}(n)$, que obrigan a visitar cada nó en orde ascendente (como imprimir a lista enteira), dan a oportunidade de realizar unha desrandomización entre bastidores da estrutura de niveis da skip list de forma óptima, levando a skip list a un tempo de busca ${\mathcal {O}}(\log n)$. (Escóllese o nivel do i-ésimo nó finito como 1 máis o número de veces que se pode dividir repetidamente i por 2 antes de que se volva impar.) Con todo, isto tamén permite saber onde están todos os nós de nivel superior a 1 e borralos.

Alternativamente, a estrutura de niveis pódese facer case aleatoria do seguinte xeito:

make all nodes level 1
j ← 1
while the number of nodes at level j > 1 do
    for each i'th node at level j do
        if i is odd and i is not the last node at level j
            randomly choose whether to promote it to level j+1
        else if i is even and node i-1 was not promoted
            promote it to level j+1
        end if
    repeat
    j ← j + 1
repeat

Como na versión desrandomizada, a cuasialeatoriedade só se fai cando hai algunha outra razón para executar unha operación ${\mathcal {O}}(n)$ (que visita cada nó).

A vantaxe desta cuasialeatoriedade é que non revela tanta información sobre a estrutura de niveis a un usuario adversario como a desrandomizada. Isto é desexable porque un usuario adversario que poida saber que nós non están no nivel máis baixo pode empeorar o rendemento simplemente borrando os nós de nivel superior. (Bethea e Reiter argumentan, con todo, que un adversario pode usar métodos probabilísticos e de temporización para forzar a degradación do rendemento.) O rendemento da busca segue estando garantido como logarítmico.

Sería tentador facer a seguinte «optimización»: na parte que di «Logo, para cada i-ésimo...», esquecer facer un lanzamento de moeda por cada par par-impar e lanzar unha soa moeda para decidir se promover só os pares ou só os impares. O pseudocódigo anterior usa $O(n)$ lanzamentos en total, porque cada nivel ten como máximo a metade dos nós do anterior; cunha soa moeda por nivel usaríanse $O(\log n)$. Porén, isto dálle ao usuario adversario unha probabilidade do 50 % de acertar ao adiviñar que todos os nós de número par do primeiro nivel ascenderon ao segundo.

Unha skip list non ofrece as mesmas garantías de rendemento no peor caso absoluto que as estruturas de árbore equilibrada máis tradicionais, porque sempre é posible (aínda que cunha probabilidade moi baixa) que os lanzamentos de moeda usados para construír a skip list produzan unha estrutura mal equilibrada. Con todo, funcionan ben na práctica, e argumentouse que o esquema de equilibrio aleatorizado é máis doado de implementar cós esquemas deterministas usados nas árbores binarias de busca equilibradas. As skip lists tamén son útiles na computación paralela, onde as insercións se poden facer en distintas partes da skip list en paralelo sen ningún reequilibrado global da estrutura. Este paralelismo pode ser especialmente vantaxoso para o descubrimento de recursos nunha rede sen fíos ad hoc, porque unha skip list aleatorizada se pode facer robusta á perda de calquera nó individual.

Skip list indexable

Como se describiu, unha skip list permite inserción e borrado rápidos ${\mathcal {O}}(\log n)$ de valores nunha secuencia ordenada, pero só ten buscas lentas ${\mathcal {O}}(n)$ de valores nunha posición dada da secuencia (é dicir, devolver o valor 500). Con todo, cunha pequena modificación pódese mellorar a velocidade das buscas indexadas de acceso aleatorio a ${\mathcal {O}}(\log n)$.

Para cada ligazón, gárdase tamén a súa anchura. A anchura defínese como o número de ligazóns da capa inferior que percorre cada ligazón «vía rápida» das capas superiores.

Por exemplo, aquí están as anchuras das ligazóns do exemplo da parte superior da páxina:

   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º   NIL
       Nó    Nó    Nó    Nó    Nó    Nó    Nó    Nó    Nó    Nó

Obsérvese que a anchura dunha ligazón de nivel superior é a suma das ligazóns compoñentes inferiores (por exemplo, a ligazón de anchura 10 abrangue as ligazóns de anchuras 3, 2 e 5 inmediatamente debaixo). En consecuencia, a suma de todas as anchuras é a mesma en cada nivel.

Para indexar a skip list e atopar o i-ésimo valor, recórrese a skip list mentres se restan as anchuras de cada ligazón percorrida. Descéndese un nivel sempre que a seguinte anchura sexa demasiado grande.

Por exemplo, para atopar o nó en quinta posición (Nó 5), recórrese unha ligazón de anchura 1 no nivel superior. Agora fan falta catro pasos máis, pero a seguinte anchura neste nivel é dez, que é demasiado grande, polo que se baixa un nivel. Recórrese unha ligazón de anchura 3. Como outro paso de anchura 2 sería demasiado, báixase ao nivel inferior. Agora recórrese a ligazón final de anchura 1 para acadar o total obxectivo de 5 (1+3+1).

O seguinte pseudocódigo usa un índice i baseado en cero e supón $0\leq i<n$, onde $n$ é o número de elementos.

function lookupByPositionIndex(i)
    node ← head
    i ← i + 1                           # non contar a cabeza como un paso
    for level from top to bottom do
        while i ≥ node.width[level] do # se o seguinte paso non é demasiado
            i ← i - node.width[level]  # restar a anchura actual
            node ← node.next[level]    # avanzar no nivel actual
        repeat
    repeat
    return node.value
end function

Este método de implementar a indexación detállase en «A skip list cookbook», de William Pugh.

Historia

As skip lists foron descritas por primeira vez en 1989 por William Pugh.

Citando o autor:

«As skip lists son unha estrutura de datos probabilística que parece probable que substitúa as árbores equilibradas como método de implementación preferido en moitas aplicacións. Os algoritmos de skip list teñen as mesmas cotas de tempo esperado asintóticas cás árbores equilibradas e son máis simples, máis rápidos e usan menos espazo.» (tradución do inglés)

— William Pugh, Concurrent Maintenance of Skip Lists (1989)

Usos

Lista de aplicacións e marcos que usan skip lists:

• Apache Portable Runtime implementa skip lists.
• MemSQL usa skip lists sen bloqueos como a súa principal estrutura de indexación para a súa tecnoloxía de bases de datos.
• MuQSS, para o núcleo Linux, é un planificador de CPU construído sobre skip lists.
• Cyrus IMAP server ofrece unha implementación de base de datos de backend «skiplist».
• IBM DOORS ofrece skip lists como tipo de datos na súa linguaxe de script DOORS/DXL.
• Lucene usa ligazóns de salto para buscar nas listas invertidas de documentos (posting lists) con codificación delta.
• A clase modelo «QMap» (dicionario chave/valor, ata Qt 4) de Qt está implementada con skip lists.
• Redis, un almacén chave/valor persistente de código aberto en C ANSI para sistemas Posix, usa skip lists na implementación dos conxuntos ordenados.
• Discord usa skip lists para xestionar o almacenamento e a actualización da lista de membros dun servidor.
• RocksDB usa skip lists para a súa implementación predeterminada de Memtable.
• Java usa skip lists para as súas clases ConcurrentSkipListSet e ConcurrentSkipListMap.

As skip lists tamén se usan en aplicacións distribuídas (onde os nós representan ordenadores físicos e os punteiros representan conexións de rede) e para implementar colas de prioridade concorrentes altamente escalables con menos contención de bloqueos, ou mesmo sen bloqueos, así como dicionarios concorrentes libres de bloqueos.

Véxase tamén

Outros artigos

• Filtro de Bloom
• Skip graph
• Estrutura de datos probabilística

Ligazóns externas

• Skip lists en Wikimedia Commons (en inglés)
• Entrada «Skip list» no Dictionary of Algorithms and Data Structures (en inglés)
• Open Data Structures - Capítulo 4 - Skiplists, Pat Morin (en inglés)