在java中使用long作为ArrayList索引

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

  •  19-08-2019
  •  | 
  •  

题

我正在编写这个java程序来使用埃拉托斯特尼筛法查找直到num的所有素数，但是当我尝试编译时，它说我不能使用long 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);
        }
    }
}
有帮助吗？

解决方案

我不知道为什么你的代码将编译开始。

你不应该使用[]阵列中的列表来访问成员。一个ArrayList仅仅是在内部存储在数组中的列表。你必须使用列表get操作（这仍然是O（1））。写numlist [指数]意味着你有在numlist对象的数组。不能覆盖的[]操作如在C ++。

另外，int是在Java中的32位。具有长度大于阵列2 ^ 32（所以你需要长索引）是不可能的，我甚至不知道该规范允许它。

其他提示

认识到，一个32位的签署int索引到一个长[]你在处理16GB。

如果你真的很严重关于得到大素数的筛子，你不要摆脱几件事情在你目前的实施:

  • 对列表的盒装的渴望
  • 使用[]如Uri提到
  • 没有系统地呼磁盘

在 Java规范至多限制阵列Integer.MAX_VALUE的元素。虽然List可以含有多个元素（这是为Collections 在真一般），你只能添加/获得/删除/使用int索引设置它们。

假设你有很多元素（不太可能，我认为）的内存，你可以写由“串联”阵列，你自己的数据结构。的get()和set()方法将采取long索引，并计算出该阵列中相应的数组和索引int

另外，我建议使用布尔值来表示每个号码的状态，而不是存储/明确地移除每个号码。这将是更好的，因为（1）布尔值取比多头更少的空间，和（2）元素的移除期间切换元件（如在ArrayList完成）可能是昂贵的。

至少Java数组的理论最大尺寸是Integer.MAX_VALUE的。这是因为数组的索引的类型是根据该规范的一个int。在现实中，它取决于你的记忆，虽然。

所以，如果你的算法实际上取决于具有如此大阵，你的运气了与Java数组。

正如我怀疑你将需要所有你能写就像一个数组，但并不需要尽可能多的内存你自己的集合类的空间。它会崩溃的整体而在地址空间（这么说）。当然，这可能会改变你是从算法期望运行时行为。

有人建议通过 Project Coin 将长索引数组添加到 Java（ http://mail.openjdk.java.net/pipermail/coin-dev/2009-March/000869.html ）尽管尚未接受或安排任何内容。

在简单的解决方案：考虑到num不会比你的代码样本中100大，只是改变它的类型来int。

但其他人所说的关于地址空间中的点也是好点。

的

jScience库有一个称为大载体 Float64Vector 。虽然我从来没有使用过这个类可能满足您的需求。任何承诺。

编辑： 扎克Scrivena，该Float64Vector尺寸以整数评论中指出。我站在纠正。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top