Usando um longo como índice ArrayList em Java

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

  •  19-08-2019
  •  | 
  •  

Pergunta

Eu estou escrevendo este programa java para encontrar todos os números primos até num usando o Crivo de Eratóstenes, mas quando eu tento compilar, ele diz que eu não posso usar um longo var como um índice de matriz, e espera uma var int em seu lugar. Mas eu vou estar trabalhando com grandes números, então não posso usar int. O que posso fazer? 

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);
        }
    }
}
Foi útil?

Solução

Eu não tenho certeza por que o código seria compilar para começar.

Você não está suposto uso [] em uma lista de matriz para acessar membros. Um ArrayList é simplesmente uma lista que é armazenada internamente em uma matriz. Você tem que usar a operação de lista get (que ainda seria O (1)). Escrevendo numlist [índice] significa que você tem uma matriz de objetos em numlist. Você não pode substituir a operação [] como em C ++.

Além disso, um int é de 32 bits em Java. Ter uma variedade de maior comprimento do que 2 ^ 32 (assim você precisaria índices de comprimento) é improvável e não estou mesmo certo a especificação permite.

Outras dicas

perceber que com um 32-bit índice int assinado com uma 16GB long [] você está dirigindo de RAM.

Se você for realmente sério sobre a obtenção de grandes números primos com a peneira, você não vai fugir com várias coisas em sua impl atual:

  • ArrayList de anseia caixas
  • Usar [] como Uri menciona
  • Não sistematicamente paginação para o disco

O Java especificação limita matrizes para, no máximo, elementos Integer.MAX_VALUE. Enquanto um List pode conter mais elementos (isto é verdade para Collections em geral), você só pode add / obter / remover / definir -los usando um índice int.

Assumindo que você tem a memória para que muitos elementos (muito improvável que eu acho), você pode escrever sua própria estrutura de dados consiste de matrizes "concatenadas". Os métodos e get() set() levaria um índice long e figura para fora da matriz e int índice correspondente dentro dessa gama.

Além disso, gostaria de sugerir o uso booleans para representar o estado de cada número, em vez de armazenar / remoção de cada número explicitamente. Isso seria melhor porque (1) booleans levar menos espaço do que anseia, e (2) deslocando elementos (como feito em ArrayList) durante a remoção do elemento pode ser caro.

Pelo menos o tamanho máximo teórico de matrizes Java é Integer.MAX_VALUE. Isto é por causa do tipo de índice de matriz é de acordo com a especificação um int. Na realidade, depende de sua memória embora.

Portanto, se seu algoritmo realmente depende de ter uma grande variedade tal, você está fora de sorte com arrays Java.

Como eu duvido que você vai precisar de todo o espaço que você pode escrever sua própria classe de coleção que age como uma matriz, mas não precisa de tanta memória. Ele entraria em colapso as totalidades no espaço de endereço (por assim dizer). Claro que isso pode alterar o comportamento de tempo de execução que você está esperando desde o algoritmo.

Houve propostas para adicionar matrizes longo indexados para Java através do Projeto Coin ( http://mail.openjdk.java.net/pipermail/coin-dev/2009-March/000869.html ) embora nada tenha sido aceite ou agendadas.

A solução simples: considerando que num nunca é maior do que 100 em sua amostra de código, basta alterar seu tipo de int.

Mas os pontos outros têm mencionados sobre o espaço de endereço também são bons pontos.

Biblioteca jScience tem uma grande vetor chamado Float64Vector . Enquanto eu nunca usei essa classe que poderia atender às suas necessidades. Sem promessas.

EDIT: Zach Scrivena apontou nos comentários que a Float64Vector está dimensionado para ints. Eu estou corrigido.

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top