Utilisation d'un index long as ArrayList en Java

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

  •  19-08-2019
  •  | 
  •  

Question

J'écris ce programme java pour trouver tous les nombres premiers jusqu'à num en utilisant le tamis d'Eratosthène, mais lorsque j'essaie de compiler, il est indiqué que je ne peux pas utiliser une variable longue comme index de tableau. int var à sa place. Mais je vais travailler avec de grands nombres, donc je ne peux pas utiliser int. Que puis-je faire? 

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);
        }
    }
}
Était-ce utile?

La solution

Je ne suis pas sûr de savoir pourquoi votre code serait compilé pour commencer.

Vous n'êtes pas censé utiliser [] dans une liste de tableaux pour accéder aux membres. Un arraylist est simplement une liste stockée en interne dans un tableau. Vous devez utiliser l'opération list get (qui serait toujours O (1)). Ecrire numlist [index] signifie que vous avez un tableau d'objets dans numlist. Vous ne pouvez pas remplacer l'opération [] comme en C ++.

De plus, un int est 32 bits en Java. Il est peu probable qu'un tableau de longueur supérieure à 2 ^ 32 (vous auriez donc besoin d'indices longs) et je ne suis même pas sûr que la spécification le permette.

Autres conseils

Sachez qu’avec un index int signé 32 bits à un long [], vous adressez 16 Go de RAM.

Si vous êtes vraiment sérieux au sujet de l'obtention de gros nombres premiers avec le tamis, vous n'allez pas vous en tirer avec plusieurs choses dans votre système actuel:

  • ArrayList des longs en boîte
  • L'utilisation de [] comme Uri mentionne
  • Pas de pagination systématique sur le disque

La spécification Java limite les tableaux à au plus Integer.MAX_VALUE éléments. Bien qu'une Liste puisse contenir more elements (cela est vrai pour Collection s en général ), vous pouvez uniquement add / get / remove / set à l'aide d'un index int .

En supposant que vous ayez assez de mémoire pour de nombreux éléments (très peu probable, je pense), vous pouvez écrire votre propre structure de données composée de "concaténée". tableaux. Les méthodes get () et set () prennent un index long et déterminent le tableau correspondant et int . index dans ce tableau.

De plus, je suggérerais d'utiliser des booléens pour représenter l'état de chaque nombre, au lieu de stocker / supprimer explicitement chaque nombre. Ce serait mieux parce que (1) les booléens prennent moins de place que les longs et (2) les éléments de décalage (comme dans ArrayList ) lors de la suppression d'éléments peuvent être coûteux.

Au moins la taille maximale théorique des matrices java est Integer.MAX_VALUE. En effet, le type de l'index de tableau est selon les spécifications un int. En réalité, cela dépend de votre mémoire.

Donc, si votre algorithme dépend réellement de la taille de votre tableau, vous n’avez pas de chance avec les tableaux java.

Comme je doute que vous ayez besoin de tout l’espace disponible pour écrire votre propre classe de collection qui se comporte comme un tableau mais n’a pas besoin de autant de mémoire. Cela réduirait les trous dans l'espace d'adressage (pour ainsi dire). Bien sûr, cela pourrait changer le comportement d’exécution que vous attendez de l’algorithme.

Il a été proposé d'ajouter des tableaux à index long à Java via Project Coin ( http://mail.openjdk.java.net/pipermail/coin-dev/2009-March/000869.html ) bien que rien n'ait été accepté ou planifié.

La solution simple: étant donné que num n'est jamais supérieur à 100 dans votre exemple de code, modifiez simplement son type en int .

Mais les points mentionnés par d'autres sur l'espace d'adressage sont également bons.

La bibliothèque jScience a un grand vecteur appelé Float64Vector . Bien que je n’aie jamais utilisé cette classe, elle pourrait répondre à vos besoins. Aucune promesse.

EDIT: Zach Scrivena a souligné dans les commentaires que le Float64Vector est dimensionné à ints. Je reste corrigé.

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top