En informática , una matriz Judy es una estructura de datos que implementa un tipo de matriz asociativa con alto rendimiento y bajo uso de memoria. [1] A diferencia de la mayoría de las otras tiendas de valores-clave , las matrices Judy no usan hash, aprovechan la compresión en sus claves (que pueden ser números enteros o cadenas) y pueden representar de manera eficiente datos dispersos, es decir, pueden tener grandes rangos de índices no asignados sin aumentando considerablemente el uso de la memoria o el tiempo de procesamiento. Están diseñados para seguir siendo eficientes incluso en estructuras con tamaños en el rango de petaelementos, con una escala de rendimiento del orden de O (log n ). [2]En términos generales, las matrices de Judy son árboles de radix de 256 arios altamente optimizados . [3]
Los árboles Judy suelen ser más rápidos que los árboles AVL , los árboles B , las tablas hash y las listas de omisión porque están altamente optimizados para maximizar el uso de la memoria caché de la CPU . Además, no requieren balanceo de árboles y no se utiliza ningún algoritmo hash. [4]
La matriz de Judy fue inventada por Douglas Baskins y lleva el nombre de su hermana. [5]
Beneficios
Asignación de memoria
Las matrices de Judy son dinámicas y pueden crecer o reducirse a medida que se agregan o eliminan elementos de la matriz. La memoria utilizada por las matrices de Judy es casi proporcional al número de elementos de la matriz de Judy.
Velocidad
Las matrices Judy están diseñadas para minimizar la cantidad de costosos rellenos de línea de caché desde la RAM , por lo que el algoritmo contiene mucha lógica compleja para evitar fallas de caché con la mayor frecuencia posible. Debido a estas optimizaciones de caché , las matrices Judy son rápidas, especialmente para conjuntos de datos muy grandes. En conjuntos de datos que son secuenciales o casi secuenciales, las matrices Judy pueden incluso superar a las tablas hash, ya que, a diferencia de las tablas hash, la estructura de árbol interna de las matrices Judy mantiene el orden de las claves. [6]
Inconvenientes
Las matrices de Judy son extremadamente complicadas. Las implementaciones más pequeñas son miles de líneas de código. [5] Además, las matrices Judy están optimizadas para máquinas con líneas de caché de 64 bytes, lo que las hace esencialmente imposibles de transportar sin una reescritura significativa. [6] En la mayoría de las aplicaciones, la posible ventaja de rendimiento es demasiado pequeña para justificar la alta complejidad de la implementación de la estructura de datos.