Como los árboles de bits críticos son un tipo particular de trie (conocidos como intentos de bits sabios, o sus contrapartes más generales pero más lentas, los árboles PATRICIA / radix) representan solo otro conjunto de compensaciones, es útil enumerar estas compensaciones, ya que Destaque cualquier desventaja que podamos encontrar en la práctica (al menos, en relación con otras estructuras de datos).
Complejidad de la clave La fortaleza de la complejidad de los árboles de bits críticos radica en la ramificación a través del conjunto de entrada / espacio clave basado en la diferencia de bits individual; deberíamos esperar que cuanto mayor sea la entropía (desorden) de Shannon entre las teclas en el conjunto de entrada, más efectiva será esta disposición. Lo contrario también es válido.
Por lo tanto, obtenemos la complejidad del peor de los casos cuando las claves son casi idénticas [1]. Esperamos generar árboles profundos en este caso; es decir, espere un costo de O (\ log_2 N) conjuntos de operaciones por consulta. Nuestra complejidad promedio es excelente para conjuntos de claves bien distribuidos, pero no tanto en esta disposición particular.
- ¿Cuál es la diferencia entre el primer turno CS y el segundo turno CS en el Instituto de Tecnología Maharaja Surajmal, GGSIPU?
- ¿Cuáles son algunos sistemas operativos alternativos para PC aparte de Windows?
- Si un informático se despertara en el año 1500, ¿cuánto tiempo les tomaría construir una computadora con estándares modernos?
- ¿Cuáles son las ventajas del desenfoque gaussiano, el desenfoque mediano y el filtro bilateral?
- ¿Hasta qué punto pueden los políticos ser reemplazados por modelos de computadora?
Esto se mitiga algo al restringirnos a árboles de bits críticos de dominio finito (por ejemplo, las claves están restringidas a enteros de ancho fijo). Esto limita nuestra profundidad máxima del árbol al ancho de la clave, ya que ningún par de claves puede diferir en un poco más que el tamaño de la palabra en sí.
Un ejemplo práctico de esta compensación de dominio finito es en Data.IntMap [2] de Haskell usando una variante de un árbol PATRICIA.
Caché Localidad. La siguiente gran ventaja del diseño radica en la representación compacta del espacio del árbol de bits críticos; si una buena tabla hash puede lograr una recuperación de clave O (1) efectiva, ¿no deberíamos esperar que las tablas hash superen a los árboles de bits críticos? ¿Qué pasa con los árboles equilibrados?
Como señaló, la localidad de caché desempeña un papel clave en el tiempo de ejecución resultante, pero resulta ser compleja y depende del procesador (podría argumentar que esto es una desventaja de usar estructuras de datos particularmente especializadas). Aquí hay desgloses de complejidad individuales, donde m representa la longitud de la clave yn representa la profundidad promedio del árbol:
- bit crítico O (m) comparaciones de bit crítico + una comparación final O (m), para un total de O (m).
- tabla hash Un O (m) pasa a través de la función hash, la recuperación promedio de caso O (1), y luego la comparación O (m) del valor clave, para un total de O (m) (ignorando colisiones).
- árbol equilibrado (p. ej. rojo-negro): O (\ log_2 n) comparaciones.
A primera vista, el bit crítico O (m) no parece mucho mejor que O (log n), ya que generalmente se espera que m sea mayor que log_2 n. Una buena forma de pensar en la compensación es considerar cómo la amortización de las operaciones individuales se compara con una posible pérdida de caché. djb aboga por empacar los nodos de árbol de bits críticos de tamaño constante y las hojas de una manera amigable con el caché, proporcionando un rendimiento al menos tan bueno como los árboles binarios equilibrados; es decir, a pesar de tener un mayor número de operaciones, eliminamos la latencia de memoria debido a una mayor proporción de aciertos de caché.
Por lo tanto, en la práctica, la facilidad de almacenar los datos completos de los nodos internos en líneas de caché da como resultado una estructura de datos tan rápida o más rápida, pero mucho más simple que en el caso ideal (árbol equilibrado). Esta es posiblemente la contribución de diseño más importante para el rendimiento del árbol de bits críticos, en relación con otras implementaciones de trie.
Del artículo de Wikipedia sobre los intentos:
Un árbol rojo-negro, por ejemplo, funciona mucho mejor en papel, pero es muy poco amigable con la caché y causa múltiples cañerías y paradas de TLB en las CPU modernas, lo que hace que ese algoritmo esté limitado por la latencia de la memoria en lugar de la velocidad de la CPU. En comparación, un archivo bit a bit rara vez accede a la memoria y, cuando lo hace, solo lo hace para leer, evitando así la sobrecarga de coherencia de caché SMP y, por lo tanto, se está convirtiendo cada vez más en el algoritmo de elección para el código que realiza muchas inserciones y eliminaciones, como los asignadores de memoria (por ejemplo, versiones recientes del famoso asignador de Doug Lea (dlmalloc) y sus descendientes).
Las desventajas
- En tamaños pequeños, los árboles de bits críticos bien diseñados deben ser comparables o más rápidos que los mapas hash / árboles balanceados. Sin embargo, espere que un mapa de hash bien diseñado (por ejemplo, con funciones de hash específicas del dominio) funcione mejor que un árbol de bits críticos en conjuntos de entrada grandes o estructurados, principalmente debido al efecto de predeterminar cuál es el criterio de ramificación ( en comparación con la mayor generalidad que ofrece una función hash arbitraria).
- los árboles de bits críticos pueden ser más lentos que las tablas hash para buscar datos, particularmente cuando el tiempo de acceso aleatorio de su medio de almacenamiento es mayor que la memoria principal (es decir, cuando ya no puede aprovechar la localidad de caché).
- Los conjuntos de entrada estructurados a menudo causan largas cadenas en árboles de bits críticos, lo que mitiga los beneficios de la localidad de caché.
[1] La complejidad para una clave dada de O (1 / DKL (clave || clave promedio)) es la inversa de la divergencia Kullback-Leibler http://en.wikipedia.org/wiki/Kul… (es decir, entropía relativa) entre la entropía de la clave que está buscando y la entropía promedio de la clave en el árbol.
[2] http://hackage.haskell.org/packa…
