Uso de un índice long as ArrayList en java

Question

Estoy escribiendo este programa java para encontrar todos los números primos hasta el número usando el Tamiz de Eratóstenes, pero cuando intento compilar, dice que no puedo usar una var larga como índice de matriz, y espera un int var en su lugar. Pero trabajaré con grandes números, así que no puedo usar int. ¿Qué puedo hacer?

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

No estoy seguro de por qué su código se compilaría para empezar.

Se supone que no debe usar [] en una lista de matriz para acceder a los miembros. Una lista de matrices es simplemente una lista que se almacena internamente en una matriz. Debe usar la operación de obtención de lista (que aún sería O (1)). Escribir numlist [index] significa que tiene una matriz de objetos en numlist. No puede anular la operación [] como en C ++.

Además, un int es de 32 bits en Java. Es poco probable tener una matriz de longitud mayor que 2 ^ 32 (por lo que necesitaría índices largos) y ni siquiera estoy seguro de que la especificación lo permita.

Answer 2

Tenga en cuenta que con un índice int firmado de 32 bits a un largo [], está direccionando 16 GB de RAM.

Si realmente te tomas en serio el éxito con el tamiz, no vas a salirte con la tuya con varias cosas:

• ArrayList de longs en caja
• Usar [] como Uri menciona
• No paginar sistemáticamente al disco

Answer 3

La especificación Java limita las matrices como máximo Integer.MAX_VALUE elementos. Mientras que una List puede contener más elementos (esto es cierto para Collection s en general ), solo puede agregar / obtener / eliminar / configurar utilizando un índice int .

Suponiendo que tiene la memoria para tantos elementos (creo que es muy improbable), podría escribir su propia estructura de datos consistente en "concatenado". matrices Los métodos get () y set () tomarían un índice long y descubrirían la matriz correspondiente y int índice dentro de esa matriz.

Además, sugeriría usar booleanos para representar el estado de cada número, en lugar de almacenar / eliminar cada número explícitamente. Esto sería mejor porque (1) los booleanos ocupan menos espacio que los largos, y (2) el desplazamiento de elementos (como se hace en ArrayList ) durante la eliminación de elementos puede ser costoso.

Answer 4

Al menos el tamaño máximo teórico de las matrices java es Integer.MAX_VALUE. Esto se debe a que el tipo de índice de matriz es de acuerdo con la especificación un int. Sin embargo, en realidad depende de tu memoria.

Entonces, si su algoritmo realmente depende de tener una matriz tan grande, no tendrá suerte con las matrices java.

Como dudo, necesitará todo el espacio en el que podría escribir su propia clase de colección que actúa como una matriz pero no necesita tanta memoria. Colapsaría los totalidades en el espacio de direcciones (por así decirlo). Por supuesto, esto podría cambiar el comportamiento en tiempo de ejecución que espera del algoritmo.

Answer 5

Ha habido propuestas para agregar matrices indexadas largas a Java a través de Project Coin ( http://mail.openjdk.java.net/pipermail/coin-dev/2009-March/000869.html ) aunque no se ha aceptado ni programado nada.

Answer 6

La solución simple: teniendo en cuenta que num nunca es mayor que 100 en su muestra de código, simplemente cambie su tipo a int .

Pero los puntos que otros han mencionado sobre el espacio de direcciones también son buenos puntos.

Answer 7

la Biblioteca jScience tiene un vector grande llamado Float64Vector . Si bien nunca he usado esta clase, podría satisfacer sus necesidades. Sin promesas.

EDITAR: Zach Scrivena señaló en los comentarios que el Float64Vector está dimensionado para ints. Estoy corregido.