Использование длинного индекса ArrayList в java

Я пишу эту java-программу, чтобы найти все простые числа до num, используя сито Eratosthenes, но когда я пытаюсь скомпилировать, он говорит, что я не могу использовать длинный var как индекс массива, и он ожидает, что int var на своем месте. Но я буду работать с большими числами, поэтому я не могу использовать int. Что я могу сделать?

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);
        }
    }
}

Ответы

Ответ 1

Я не уверен, почему ваш код будет скомпилирован для начала.

Вы не должны использовать [] в списке массивов для доступа к элементам. Аррайалист - это просто список, который хранится внутри массива. Вы должны использовать операцию получения списка (которая все равно будет O (1)). Запись numlist [index] означает, что у вас есть массив объектов в числовом списке. Вы не можете переопределить операцию [], как на С++.

Кроме того, int составляет 32 бита в Java. Наличие массива длиной больше 2 ^ 32 (так что вам нужны длинные индексы) маловероятно, и я даже не уверен, что спецификация позволяет это.

Ответ 2

Поймите, что с 32-разрядным индексом int с длинным [] вы адресуете 16 ГБ ОЗУ.

Если вы действительно серьезно относитесь к тому, чтобы добраться до больших простых чисел с помощью сита, вы не сможете уйти с несколькими вещами в своем текущем имплементе:

  • ArrayList с короткими длинными
  • Использование [], как указано в Uri
  • Не систематически подкачки на диске

Ответ 3

спецификация Java ограничивает массивы не более чем целыми элементами Integer.MAX_VALUE. Хотя List может содержать больше элементов (это верно для Collection в целом), вы можете добавить/получить/удалить/установить их с помощью индекса int.

Предполагая, что у вас есть память для многих элементов (что маловероятно, я думаю), вы можете написать свою собственную структуру данных, состоящую из "конкатенированных" массивов. Методы get() и set() использовали бы индекс long и вычисляли соответствующий массив и int индекс внутри этого массива.

Кроме того, я бы предложил использовать booleans для представления состояния каждого числа, вместо того, чтобы хранить/удалять каждый номер явно. Это было бы лучше, потому что (1) булевы занимают меньше места, чем longs, и (2) перемещение элементов (как сделано в ArrayList) во время удаления элемента может быть дорогостоящим.

Ответ 4

Как минимум теоретический максимальный размер массивов java - Integer.MAX_VALUE. Это связано с тем, что тип индекса массива согласно спецификации int. На самом деле это зависит от вашей памяти.

Итак, если ваш алгоритм действительно зависит от наличия такого большого массива, вам не повезло с массивами java.

Как я сомневаюсь, вам понадобится все пространство, в котором вы могли бы написать свой собственный класс коллекции, который действует как массив, но не нуждается в такой большой памяти. Это разрушит целостности в адресном пространстве (так сказать). Конечно, это может изменить поведение времени выполнения, которое вы ожидаете от алгоритма.

Ответ 6

Простое решение: учитывая, что num никогда не превышает 100 в вашем примере кода, просто измените его на int.

Но другие точки, упомянутые в адресном пространстве, также являются хорошими точками.

Ответ 7

Библиотека jScience имеет большой вектор, называемый Float64Vector. Хотя я никогда не использовал этот класс, он мог бы соответствовать вашим потребностям. Нет promises.

EDIT: Зак Скривена отметил в комментариях, что Float64Vector рассчитан на ints. Я исправляюсь.