Использование длинного индекса ArrayList в Java
Вопрос
Я пишу эту 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);
}
}
}
Решение
Я не уверен, почему ваш код будет компилироваться для начала.
Вы не должны использовать [] в списке массивов для доступа к членам. Массив - это просто список, который хранится внутри массива. Вы должны использовать операцию получения списка (которая все равно будет O (1)). Запись numlist [index] означает, что у вас есть массив объектов в numlist. Вы не можете переопределить операцию [], как в C ++.
Кроме того, int является 32-битным в Java. Массив длиной более 2 ^ 32 (поэтому вам понадобятся длинные индексы) маловероятен, и я даже не уверен, что спецификация позволяет это.
Другие советы
Помните, что с помощью 32-битного индекса int со знаком для long[] вы адресуете 16 ГБ ОЗУ.
Если вы действительно серьезно настроены получить большие простые числа с помощью сита, вам не сойдет с рук несколько вещей в вашей текущей реализации:
- ArrayList упакованных длинных позиций
- Использование [] как упоминает Ури
- Несистематическая запись на диск
спецификация Java ограничивает массивы максимум Элементы Integer.MAX_VALUE. Хотя List
может содержать больше элементов (это верно для Collection
s в общем ), вы можете только добавьте / получите / удалите / установите их, используя индекс int
.
Предполагая, что у вас есть память для такого количества элементов (я думаю, очень маловероятно), вы можете написать свою собственную структуру данных, состоящую из " concatenated " массивы. Методы get()
и set()
получают индекс long
и вычисляют соответствующий массив и индекс ArrayList
в этом массиве.
Кроме того, я бы предложил использовать логические значения для представления состояния каждого числа вместо явного хранения / удаления каждого числа. Это было бы лучше, потому что (1) логические значения занимают меньше места, чем long, и (2) смещение элементов (как сделано в <=>) во время удаления элемента может быть дорогим.
По крайней мере теоретический максимальный размер Java-массивов - Integer.MAX_VALUE. Это связано с тем, что тип индекса массива в соответствии со спецификацией int. На самом деле это зависит от вашей памяти, хотя.
Итак, если ваш алгоритм действительно зависит от наличия такого большого массива, вам не повезло с массивами Java.
Поскольку я сомневаюсь, вам понадобится все пространство, которое вы могли бы написать свой собственный класс коллекции, который действует как массив, но не требует такого большого количества памяти. Это разрушило бы целые в адресном пространстве (так сказать). Конечно, это может изменить поведение во время выполнения, которое вы ожидаете от алгоритма.
Были предложения добавить массивы с длинными индексами в Java через Project Coin ( http://mail.openjdk.java.net/pipermail/coin-dev/2009-March/000869.html ), хотя ничего не было принято или запланировано.
Простое решение: учитывая, что num
никогда не превышает 100 в вашем примере кода, просто измените его тип на int
. Р>
Но пункты, которые другие упоминали о адресном пространстве, также являются хорошими моментами.
в библиотеке jScience есть большой вектор под названием Float64Вектор.Хотя я никогда не использовал этот класс, он может соответствовать вашим потребностям.Не обещаю.
РЕДАКТИРОВАТЬ:Зак Скривена отметил в комментариях, что Float64Vector имеет целые числа.Я исправляюсь.