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

Question

Я пишу эту Java-программу, чтобы найти все простые числа вплоть до num, используя Сито Эратосфена, но когда я пытаюсь скомпилировать, он говорит, что я не могу использовать длинную переменную в качестве индекса массива, и он ожидает 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);
        }
    }
}

Answer 1

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

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

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

Answer 2

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

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

• ArrayList длинных коробок
• Использование [], как упоминает Ури
• Систематическое разбиение на страницы

Answer 3

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

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

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

Answer 4

Были предложения добавить массивы с длинными индексами в Java через Project Coin (http://mail.openjdk.java.net/pipermail/coin-dev/2009-March/000869.html), хотя ничего не было принято или запланировано.

Answer 5

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

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

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

Answer 6

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

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

Answer 7

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

EDIT: Зак Скривена указал в комментариях, что Float64Vector имеет размеры в дюймах. Я стою исправлено.