Liste chaînée

Résumé

Une liste chaînée ou liste liée (en anglais linked list) désigne en informatique une structure de données représentant une collection ordonnée et de taille arbitraire d'éléments de même type, dont la représentation en mémoire de l'ordinateur est une succession de cellules faites d'un contenu et d'un pointeur vers une autre cellule. De façon imagée, l'ensemble des cellules ressemble à une chaîne dont les maillons seraient les cellules. L'accès aux éléments d'une liste se fait de manière séquentielle : chaque élément permet l'accès au suivant (contrairement au tableau dans lequel l'accès se fait de manière directe, par adressage de chaque cellule dudit tableau). Principe Le principe de la liste chaînée est que chaque élément possède, en plus de la donnée, un pointeur vers un élément qui lui est contigu dans la liste. L'usage d'une liste est souvent préconisé pour des raisons de rapidité de traitement, lorsque l'ordre des éléments est important et que les insertions et les su

Source officielle

https://fr.wikipedia.org/wiki/Liste_cha%C3%AEn%C3%A9e

À 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)

Publications associées

Chargement

Personnes associées

Aucun résultat

Personnes associées

Chargement

Unités associées

Chargement

Concepts associés (58)

Concepts associés

Chargement

Cours associés (15)

Cours associés

Chargement

Séances de cours associées (27)

Séances de cours associées

Chargement

Meet the Walkers: Accelerating Index Traversals for In-Memory Databases

Babak Falsafi, Boris Robert Grot, Yusuf Onur Koçberber, Javier Picorel Obando

The explosive growth in digital data and its growing role in real-time decision support motivate the design of high-performance database management systems (DBMSs). Meanwhile, slowdown in supply voltage scaling has stymied improvements in core performance and ushered an era of power-limited chips. These developments motivate the design of DBMS accelerators that (a) maximize utility by accelerating the dominant operations, and (b) provide flexibility in the choice of DBMS, data layout, and data types. We study data analytics workloads on contemporary in-memory databases and find hash index lookups to be the largest single contributor to the overall execution time. The critical path in hash index lookups consists of ALU-intensive key hashing followed by pointer chasing through a node list. Based on these observations, we introduce Widx, an on-chip accelerator for database hash index lookups, which achieves both high performance and flexibility by (1) decoupling key hashing from the list traversal, and (2) processing multiple keys in parallel on a set of programmable walker units. Widx reduces design cost and complexity through its tight integration with a conventional core, thus eliminating the need for a dedicated TLB and cache. An evaluation of Widx on a set of modern data analytics workloads (TPC-H, TPC-DS) using full-system simulation shows an average speedup of 3.1x over an aggressive OoO core on bulk hash table operations, while reducing the OoO core energy by 83%.

2013

Chargement

, ,

Navigation in unknown or partially unknown environments remains one of the biggest challenges in today's mobile robotics. Environmental modeling, perception, localization and mapping are all needed for a successful approach. The contribution of this paper resides in the extension of the fingerprint concept (circular list of features around the robot) with uncertainty modeling, in order to improve localization and allow for automatic map building. The uncertainty is defined as the probability of a feature of being present in the environment when the robot perceives it. The whole approach is presented in details and viewed in a topological optic. Experimental results of the perception and localization capabilities with a mobile robot equipped with two 180° laser range finders and an omni-directional camera are reported.

2004

Chargement