algorithm - racionales - propiedades de los numeros enteros
¿Representando conjuntos enteros dispersos? (4)
Si desea que la estructura sea más pequeña que el conjunto de datos, probablemente debería considerar algún tipo de disposición de árbol. Realice cada nivel de 4 maneras en que la clave del árbol se separa de 2 bits comenzando en el extremo superior y puede compactarse bastante bien (si los punteros tienen algún grado de localidad espacial). El truco sería codificarlo lo suficientemente compacto (índices en matrices de nodos, un árbol mapeado en una matriz?).
¿Cuál es una buena forma de representar un conjunto disperso de enteros (realmente direcciones de memoria C) de forma compacta y rápida? Ya sé sobre las cosas obvias como los vectores de bits y la codificación de longitud de ejecución. pero quiero algo mucho más compacto que una palabra por conjunto de elementos. Necesito agregar y eliminar elementos y probar la membresía. No necesito otras operaciones de conjunto, como la unión.
Leí sobre una de esas bibliotecas hace muchos años, pero desde entonces he olvidado su nombre. Creo que fue lanzado como fuente abierta por HP y tenía un nombre de mujer.
Si todo lo que necesita es inserción, eliminación y prueba de membresía, entonces una tabla hash le conviene muy bien. Puede encontrar algunas buenas funciones hash para mezclar enteros de 32 bits aquí .
Te estás refiriendo a una matriz Judy. Fue un proyecto de HP. Creo que se usan en ruby y están disponibles en c. Estructura de datos muy interesante. Haciendo uso del hecho de que las asignaciones están (al menos) alineadas con palabras, teniendo estructuras separadas para rangos densos y dispersos.
Una estructura de datos muy compacta sería un filtro de floración, tal vez un filtro de recuento de florecimiento para admitir eliminaciones.
http://en.wikipedia.org/wiki/Bloom_filter
El filtro Bloom, concebido por Burton H. Bloom en 1970, es una estructura de datos probabilísticos eficientes en el uso del espacio que se usa para probar si un elemento es miembro de un conjunto. Los falsos positivos son posibles, pero los falsos negativos no lo son. Se pueden agregar elementos al conjunto, pero no se eliminan (aunque esto se puede abordar con un filtro de conteo)