math - sacar - Almacenamiento eficiente de números primos
numeros primos del 1 al 100 (9)
Para una biblioteca, necesito almacenar los primeros números primos hasta un límite L. Esta colección debe tener un tiempo de búsqueda O (1) (para verificar si un número es primo o no) y debe ser fácil, dado un número, para encontrar el próximo número primo (suponiendo que es más pequeño que L).
Dado que L es fijo, un tamiz Eratostene para generar la lista está bien. En este momento, utilizo una matriz booleana compacta para almacenar la lista, que contiene solo entradas para números impares entre 3 y L (inclusive). Esto toma (L-2) / 2 bits de memoria. Me gustaría poder aumentar L de forma estática sin usar más memoria.
¿Hay una estructura de datos que usa menos memoria con propiedades similares? ¿O con al menos el tiempo de búsqueda constante? (los números impares pueden ser enumerados hasta que obtengamos un primo)
(El lenguaje en el que escribí esto es Factor pero esta pregunta sería la misma en cualquier idioma que tenga arreglos de bits empaquetados o fácilmente programables)
¿Qué tal un árbol de intervalos? http://www.geeksforgeeks.org/interval-tree/
Puede que no sea O (1) pero es realmente rápido. Como quizás O (log (p (n))) donde p (n) es el número de números primos hasta el número n. De esta manera, la memoria que necesitará estará en proporción con el número de primos solamente, reduciendo en gran medida el costo de la memoria.
Por ejemplo, suponga que encuentra un primo en decir p1 y luego el siguiente en p2, Insertar intervalo (p1, p2) y así sucesivamente y cuando ejecuta una búsqueda de cualquier número en ese rango, devolverá este intervalo y puede devolver p2 cuál sería la respuesta en tu caso.
¿Qué tal un tipo de tabla hash?
Necesitaría una muy buena función hash (algo así como n mod p , donde p no es un múltiplo de ninguno de los q primos más bajos - elija q suficientemente alto para minimizar el número de colisiones).
Consulte el tutorial de Topcoder sobre números primos: http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=math_for_topcoders
Dado que la memoria es tan barata, no creo que puedas hacer mucho mejor desde una perspectiva de velocidad que tu esquema actual.
Si hay una solución mejor, entonces asumiría que se aprovecharía del Teorema del Número Principal que muestra que a medida que L se hace más grande, el límite de
π (L) / (L / ln (L)) se aproxima a 1.
Tal vez una solución mejor tendría una solución de empaque adaptable en una estructura de datos similar a una lista de omisiones .
En este momento está tratando a 2 como un caso especial y luego tiene una matriz donde cada número impar se asigna a un elemento en la matriz (con algunos números impares siendo primos). Podría mejorar esto tratando a los casos 2 y 3 como casos especiales que reconocen que el resto de los números primos tienen la forma 6n + 1 o 6n-1 (esto es para todos los primos p donde p> 3, p mod 6 = 1 o 5). Esto se puede generalizar aún más - ver Wikipedia . Para todos los primes p> 5, p mod 30 = 1, 7, 11, 13, 17, 19, 23 o 29. Puede continuar con esto y reducir la memoria necesaria a expensas del tiempo de procesamiento (aunque seguirá siendo O (1), solo un O más lento (1)).
Puede verificar explícitamente más números primos para eliminar la redundancia.
En este momento, solo hace esto para dos, comprobando la divisibilidad por dos explícitamente y luego almacenando solo para los números impares, ya sean primos.
Para 2 y 3 obtienes los residuos 0 a 5, de los cuales solo 1 y 5 no son divisibles por dos o tres y pueden conducir a un número primo, por lo que estás abajo a 1/3.
Para 2, 3 y 5 obtienes 8 números de 30, lo que es bueno almacenar en un byte.
Esto se explica con más detalle here .
Si puede averiguar cuáles son Mersenne u otros números primos fácilmente representados, puede guardar algunos bits usando esa representación con un indicador para los números aplicables.
Además, ¿qué hay de almacenar los números como la diferencia del número anterior? Entonces el tamaño no debería aumentar tan rápido (pero la búsqueda sería lenta). Combinando con el enfoque anterior, podría almacenar números primos de Mersenne y la diferencia del último primo de Mersenne.
Tal vez una trie datos trie que contiene solo los números primos es lo que estás buscando. En lugar de usar caracteres como índices, puede usar los dígitos enteros. Una implementación de esto es Judy-Array s.
A pesar de que no cumplen con su requisito O (1), son extremadamente eficientes en memoria para teclas similares (como la mayoría de las partes de los números) y bastante rápidas para buscar con O (m) (m = longitud de la tecla) en máximo.
Si busca un primo en el árbol generado previamente, puede caminar por el árbol hasta que lo encuentre o ya se encuentra en el nodo que está al lado del primado anterior y siguiente.
Una alternativa a los mapas de bits empaquetados y las ruedas, pero igualmente eficiente en ciertos contextos, es almacenar las diferencias entre los primos consecutivos. Si omite el número 2 como de costumbre, todas las diferencias son pares. Al almacenar la diferencia / 2 puede obtener hasta 2 ^ 40 regiones (justo antes de 1999066711391) usando variables de tamaño byte.
Los primos hasta 2 ^ 32 requieren solo 194 MByte, en comparación con 256 MByte para un mapa de bits embalado solo con probabilidades. La iteración sobre primos almacenados en delta es mucho más rápida que para el almacenamiento con ruedas, que incluye la rueda de módulo 2 conocida como mapa de bits de probabilidades únicas.
Para rangos de 1999066711391 en adelante, se necesita un tamaño de celda mayor o un almacenamiento de longitud variable. Este último puede ser extremadamente eficiente incluso si se utilizan esquemas muy simples (por ejemplo, seguir agregando hasta que se haya agregado un byte <255, como en la compresión de estilo LZ4 ), debido a la frecuencia extremadamente baja de espacios de más de 510/2.
Por razones de eficiencia, es mejor dividir el rango en secciones (páginas) y administrarlas con estilo B-Tree.
La codificación de entropía de las diferencias (codificación Huffmann o aritmética) reduce los requisitos de almacenamiento permanentes a un poco menos de la mitad, lo que se acerca al óptimo teórico y es mejor que las listas o ruedas comprimidas utilizando los mejores empaquetadores disponibles.
Si los datos se almacenan sin comprimir, entonces es mucho más compacto que los archivos de números binarios o textuales, en un orden de magnitud o más. Con un índice de estilo B-Tree en su lugar, es fácil simplemente mapear secciones en la memoria según sea necesario e iterar sobre ellas a una velocidad vertiginosa.