Matrice Judy
En informatique, une matrice Judy est une structure de données mettant en œuvre un type de tableau associatif offrant de hautes performances et une faible utilisation de la mémoire[1]. Contrairement à la plupart des autres bases de données clé-valeur, les matrices Judy n'utilisent pas de hachage, exploitent la compression sur leurs clés (qui peuvent être des entiers ou des chaînes de caractères) et peuvent représenter efficacement des données éparses, c'est-à-dire qu'ils peuvent avoir de grandes plages d'indices non attribués sans augmenter considérablement l'utilisation de la mémoire ou le temps de traitement. Ils sont conçus pour rester efficaces même sur des structures dont la taille est de l'ordre du péta-élément, avec des performances de l'ordre de O(log n)[2]. Grossièrement, les matrices Judy sont des arbres radix 256-ary hautement optimisés[3].
Les arbres Judy sont généralement plus rapides que les arbres AVL, les arbres B, les tables de hachage et les skip list car ils sont hautement optimisés pour maximiser l'utilisation du cache CPU. De plus, ils ne nécessitent aucun équilibrage d'arbre et aucun algorithme de hachage n'est utilisé[4].
Histoire
La matrice Judy a été inventée par Douglas Baskins et nommée d'après sa sœur[5].
Avantages
Allocation de mémoire
Les matrices Judy sont dynamiques et peuvent croître ou décroître à mesure que des éléments sont ajoutés ou retirés du tableau. La mémoire utilisée par les matrices Judy est presque proportionnelle au nombre d'éléments de la matrice.
Vitesse
Les matrices Judy sont conçues pour minimiser le nombre de remplissages coûteux de lignes de cache à partir de la RAM, et l'algorithme contient donc une logique très complexe pour éviter les manques de cache aussi souvent que possible. Grâce à ces optimisations du cache, les matrices Judy sont rapides, en particulier pour les très grands ensembles de données. Sur les ensembles de données séquentielles ou presque séquentielles, les matrices Judy peuvent même surpasser les tables de hachage car, contrairement à ces dernières, la structure arborescente interne des matrices Judy maintient l'ordre des clés[6].
Désavantages
Les matrices Judy sont extrêmement compliquées. Les plus petites implémentations représentent des milliers de lignes de code[5]. En outre, les matrices Judy sont optimisées pour les machines dotées de lignes de cache de 64 octets, ce qui les rend essentiellement intransportables sans une réécriture importante[6]. Dans la plupart des applications, l'avantage possible en termes de performances est trop faible pour justifier la grande complexité de l'implémentation de la structure de données.
Références
- (en) « Brevet de Robert Gobeille et Douglas Baskins » (consulté le )
- « Debian -- Détails du paquet libjudy-dev dans buster », sur Debian (consulté le )
- (en) Alan Silverstein, Judy IV Shop Manual, , 81 p. (lire en ligne)
- (en) « Une description en 10 minutes du fonctionnement des matrices Judy et des raisons pour lesquelles elles sont si rapides »
- « Judy Arrays Web Page », sur sourceforge.net (consulté le ).
- (en) « Comparaison des performances de Judy et des tables de hachage » (consulté le )
Voir également
Articles connexes
- Arbre radix
- Matrice de hachage d'essai cartographié