Skip list | EPFL Graph Search

Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?

Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.

Découvrez-en plus sur les applications Graph.

En informatique, et plus précisément en algorithmique, une skip list, ou liste à enjambements, ou liste à saut, 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. Les skip lists ont été inventées par William Pugh, d'abord présentées dans un rapport technique en 1989 puis présentées dans une publication en 1990. L'auteur, dans son rapport technique les compare avec les arbres binaires de recherche balancé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) balancé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 balancés, et sont plus simples, plus rapides et utilisent moins de mémoire) 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 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.

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Publications associées (2)

Personnes associées (2)

Concepts associés (3)

Séances de cours associées (18)

Generalization Properties of NAS under Activation and Skip Connection Search

Volkan Cevher, Grigorios Chrysos, Zhenyu Zhu

Neural Architecture Search (NAS) has fostered the automatic discovery of stateof- the-art neural architectures. Despite the progress achieved with NAS, so far there is little attention to theoretical

2022

Scalable peer-to-peer Web search using highly discriminative keys

Vinh Toan Luu

Standard general-purpose Web retrieval relies on centralized search engines that do not realistically scale when applied to the exponentially growing number of documents available on the Web. By takin

EPFL2007

Structures de données élémentaires : piles, files d'attente, listes liées

Couvre les piles, les files d'attente et les listes liées, en mettant l'accent sur l'efficacité et les structures dynamiques.

Recherche Binaire: Bases et Exécution

Explore les fondamentaux de la recherche binaire, l'efficacité et la complexité temporelle dans la recherche algorithmique.

Arbres de recherche binaires: mise en œuvre et opérations

Couvre la mise en œuvre et les opérations des structures de données de base telles que les piles, les files d'attente et les listes liées, et introduit des arbres de recherche binaires.

Skip list

Self-balancing binary search tree

In computer science, a self-balancing binary search tree (BST) is any node-based binary search tree that automatically keeps its height (maximal number of levels below the root) small in the face of arbitrary item insertions and deletions. These operations when designed for a self-balancing binary search tree, contain precautionary measures against boundlessly increasing tree height, so that these abstract data structures receive the attribute "self-balancing".

Tableau (structure de données)

En informatique, un tableau est une structure de données représentant une séquence finie d'éléments auxquels on peut accéder efficacement par leur position, ou indice, dans la séquence. C'est un type de conteneur que l'on retrouve dans un grand nombre de langages de programmation. Dans les langages à typage statique (comme C, Java et OCaml), tous les éléments d’un tableau doivent être du même type. Certains langages à typage dynamique (tels APL et Python) permettent des tableaux hétérogènes.