Come creare una matrice di dimensioni superiori a numero intero max

Question

Stavo cercando di ottenere tutti i numeri primi 600851475143. Stavo usando Sieve di Eratostene per questo. Questo mi richiede di creare un array booleano di quella dimensione enorme. Pessima idea, puoi esaurire la memoria. Qualsiasi altro modo. Ho provato a utilizzare una stringa, utilizzando ogni indice con valori 0 & 1 per rappresentare true o false. ma il metodo indexOf restituisce anche int.

Successivamente sto usando l'array 2d per il mio problema. Qualunque altro modo migliore per memorizzare un array così grande?

Answer 1

Utilizzare BitSet. È quindi possibile impostare bit di qualsiasi elemento indice. 600851475143 è 2^39, quindi prende solo 39 bit internamente (in realtà in realtà occuperà 64 bit in quanto utilizza a lungo).

È possibile infatti mossa fino 2^63 che è enorme per molti scopi

Answer 2

Ho avuto un problema simile e ho usato un bit impostato (fondamentalmente impostato 1 o 0 per l'offset desiderato in ordine) e raccomando usando EWAHCompressedBitmap essa sarà anche comprimere il bit impostato

EDIT

Come Alan ha detto che il BitSet occuperà 70GB di memoria, ma si può fare un'altra cosa: per avere più bitset (quelli consecutivi in ​​modo da poter calcolare la posizione assoluta) e carica in memoria solo il BitSet di cui hai bisogno in quel momento qualcosa di simile a un carico pigro, in questo caso avrai il controllo della memoria utilizzata.

Answer 3

Il requisito di memoria per i booleans 600851475143 è al massimo di 70 GB. Questo non è fattibile. È necessario utilizzare la compressione come suggerito da Stephan oppure trovare un algoritmo diverso per calcolare i numeri primi.

Answer 4

Non è molto pratico da ricordare per ogni numero se era un numero primo o meno per una quantità così grande (il setaccio è un approccio molto lento per i grandi numeri in generale).

Da questo link hai un'idea di quanti numeri primi ci si possono aspettare più piccoli di X. Per i tuoi 600 miliardi di range puoi aspettarti circa 20 miliardi di numeri primi esistenti all'interno di tale intervallo. Archiviandole a lungo [] richiederebbero circa 160 GB di memoria ... che in misura maggiore rispetto a 70 GB suggeriti per la memorizzazione di un singolo bit per ciascun numero, metà se si escludono anche i numeri pari (2 è l'unico numero pari).

Per un computer desktop 35 GB in memoria possono essere un po 'troppo, ma una buona workstation può avere così tanta RAM. Vorrei provare un array bidimensionale con bit shifting/masking.

Mi aspetto ancora che il codice di setacciamento esegua un tempo di considerevole (alcuni giorni o anni). Ti suggerisco di investigare su metodi di rilevamento dei primati più avanzati del setaccio.

Answer 5

È possibile utilizzare l'API sun.misc.Unsafe interna di HotSpot per allocare un array più grande. I wrote a blogpost how to simulate an array with it Tuttavia, non è un'API Java ufficiale, quindi si qualifica come un hack.