Skip-list

Skip-list

Une Skip-list (liste à enjambements) est une structure de données probabiliste, à base de listes chaînées parallèles. La plupart de ses opérations s'effectuent en O(log n)[1] avec une grande probabilité.

Sommaire

Description

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" (skip) 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 0, ..., 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) listes, et l'élément le plus haut (souvent un élément factice[2] plus petit que tous les autres) apparaît dans O(log1/p n) couches.

1
1-----4---6
1---3-4---6-----9
1-2-3-4-5-6-7-8-9-10

Opération de recherche

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 est é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 O\left(\log_\frac{1}{p}\left(n/p\right)\right) ; ce qui revient à O(log(n)) 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é.

Autres opérations

L'insertion et la suppression s'implémentent comme dans une liste chaînée, sauf que les éléments "hauts"[3] doivent être insérés et supprimés dans plusieurs couches.

Performances

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[4].

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.

Une réserve cependant : dans les implémentations réelles, on a mesuré que leurs performances en temps et en espace sont inférieures à celles des B-trees. Cela est dû à des problématiques telles que la proximité des données dans les mémoires cache.

Histoire

Les skip-lists ont été inventées par William Pugh en 1990. Il explique leur fonctionnement dans Skip lists: a probabilistic alternative to balanced trees in Communications of the ACM, June 1990, 33(6) 668-676.

Références

  1. n est le nombre d'éléments contenus dans la liste.
  2. 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
  3. 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.
  4. 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.

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Skip-list de Wikipédia en français (auteurs)

Игры ⚽ Поможем решить контрольную работу

Regardez d'autres dictionnaires:

  • Skip list — Invented in 1990 by William Pugh, a skip list is a probabilistic data structure, based on multiple parallel, sorted linked lists, with efficiency comparable to a binary search tree (order log n average time for most operations).Underlying the… …   Wikipedia

  • Skip list — Una skip list o lista por saltos es una Estructura de datos, basada en Listas enlazadas paralelas con eficiencia comparable a la de un árbol binario (tiempo en orden O(log n) para la mayoría de las operaciones). Una lista por saltos se construye… …   Wikipedia Español

  • Skip list — Una skip list o lista por saltos es una Estructura de datos, basada en Listas enlazadas paralelas con eficiencia comparable a la de un árbol binario (tiempo en orden O(log n) para la mayoría de las operaciones). Una lista por saltos se construye… …   Enciclopedia Universal

  • Skip liste — Skip list Une Skip list (liste à enjambements) est une structure de données probabiliste, à base de listes chaînées parallèles. La plupart de ses opérations s effectuent en O(log n)[1] avec une grande probabilité. Sommaire 1 Description 2… …   Wikipédia en Français

  • List of terms relating to algorithms and data structures — The [http://www.nist.gov/dads/ NIST Dictionary of Algorithms and Data Structures] is a reference work maintained by the U.S. National Institute of Standards and Technology. It defines a large number of terms relating to algorithms and data… …   Wikipedia

  • Skip (homonymie) — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Sur les autres projets Wikimedia : « Skip (homonymie) », sur le Wiktionnaire (dictionnaire universel) Un skip est une benne roulant sur un… …   Wikipédia en Français

  • List of combinatorics topics — This is a list of combinatorics topics.A few decades ago it might have been said that combinatorics is little more than a way to classify poorly understood problems, and some standard remedies. Great progress has been made since 1960.This page is …   Wikipedia

  • Skip James — The only photograph of James in his youth. Background information Birth name Nehemiah Curtis James Born …   Wikipedia

  • List of Skip Beat chapters — Skip Beat! by Yoshiki Nakamura is currently being published in Japan by Hakusensha. It is being serialized in the magazine Hana to Yume since February of 2005. In North America it is being published by the Shojo Beat label. There are currently 19 …   Wikipedia

  • Skip Weshner — (1927 1995) was a disc jockey on stations in New York and Los Angeles from the mid 1950 s until the mid 1980 s. In particular, he hosted a popular show on KRHM FM in Los Angeles. He hosted Accent On Sound on WBAI (FM) and later WNCN (FM) in New… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”