Comment fonctionne une liste de sauts?

Pour un devoir, j'ai besoin de comprendre comment fonctionne une liste de sauts .

Je programme depuis un peu plus de 2 ans maintenant (je sais que ce n'est pas si long en réalité), et je n'ai même jamais entendu parler d'une liste à sauter.

J'ai parcouru tous les guides que je peux trouver, et je comprends encore à peine comment ils fonctionnent. J'ai même cherché Code Review pour un exemple d'implémentation et trouvé un seul examen; et ce n'est même pas une implémentation complète. J'ai regardé l'exemple d'implémentation fourni par le cours, et c'est absolument atroce. Entre le manque de méthodes appropriées et les noms de variables à une seule lettre, je n'ai aucune idée de comment cela fonctionne.

Comment fonctionne une liste de sauts? La connaissance d'une liste de sauts est-elle nécessaire pour comprendre des structures de données plus avancées?

Autrefois, dans la classe des structures de données, nous avons appris comment fonctionnaient les arbres AVL . J'aurais eu ça dans une de mes classes, mais l'instructeur a dit "vous ne l'utiliserez jamais réellement" et nous a plutôt fait apprendre 2-3 arbres et arbres b * à la place. C'étaient des jours où la mémoire était serrée et les processus étaient enfilés individuellement. Vous n'avez pas utilisé de deque lorsqu'une liste liée individuellement fonctionnerait aussi bien.

La liste de sauts est beaucoup plus courante aujourd'hui, avec plus de mémoire disponible et d'accès concurrentiel étant un problème (vous n'avez pas besoin de verrouiller beaucoup du tout lorsque vous agissez en tant qu'écrivain dans une liste de sauts - par rapport à tout avec une arborescence AVL).

Franchement, c'est ma structure de données préférée maintenant en ce sens que je peux facilement raisonner sur la façon dont cela fonctionne en dessous et où il sera avantageux ou désavantageux d'utiliser.

Vous n'aurez pas besoin d'en écrire une à partir de zéro (à moins que vous ne la receviez comme une question d'entrevue - mais alors vous êtes tout aussi susceptible de mettre en œuvre une arborescence AVL).

Vous êtes allez avoir besoin de comprendre pourquoi vous souhaitez sélectionner un ConcurrentSkipListMapen Java plutôt qu'un HashMapou TreeMapou l' une des autres implémentations de carte.

Pour comprendre comment cela fonctionne, vous devez comprendre le fonctionnement d'un arbre binaire. Attendez, permettez-moi de modifier cela. Vous devez comprendre le fonctionnement d'un arbre binaire équilibré . Sans équilibrer un arbre binaire, vous n'obtenez aucun avantage réel avec sa recherche.

Disons que nous avons cet arbre:

Et nous y insérons un «8». Maintenant, nous avons:

Et ce n'est pas équilibré. Donc, nous allons faire la magie de l'équilibrer via une implémentation ...

Et vous avez à nouveau un arbre équilibré. Mais c'était beaucoup de magie, j'ai agité ma main.

Prenons une liste à sauter.

Celui-ci se trouve être idéalisé. Peu le sont, mais cela montre la nature équilibrée des arbres binaires que l'idéal skiplist se rapproche.

Maintenant, nous voulons insérer un 6 là-dedans. Cela l'insère un peu comme une liste chaînée. Cependant, nous commençons par le haut et descendons. Les premiers points à 5. Est-ce que 6> 5? Oui. D'accord, le sommet pointe à la fin maintenant, alors nous descendons la pile (nous sommes sur le 5). Le suivant est 7. Is 6> 7? Nan. On descend donc d'un niveau et on est au niveau de base donc on insère 6 à droite du 5.

Nous lançons une pièce - des têtes que nous construisons, des queues que nous restons. Tails. Il n'y a plus rien à faire.

Permet d'insérer ce 8 maintenant. 8> 5? oui. 8> 7? Oui. Et maintenant, nous sommes à nouveau au niveau inférieur après avoir suivi les flèches et la pile autour et nous testons 8> 11? Nan. Nous insérons donc le 8 à droite du 7.

Nous lançons une pièce - des têtes que nous construisons, des queues que nous restons. Tails. Il n'y a plus rien à faire.

Dans l'arbre équilibré, nous aurions tous travaillé sur le fait que l'arbre ne soit pas équilibré maintenant. Mais ce n'est pas un arbre - c'est une liste à sauter. Nous approchons un arbre équilibré.

Insérons maintenant un 10. J'éviterai toutes les comparaisons.

Nous lançons une pièce - des têtes que nous construisons, des queues que nous restons. Têtes! Et retournez-le à nouveau, têtes à nouveau! Retournez-le à nouveau, ok, il y a une queue. Deux niveaux au-dessus de la liste chaînée de base.

L'avantage ici est que maintenant, si nous allons insérer un 12, nous pouvons passer de 5 à 10 sans faire toutes ces autres comparaisons. Nous pouvons les ignorer avec la liste de sauts. Et nous n'avons pas à nous soucier de l'arbre équilibré - la nature probabiliste de l'empilement le fait pour nous.

Pourquoi est-ce si utile? Parce que lors de l'insertion du 10, je peux le faire en verrouillant l'écriture sur les pointeurs 5 et 7 et 8 plutôt que sur la structure entière. Et pendant que je fais cela, les lecteurs peuvent toujours parcourir la liste de sauts sans avoir un état incohérent. Pour une utilisation simultanée, il est plus rapide de ne pas avoir à verrouiller. Pour itérer sur la couche inférieure, c'est plus rapide qu'un arbre (les joies des algorithmes BFS et DFS pour la navigation dans les arbres - vous n'avez pas à vous en soucier).

Le rencontrerez-vous? Vous le verrez probablement utilisé par endroits. Et vous saurez alors pourquoi l'auteur a choisi cette implémentation plutôt que a TreeMapou HashMappour la structure.

Une grande partie de cela a été empruntée à mon article de blog: La liste à sauter