Loading AI tools
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].
La matrice Judy a été inventée par Douglas Baskins et nommée d'après sa sœur[5].
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].
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.
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
