Skip list
En informatique, et plus précisément en algorithmique, une skip list, ou liste à enjambements[1], ou liste à saut[2], est une structure de données probabiliste, à base de listes chaînées parallèles. La plupart de ses opérations s'effectuent en temps O(log n) avec une grande probabilité, où n est le nombre d'éléments contenus dans la liste.
Histoire modifier
Les skip lists ont été inventées par William Pugh, d'abord présentées dans un rapport technique en 1989[3] puis présentées dans une publication en 1990[4]. L'auteur, dans son rapport technique les compare avec les arbres binaires de recherche équilibrés, écrit :
''Skip lists are a probabilistic data structure that seem likely to supplant balanced trees as the implementation method of choice for many applications. Skip list algorithms have the same asymptotic expected time bounds as balanced trees and are simpler, faster and use less space.''
(Les skip lists sont une structure de données qui a l'air de surpasser les arbres (binaires de recherche) équilibrés comme une méthode d'implémentation de choix pour plusieurs applications. Les algorithmes des skip lists ont la même complexité asymptotique en espérance que les arbres équilibrés, et sont plus simples, plus rapides et utilisent moins de mémoire)
Description modifier
Une skip list se présente comme une amélioration d'une liste chaînée triée. Elle contient des pointeurs supplémentaires vers l'avant, ajoutés de façon aléatoire, de sorte que la recherche dans la liste puisse « sauter » (to skip en anglais) de nombreux éléments.
La skip list est organisée en couches. La couche la plus basse est simplement une liste chaînée standard. Chaque couche supérieure i+1 est une « voie rapide » pour parcourir les couches inférieures 1, …, i. Un élément présent sur la couche i a une probabilité fixée p de faire partie de la couche i+1. En moyenne, chaque élément apparaît dans 1/(1-p) couches, et l'élément le plus haut (souvent un élément factice[5] plus petit que tous les autres) apparaît dans toutes les couches. La skip list contient O(log1/p n) couches, où n est le nombre d'éléments total.
L'exemple suivant montre une skip list contenant 10 éléments avec 4 couches :
couche 4 1 couche 3 1-----4---6 couche 2 1---3-4---6-----9 couche 1 1-2-3-4-5-6-7-8-9-10
Opération de recherche modifier
La recherche commence par le plus petit élément, sur la couche la plus haute. Pour chaque couche visitée, on parcourt les chaînons jusqu'à atteindre le dernier élément inférieur ou égal à l'élément recherché. Alors, si cet élément est strictement inférieur à la valeur recherchée, on descend verticalement dans la couche suivante. L'espérance du nombre de pas dans chaque couche est 1/p. Le coût total de la recherche est en ; ce qui revient à si l'on considère p comme fixé.
En jouant sur la valeur de ce paramètre p, on obtient un compromis entre temps de recherche et espace mémoire consommé. Pour p = 0, la skip list est une liste chaînée standard (une couche seulement). Plus p proche de 1, plus il y a de couches.
Autres opérations modifier
L'insertion et la suppression s'implémentent comme dans une liste chaînée, sauf que les éléments « hauts »[6] doivent être insérés et supprimés dans plusieurs couches.
Performances modifier
De par sa nature probabiliste, cette structure de données ne donne pas les mêmes garanties sur les pires cas que, par exemple, les arbres équilibrés. En effet, il est très peu probable mais néanmoins possible que l'agencement aléatoire ait pu produire une structure très déséquilibrée[7].
En fait, ces listes fonctionnent très bien en pratique, et sont réputées plus faciles à implémenter que leur équivalent déterministe à base de rééquilibrage d'arbres. Dans les implémentations réelles, on a mesuré que leurs performances en temps et en espace sont inférieures à celles des B-trees[réf. souhaitée]. Cela est dû à des problématiques telles que la proximité des données dans les mémoires cache.
Variantes et extensions modifier
Dans les skip listes déterministes, les éléments à sauter ne sont pas choisis aléatoirement mais de manière déterministe[8].
Références modifier
- Référence pour la traduction en français : Salma Ktari, Interconnexion et routage dans les systèmes pair à pair (Thèse de doctorat), École Nationale Supérieure des Télécommunications, .
- Cormen et al., Algorithmique, (lire en ligne), p. 314 (dernier paragraphe)
- Pugh, William (April 1989). Concurrent Maintenance of Skip Lists (PS, PDF) (Technical report). Dept. of Computer Science, U. Maryland. CS-TR-2222.
- (en) William Pugh, « Skip lists: a probabilistic alternative to balanced trees », Communications of the ACM, vol. 6, no 33, , p. 668-676.
- Cet élément factice est physiquement présent en mémoire mais ne fait pas partie fonctionnellement de la liste, dans la mesure où l'utilisateur ne l'y a pas inséré et ne désire pas le consulter.
- Un élément haut est un élément présent dans plusieurs couches (voir la figure) ; ce n'est pas forcément un grand élément.
- Par exemple, si les couches supérieures ne contiennent que des éléments de la première moitié de la liste, alors la recherche d'un grand élément est catastrophique.
- (en) Ian Munro (en), Thomas Papadakis et Robert Sedgewick « Deterministic skip lists » (DOI 10.1145/139404.139478, lire en ligne)
— « (ibid.) », dans Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms (SODA '92), Orlando (Floride), Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, , p. 367–375
