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

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

  •  19-08-2019
  •  | 
  •  

Вопрос

Я пишу эту 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 имеет целые числа.Я исправляюсь.

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top