Publication
Fast Functional Lists, Hash-Lists, Deques and Variable Length Arrays
Concepts associés (33)
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.
Structure de données persistante
En informatique, une structure de données persistante est une structure de données qui préserve ses versions antérieures lorsqu'elle est modifiée ; une telle structure est immuable, car ses opérations ne la modifient pas en place (de manière visible) mais renvoient au contraire de nouvelles structures. Une structure est partiellement persistante si seule sa version la plus récente peut être modifiée, les autres n'étant accessibles qu'en lecture. La structure est dite totalement persistante si chacune de ses versions peut être lue ou modifiée.
Liste chaînée
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.
Programmation fonctionnelle
La programmation fonctionnelle est un paradigme de programmation de type déclaratif qui considère le calcul en tant qu'évaluation de fonctions mathématiques. Comme le changement d'état et la mutation des données ne peuvent pas être représentés par des évaluations de fonctions la programmation fonctionnelle ne les admet pas, au contraire elle met en avant l'application des fonctions, contrairement au modèle de programmation impérative qui met en avant les changements d'état.
Vecteur (structure de données)
En informatique, un vecteur désigne un conteneur d'éléments ordonnés et accessibles par des indices, dont la taille est dynamique : elle est mise à jour automatiquement lors d'ajouts ou de suppressions d'éléments. On retrouve les vecteurs dans de nombreux langages de programmation, notamment le C++ et le Java. Ils sont alors inclus dans des bibliothèques et l'utilisateur n'a pas besoin d'en programmer un. En langage objet, la classe vecteur est généralement polymorphe, c'est-à-dire qu'il est possible de l'utiliser avec n'importe quel type d'objet.
Array (data type)
In computer science, array is a data type that represents a collection of elements (values or variables), each selected by one or more indices (identifying keys) that can be computed at run time during program execution. Such a collection is usually called an array variable or array value. By analogy with the mathematical concepts vector and matrix, array types with one and two indices are often called vector type and matrix type, respectively. More generally, a multidimensional array type can be called a tensor type, by analogy with the physical concept, tensor.
Fonction de hachage
Quand il s'agit de mettre dans un tableau de taille raisonnable (typiquement résidant dans la mémoire principale de l'ordinateur) un ensemble de données de taille variable et arbitraire, on utilise une fonction de hachage pour attribuer à ces données des indices de ce tableau. Par conséquent, une fonction de hachage est une fonction qui associe des valeurs de taille fixe à des données de taille quelconque. Les valeurs renvoyées par une fonction de hachage sont appelées valeurs de hachage, codes de hachage, résumés, signatures ou simplement hachages.
Lisp
Lisp est la plus ancienne famille de langages de programmation à la fois impératifs et fonctionnels. Développé initialement en tant que modèle pratique pour représenter des programmes (par contraste avec la notion théorique de machine de Turing), il est devenu, dans les années 1970 et 80, un des langages de choix (comme le langage Prolog) pour la recherche en intelligence artificielle. Les langages Lisp sont aujourd'hui utilisés dans de nombreux domaines, de la programmation Web à la finance, et dans certains cursus de formation en informatique.
Common Lisp
Common Lisp (en abrégé CL) est une spécification du langage Lisp standardisée par l'ANSI. Common Lisp est un dialecte de Lisp standardisé par l'ANSI X3.226-1994. Développé pour standardiser les variantes divergentes de Lisp qui l'ont précédé, ce n'est pas une implémentation mais une spécification à laquelle les implémentations Lisp essayent de se conformer. Il est fréquemment abrégé en CL. Common Lisp est un langage de programmation à usage général, a contrario de dialectes de Lisp comme Emacs Lisp et AutoLisp, qui sont des langages d'extension embarqués dans des produits particuliers.
Table de hachage
Une table de hachage est, en informatique, une structure de données qui permet une association clé–valeur, c'est-à-dire une implémentation du type abstrait tableau associatif. Son but principal est de permettre de retrouver une clé donnée très rapidement, en la cherchant à un emplacement de la table correspondant au résultat d'une fonction de hachage calculée en O(1). Cela constitue un gain de temps très important pour les grosses tables, lors d'une recherche ou d'un besoin d'accès aux données en utilisant la clé définie.