Como funciona uma lista de pulos?

Para uma tarefa de casa, preciso entender como funciona uma lista de pulos.

Estou programando há pouco mais de 2 anos (sei que isso não é tão longo na realidade) e nunca ouvi falar de uma lista de pulos.

Examinei todos os guias que consigo encontrar e ainda mal compreendo como eles funcionam. Até procurei no Code Review por um exemplo de implementação e encontrei apenas um comentário; e nem sequer é uma implementação completa. Examinei a implementação de amostra fornecida pelo curso e é absolutamente atroz. Entre a falta de métodos adequados e os nomes de variáveis ​​de uma letra, não tenho idéia de como isso funciona.

Como funciona uma lista de pulos? É necessário o conhecimento de uma lista de ignorados para entender estruturas de dados mais avançadas?

Antigamente, na aula de estruturas de dados, aprendíamos como as árvores AVL funcionavam . Eu teria tido isso em uma das minhas aulas, mas o instrutor disse "você nunca vai usar isso" e, em vez disso, pediu que aprendêssemos 2-3 árvores e árvores *. Aqueles eram dias em que a memória estava fraca e os processos eram encadeados individualmente. Você não usou um deque quando uma lista com link único também funcionaria.

A lista de ignorados é muito mais comum hoje em dia, com mais memória disponível e simultaneidade sendo um problema (você não precisa bloquear muito quando atua como escritor em uma lista de ignorados - em comparação com tudo com uma árvore AVL).

Francamente, agora é minha estrutura de dados favorita, pois é algo que eu posso facilmente raciocinar sobre como funciona por baixo e onde será vantajoso ou desvantajoso de usar.

Você não precisará escrever uma do zero (a menos que a receba como uma pergunta de entrevista - mas é provável que você implemente uma árvore AVL).

Você está indo a necessidade de entender por que você quer selecionar um ConcurrentSkipListMapem Java em vez de um HashMapou TreeMapou qualquer uma das outras implementações do mapa.

Para entender como funciona, você precisa entender como uma árvore binária funciona. Espere, deixe-me corrigir isso. Você precisa entender como uma árvore binária equilibrada funciona. Sem balancear uma árvore binária, você não obtém nenhuma vantagem real com sua pesquisa.

Digamos que temos essa árvore:

E nós inserimos um '8' nele. Agora temos:

E isso não é equilibrado. Então, vamos fazer o mágica de equilibrá-lo através de alguma implementação ...

E você tem uma árvore equilibrada novamente. Mas foi muita magia que acenei com a mão.

Vamos fazer uma lista de pulos.

Esse aqui é idealizado. Poucos são, mas mostra a natureza equilibrada da árvore binária que o ideal do skiplist aproxima.

Agora, queremos inserir um 6 nele. Isso é inseri-lo como uma lista vinculada. No entanto, começamos do topo e descemos. Os pontos principais para 5. É 6> 5? Sim. Ok, o topo aponta para o final agora, então descemos a pilha (estamos no 5). O próximo é 7. É 6> 7? Não. Então, descemos um nível e estamos no nível base e inserimos 6 à direita dos 5.

Nós jogamos uma moeda - cabeças que construímos, caudas que ficamos. Caudas. Nada mais precisa ser feito.

Vamos inserir esse 8 agora. 8> 5? Sim. 8> 7? Sim. E agora estamos no nível inferior novamente depois de seguir as setas e a pilha ao redor e testar 8> 11? Não. Então, inserimos o 8 à direita do 7.

Nós jogamos uma moeda - cabeças que construímos, caudas que ficamos. Caudas. Nada mais precisa ser feito.

Na árvore equilibrada, estaríamos todos preocupados porque a árvore não está equilibrada agora. Mas isso não é uma árvore - é uma lista de pulos. Nós aproximamos uma árvore equilibrada.

Agora vamos inserir um 10. Vou evitar todas as comparações.

Nós jogamos uma moeda - cabeças que construímos, caudas que ficamos. Cabeças! E vire novamente, cabeças novamente! Virá-lo novamente, ok, há uma coroa. Dois níveis acima da lista vinculada à base.

A vantagem aqui é que agora, se vamos inserir um 12, podemos pular de 5 para 10 sem fazer todas as outras comparações. Podemos pular sobre eles com a lista de pulos. E não precisamos nos preocupar com a árvore equilibrada - a natureza probabilística do empilhamento faz isso por nós.

Por que isso é tão útil? Porque, ao inserir os 10, posso fazer isso bloqueando a gravação nos ponteiros 5, 7 e 8, em vez de em toda a estrutura. E enquanto estou fazendo isso, os leitores ainda podem passar pela lista de ignorados sem ter um estado inconsistente. Para uso simultâneo, é mais rápido não ter que bloquear. Para iterar sobre a camada inferior, é mais rápido que uma árvore (as alegrias dos algoritmos BFS e DFS para a navegação em árvore - você não precisa se preocupar com eles).

Você vai encontrá-lo? Você provavelmente o verá em uso em alguns lugares. E você saberá por que o autor escolheu essa implementação em vez de uma TreeMapou HashMappara a estrutura.

Muito disso foi emprestado do meu blog: The Skip List