L'iterazione di una struttura di dati con 51 milioni di numeri primi in fretta

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

  •  22-08-2019
  •  | 
  •  

Domanda

Qual è il miglior struttura di dati (in Java) per l'attività di carico 51 milioni di numeri primi e poi iterazione su di loro?

Ho bisogno di sapere, per esempio, i numeri primi che sono tra il miliardo e che lo stesso numero meno 100000.

È stato utile?

Soluzione

Una ricerca binaria non sta per essere meraviglioso per questi dati, dal momento che la prima metà dei numeri primi stanno per essere più vicini gli uni agli altri che l'ultimo metà di loro.

Potreste essere in grado di migliorare la vostra ricerca conoscendo quanti numeri primi ci sono sotto x . Forse inclinare il taglio utilizzando il ravvicinamento menzionato nel collegamento.

Il mio primo tentativo sarebbe questo. Mi piacerebbe avere due array.

  1. un array di tutti i numeri primi.
  2. Una matrice che mi dice dove nel primo array il primo numero primo di sopra di 1000 * n era. Quindi, se volevo trovare il primo numero primo con un valore di 5000 o più, mi piacerebbe guardare secondArray [5000 / 1000-1].

mi piacerebbe avere una posizione di massima con array di 2 prima di fare qualsiasi cosa con 1 campo.

Altri suggerimenti

Perché memorizzarli in una mappa a tutti? E 'questo in modo da avere di ricerca veloce per vedere se un dato numero è un numero primo? Che avrebbe senso e vi darà accesso rapido. Il costo di aggiunta loro può essere attenuato (ma non eliminato) impostando la capacità iniziale della TreeMap. Questo sarà ancora sostenere costi albero di riequilibrio tuttavia.

Un memorizzazione alternativo potrebbe essere semplicemente per ordinare e metterli in un array. Questo vi darà (log n) ricerca O con una ricerca di bisezione, ma vi farà ottenere gamme banale. È possibile utilizzare Arrays.binarySearch () .

Dato che è possibile precalculate tutti i numeri primi, e (dal Teorema dei Numeri Primi che Nosredna e altri hanno detto) si sa di quante non ci sarà, è possibile utilizzare una struttura fissa (int []) e una volta in costo di inserzione order non dovrebbe essere una preoccupazione.

La ricerca binaria (come Arrays.binarySearch ()) sarà così veloce che probabilmente non c'è bisogno di prendere in considerazione le ottimizzazioni. Ma, si potrebbe anche utilizzare le previsioni del Teorema dei Numeri Primi di circa dove il primo ennesimo è quello di trovare i punti finali di gamme ancora più velocemente.

Giusto per essere diverso, io sottolineare che in questa scala si potrebbe anche memorizzare i numeri primi come bit impostati in un grande campo di bit, dove se N è primo, il bit # N è impostato su 1. La struttura sarebbe in realtà essere inferiore al int [] - 1 miliardo di bit è ~ 110MiB, mentre 51 milioni di int è ~ 200MiB. Vedere la BitSet di classe. Dal momento che nessun anche gli indici sono primi, si potrebbe sottoclasse o avvolgere BitSet per dare la risposta banale per tutti, anche gli indici e mezzo / valori doppi a seconda dei casi, prima di passare da / per BitSet, e quindi memorizzare l'intero campo in ~ 55MiB.

La prova di un primo con una tale struttura è O (1), ma iterare su tutti i bit impostati (numeri primi) dipende dalla densità dei numeri primi della gamma scelte come target. E 'ancora dovrebbe essere abbastanza veloce però.

A me sembra che un semplice array (o ArrayList dal momento che è più facile lavorare con) andrebbe bene. L'aggiunta di elementi è O (1) ed è possibile ottenere tutti i numeri primi tra X e Y facendo una ricerca binaria per il primo numero primo> = x (vedi http://java.sun.com/j2se/1.5.0 /docs/api/java/util/Collections.html#binarySearch%28java.util.List,%20T%29 ), e poi basta scorrere l'elenco fino ad arrivare ad un primo> y.

(mi rendo conto Cletus mi hanno picchiato ad esso, ma si spera dettaglio in più è di qualche utilità.)

Il primo è di circa n'th p(n) ~ n ln(n), vale a dire 

p(51E6) ~ 905114146 < 2147483647 = Integer.MAX_VALUE

Questo significa che il modo più efficace per memorizzare i primi 51 milioni di numeri primi è un int[].

Dipende esattamente l'equilibrio di operazioni, e il loro utilizzo. Un semplice array ordinato sarà meglio per memorizzare i numeri primi.

Ora, se le prestazioni sono davvero ad un premio e il costo della memoria è insignificante allora si potrebbe aumentare questo con un indice di indici. per es. 

int MAX_NUM_PRIMES =    ...   // the maximum number of primes to be stored
int MAX_PRIME = ....          // the largest prime to be stored
int primes[MAX_NUM_PRIMES]    // array of prime numbers, sorted
int nextPrime[MAX_PRIME]      // nextPrime[i] is the index of the next prime >= i

where nextPrime[i] is the starting point in the array primes for the first prime > i.

then, to iterate over e.g.   2000 primes from   3456, you would do

int j = nextPrime[3456]
for (i = j; i < j + 2000; i++) {
    int x = prime[i];
    ... do whatever with x ...
}
  

Ho bisogno di sapere, per esempio, i numeri primi che sono tra il miliardo e che lo stesso numero meno 100000.

Poi costruire un setaccio per esattamente quei numeri a cui è interessato. Computing tutti i primi sotto è uno spreco, se non volete sapere esattamente quanti numeri primi ci sono al di sotto 999.900.000.

Una struttura di buoni dati per questo formato di numeri è un insieme di bit. Poiché circa uno su 21 numeri è un numero primo, che richiede meno memoria rispetto memorizzare i numeri in modo esplicito, ed è abbastanza veloce per iterare attraverso gamme.

Modifica:. Per essere concreti, sul mio portatile in Java setacciando tutta la gamma prende un po 'più di un minuto, setacciando gli ultimi 100000 circa 30 millisecondi

Se si desidera che la migliore struttura dei dati per trovare rapidamente il numero di primi tra xey (come nel tuo esempio) che si desidera un Binary indicizzato Albero .

C'è una buona descrizione qui .

questa applet java sembra abbastanza veloce: Tabella dei numeri primi 1-1 000 000 000 000 http://www.walter-fendt.de/m14e/primes.htm (nessuna fonte, però, ma si potrebbe provare l'autore)

Una serie di numeri probabilmente fare bene:)

Il problema potrebbe generare la matrice? In tal caso, creare un oggetto contenente la matrice e popolarla (generando loro o la lettura da un elenco di numeri primi). Al termine, serializzare su disco in modo che il programma può leggere il flusso binario veloce in futuro per caricare la matrice.

Vedere questa domanda per le variazioni su come generare la matrice primaria: numero Primo calcolo divertimento

Per la vostra esigenza, è necessario utilizzare il segmentato Crivello di Eratostene. non richiede una grande quantità di memoria ..

Trova tutti i numeri primi fino alla radice quadrata di 999900000. (~ 31.621) che possono essere facilmente memorizzati in un array.

Ora, effettuare la procedura di Sieve-ing su un array 100000 di lunghezza. con questi numeri primi.

abbastanza efficiente, per un gran numero.

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