Utilizzando un indice long come ArrayList in Java

Question

Sto scrivendo questo programma java per trovare tutti i numeri primi fino a num usando il setaccio di Eratostene, ma quando provo a compilare, dice che non posso usare un var lungo come indice di array e si aspetta un int var al suo posto. Ma lavorerò con numeri grandi, quindi non posso usare int. Cosa posso fare?

import java.util.*;
import java.lang.*;

public class t3{
    public static void main(String[] args){
        long num = 100;

        //declaring list and filling it with numbers
        ArrayList<Long> numlist = new ArrayList<Long>();
        for(long x=2 ; x<num ; x++){
            numlist.add(new Long(x));
        }

        //sieve or eratosthenes
        for(long x=0 ; x<Math.sqrt(num) ; x++){
            for(long y=x+1 ; y<numlist.size() ; y++){
                if(numlist[y]%numlist[x] == 0){
                    numlist.remove(y);
                }
            }
        }

        //print list
        for(Object item : numlist){
            System.out.println((Long)item);
        }
    }
}

Answer 1

Non sono sicuro del motivo per cui il codice dovrebbe essere compilato per iniziare.

Non dovresti usare [] in un elenco di array per accedere ai membri. Un arraylist è semplicemente un elenco archiviato internamente in un array. Devi usare la lista get operazione (che sarebbe comunque O (1)). Scrivere numlist [indice] significa che hai un array di oggetti in numlist. Non è possibile ignorare l'operazione [] come in C ++.

Inoltre, un int è 32 bit in Java. Avere un array di lunghezza maggiore di 2 ^ 32 (quindi avresti bisogno di indici lunghi) è improbabile e non sono nemmeno sicuro che le specifiche lo consentano.

Answer 2

Renditi conto che con un indice int con segno a 32 bit a lungo [] stai indirizzando 16 GB di RAM.

Se sei davvero serio nel raggiungere i numeri primi con il setaccio, non riuscirai a cavartela con diverse cose nel tuo attuale impianto:

• ArrayList of boxed longs
• Uso di [] come menzioni Uri
• Non effettua il paging sistematico su disco

Answer 3

La specifica Java limita al massimo gli array Integer.MAX_VALUE elementi. Mentre un List può contenere più elementi (questo vale per Collection s in generale ), puoi solo aggiungi / ottieni / rimuovi / imposta usando un indice int .

Supponendo che tu abbia la memoria per quel numero di elementi (molto improbabile credo), potresti scrivere la tua struttura di dati composta da "concatenato" array. I metodi get () e set () richiederebbero un indice long e scopriranno l'array e int corrispondenti indice all'interno di tale array.

Inoltre, suggerirei di utilizzare i booleani per rappresentare lo stato di ciascun numero, anziché archiviare / rimuovere esplicitamente ogni numero. Ciò sarebbe meglio perché (1) i booleani occupano meno spazio dei long, e (2) spostare elementi (come fatto in ArrayList ) durante la rimozione degli elementi può essere costoso.

Answer 4

Almeno la dimensione massima teorica degli array Java è Integer.MAX_VALUE. Questo perché il tipo di indice dell'array è secondo le specifiche un int. In realtà, tuttavia, dipende dalla tua memoria.

Quindi, se il tuo algoritmo dipende davvero dall'avere un array così grande, sei sfortunato con gli array java.

Come dubito, avrai bisogno di tutto lo spazio che potresti scrivere per la tua classe di raccolta che si comporta come un array ma non ha bisogno di tanta memoria. Collasserebbe i interi nello spazio degli indirizzi (per così dire). Naturalmente questo potrebbe cambiare il comportamento di runtime che ti aspetti dall'algoritmo.

Answer 5

Ci sono state proposte per aggiungere array con indici lunghi a Java tramite Project Coin ( http://mail.openjdk.java.net/pipermail/coin-dev/2009-March/000869.html ) sebbene nulla sia stato accettato o programmato.

Answer 6

La soluzione semplice: considerando che num non è mai maggiore di 100 nell'esempio di codice, basta cambiarne il tipo in int .

Ma i punti che altri hanno citato sullo spazio degli indirizzi sono anche buoni punti.

Answer 7

la libreria jScience ha un grande vettore chiamato Float64Vector . Anche se non ho mai usato questa classe, potrebbe adattarsi alle tue esigenze. Nessuna promessa.

EDIT: Zach Scrivena ha sottolineato nei commenti che il Float64Vector è dimensionato in pollici. Sono corretto.