Almacenamiento eficiente de números primos

StackOverflow https://stackoverflow.com/questions/1032427

Pregunta

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 siguiente número primo (suponiendo que sea menor que L).

Dado que L está arreglado, un tamiz de Eratostene para generar la lista está bien. En este momento, uso una matriz booleana empaquetada 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 estáticamente L sin usar más memoria.

¿Hay una estructura de datos que usa menos memoria con propiedades similares? ¿O al menos con el tiempo de búsqueda constante? (los números impares se pueden enumerar hasta que obtengamos un número primo)

(el idioma en el que escribí esto es Factor pero esta pregunta sería la misma en cualquier idioma que tenga arrays de bits empaquetados integrados o fácilmente programables)

¿Fue útil?

Solución

Puede verificar explícitamente más números primos para eliminar la redundancia.

Por el momento, solo hace esto para dos, verificando la divisibilidad entre dos explícitamente y luego almacenando solo para números impares si son primos.

Para 2 y 3 obtienes los restos 0 a 5, de los cuales solo 1 y 5 no son divisibles por dos o tres y pueden dar lugar a un número primo, por lo que estás en 1/3.

Para 2, 3 y 5 obtienes 8 números de 30, lo cual es bueno almacenar en un byte.

Esto se explica con más detalle aquí .

Otros consejos

Una alternativa a los mapas de bits y ruedas empaquetados, pero igualmente eficiente en ciertos contextos, es almacenar las diferencias entre primos consecutivos. Si omite el número 2 como de costumbre, entonces todas las diferencias son pares. Al almacenar la diferencia / 2, puede obtener hasta 2 ^ 40 regiones (justo antes de 1999066711391) utilizando variables de tamaño de byte.

Los números primos hasta 2 ^ 32 requieren solo 194 MByte, en comparación con 256 MByte para un mapa de bits empaquetado solo con probabilidades. Iterar sobre los primos almacenados en delta es mucho más rápido que para el almacenamiento sobre ruedas, que incluye la rueda de módulo 2 conocida como mapa de bits de solo probabilidades.

Para rangos desde 1999066711391 en adelante, se necesita un tamaño de celda más grande o almacenamiento de longitud variable. Este último puede ser extremadamente eficiente incluso si se utilizan esquemas muy simples (por ejemplo, siga agregando hasta que se haya agregado un byte & Lt; 255, como en compresión LZ4 -style), 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 al estilo B-Tree.

La codificación de entropía de las diferencias (codificación Huffmann o aritmética) reduce los requisitos de almacenamiento permanente a un poco menos de la mitad, lo que está cerca del óptimo teórico y mejor que las listas o ruedas comprimidas con los mejores empacadores disponibles.

Si los datos se almacenan sin comprimir, aún son mucho más compactos 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 mapear secciones en la memoria según sea necesario e iterar sobre ellas a una velocidad vertiginosa.

En este momento está tratando 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 primos). Podría mejorar esto tratando 2 y 3 como casos especiales que reconocen que el resto de los números primos están en la forma 6n + 1 o 6n-1 (es decir, para todos los primos p donde p & Gt; 3, p mod 6 = 1 o 5). Esto se puede generalizar aún más; consulte Wikipedia . Para todos los números primos p & Gt; 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)).

Quizás una estructura de datos trie que contiene solo los números primos es lo que está buscando . En lugar de usar caracteres como índices, puede usar los dígitos enteros. Una implementación de esto son Judy-Array s.

A pesar de que no cumplen con su requisito O (1), son extremadamente eficientes en cuanto a memoria para teclas similares (como la mayoría de las partes de los números) y bastante rápido para buscar con una O (m) (m = key- longitud) al máximo.

Si busca un primo en el árbol pregenerado, puede recorrer el árbol hasta que lo encuentre o ya esté en el nodo que está al lado del precedente y el siguiente primo.

Dado que la memoria es tan barata, no creo que pueda hacerlo mucho mejor desde una perspectiva de velocidad que su esquema actual.

Si hay una solución mejor, entonces asumiría que aprovecharía el Teorema de números primos que muestra que a medida que L crece, el límite de

& # 960; (L) / (L / ln (L)) se acerca a 1.

Quizás una solución mejor tendría una solución de empaque adaptativo en una estructura de datos como una lista de omisión .

¿Qué tal algún tipo de tabla hash?

Necesitaría una función hash muy buena (algo así como n mod p, donde p no es múltiplo de ninguno de los q primos más bajos; elija <=> suficientemente alto para minimizar el número de colisiones ).

¿Qué tal un árbol de intervalo? http://www.geeksforgeeks.org/interval-tree/

Puede que no sea O (1) pero es realmente rápido. Como tal vez O (log (p (n))) donde p (n) es el número de primos hasta el número n. De esta forma, la memoria que necesitará será proporcional al número de primos solamente, lo que reducirá en gran medida el costo de la memoria.

Por ejemplo, suponga que encuentra un primo en digamos p1 y luego el siguiente en p2, Inserte el intervalo (p1, p2) y así sucesivamente y cuando realice una búsqueda de cualquier número en ese rango, devolverá este intervalo y puede devolver p2, que sería la respuesta en su caso.

Si puede averiguar cuáles son Mersenne u otros números primos fácilmente representados, usted podría guardar algunos bits utilizando esa representación con una bandera para los números aplicables.

Además, ¿qué tal 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, puede almacenar primos de Mersenne y la diferencia con el último primo de Mersenne.

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top