Memorizzazione efficiente dei numeri primi

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

Domanda

Per una libreria, devo memorizzare i numeri dei primi primi fino a un limite L. Questa raccolta deve avere un tempo di ricerca O (1) (per verificare se un numero è primo o no) e deve essere facile, dato un numero, per trovare il numero primo successivo (supponendo che sia più piccolo di L).

Dato che L è fisso, un setaccio Eratostene per generare l'elenco va bene. In questo momento, uso un array booleano compresso per memorizzare l'elenco, che contiene solo voci per numeri dispari tra 3 e L (incluso). Questo richiede (L-2) / 2 bit di memoria. Vorrei poter aumentare staticamente L senza usare più memoria.

Esiste una struttura di dati che utilizza meno memoria con proprietà simili? O con almeno il tempo di ricerca costante? (i numeri dispari possono quindi essere elencati fino a quando non si ottiene un numero primo)

(la lingua in cui ho scritto questo è Factor ma questa domanda sarebbe la stessa in qualsiasi lingua che abbia array di bit integrati o facilmente programmabili)

È stato utile?

Soluzione

È possibile controllare esplicitamente più numeri primi per rimuovere la ridondanza.

Al momento lo fai solo per due, verificando esplicitamente la divisibilità per due e quindi memorizzando solo per i numeri dispari se sono primi.

Per 2 e 3 ottieni i resti da 0 a 5, di cui solo 1 e 5 non sono divisibili per due o tre e possono portare a un numero primo, quindi scendi a 1/3.

Per 2, 3 e 5 ottieni 8 numeri su 30, che è bello da memorizzare in un byte.

Questo è spiegato in modo più dettagliato qui .

Altri suggerimenti

Un'alternativa alle bitmap e alle ruote impacchettate - ma ugualmente efficiente in determinati contesti - è la memorizzazione delle differenze tra numeri primi consecutivi. Se lasci il numero 2 come al solito, allora tutte le differenze sono pari. Memorizzando la differenza / 2 è possibile ottenere fino a 2 ^ 40 regioni (poco prima di 1999066711391) utilizzando variabili di dimensioni in byte.

I primi 2 ^ 32 richiedono solo 194 MByte, rispetto ai 256 MByte per una bitmap impacchettata solo per le probabilità. L'iterazione sui numeri primi memorizzati nel delta è molto più veloce rispetto alla memorizzazione su ruote, che include la ruota modulo-2 nota come bitmap solo a probabilità.

Per intervalli che vanno da 1999066711391 in poi, sono necessarie celle di dimensioni maggiori o memoria a lunghezza variabile. Quest'ultimo può essere estremamente efficiente anche se vengono utilizzati schemi molto semplici (ad es. Continuare ad aggiungere fino a quando è stato aggiunto un byte & Lt; 255, come in compressione in stile LZ4 ), a causa della frequenza estremamente bassa di gap più lunghi di 510/2.

Per motivi di efficienza, è meglio dividere l'intervallo in sezioni (pagine) e gestirle in stile B-Tree.

La codifica entropica delle differenze (Huffmann o codifica aritmetica) riduce i requisiti di stoccaggio permanente a un po 'meno della metà, il che è vicino all'ottimale teorico e migliore delle liste o delle ruote compresse usando i migliori packer disponibili.

Se i dati sono archiviati non compressi, sono ancora molto più compatti dei file di numeri binari o testuali, di un ordine di grandezza o più. Con un indice in stile B-Tree in atto, è facile mappare semplicemente le sezioni in memoria secondo necessità e scorrere su di esse a una velocità incredibile.

Al momento stai trattando 2 come caso speciale e quindi hai un array in cui ogni numero dispari è mappato su un elemento dell'array (con alcuni numeri dispari che sono primi). Puoi migliorare questo trattando 2 e 3 come casi speciali riconoscendo che il resto dei numeri primi sono nella forma 6n + 1 o 6n-1 (vale a dire per tutti i numeri primi p dove p & Gt; 3, p mod 6 = 1 o 5). Questo può essere ulteriormente generalizzato - vedi Wikipedia . Per tutti i numeri primi p & Gt; 5, p mod 30 = 1, 7, 11, 13, 17, 19, 23 o 29. Potresti continuare con questo e ridurre la memoria necessaria a spese del tempo di elaborazione (anche se sarà comunque O (1), solo una O più lenta (1)).

Forse una struttura dati trie che contiene solo i numeri primi è ciò che stai cercando . Invece di utilizzare i caratteri come indici, è possibile utilizzare le cifre intere. Un'implementazione di questo sono Judy-Array s.

Inoltre, non soddisfano i requisiti O (1), sono estremamente efficienti in termini di memoria per chiavi simili (come la maggior parte delle parti dei numeri) e abbastanza veloci da cercare con una O (m) (m = chiave- lunghezza) al massimo.

Se cerchi un numero primo nell'albero pre-generato, puoi camminare sull'albero fino a quando non lo trovi o non sei già nel nodo che si trova accanto al numero precedente e successivo.

Dato che la memoria è così economica, non penso che tu possa fare molto meglio dal punto di vista della velocità rispetto al tuo schema esistente.

Se esiste una soluzione migliore, suppongo che trarrebbe vantaggio dal Teorema del numero primo questo dimostra che man mano che L cresce, il limite di

& # 960; (L) / (L / ln (L)) si avvicina a 1.

Forse una soluzione migliore avrebbe una soluzione di imballaggio adattivo in una struttura di dati simile a una skip list .

Che ne dici di una specie di tabella hash?

Avresti bisogno di un'ottima funzione hash (qualcosa come n mod p, dove p non è un multiplo di nessuno dei q numeri primi più bassi - scegli <=> sufficientemente alto per ridurre al minimo il numero di collisioni ).

Che ne dici di un albero a intervalli? http://www.geeksforgeeks.org/interval-tree/

Potrebbe non essere O (1) ma è davvero veloce. Come forse O (log (p (n))) dove p (n) è il numero di numeri primi fino al numero n. In questo modo la memoria di cui avrai bisogno sarà proporzionale al numero di numeri primi, riducendo notevolmente il costo della memoria.

Ad esempio supponiamo di trovare un numero primo in dire p1 e poi il successivo in p2, Inserisci intervallo (p1, p2) e così via e quando esegui una ricerca per qualsiasi numero in quell'intervallo restituirà questo intervallo e puoi restituire p2 che sarebbe la risposta nel tuo caso.

Se riesci a capire quali sono Mersenne o altri numeri primi facilmente rappresentati, tu potrebbe essere in grado di salvare alcuni bit utilizzando quella rappresentazione con un flag per i numeri applicabili.

Inoltre, che ne dici di memorizzare i numeri come differenza rispetto al numero precedente? Quindi la dimensione non dovrebbe aumentare abbastanza velocemente (ma la ricerca sarebbe lenta). Combinando con l'approccio sopra, è possibile memorizzare i numeri primi di Mersenne e la differenza rispetto all'ultimo numero di Mersenne.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top