11

我正在编写这个 java 程序来使用 Eratosthenes 的 Sieve 查找直到 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);
        }
    }
}
4

7 回答 7

15

我不确定为什么你的代码会开始编译。

您不应该在数组列表中使用 [] 来访问成员。arraylist 只是一个内部存储在数组中的列表。您必须使用列表获取操作（仍然是 O(1)）。写 numlist[index] 意味着你在 numlist 中有一个对象数组。您不能像在 C++ 中那样覆盖 [] 操作。

此外，一个 int 在 Java 中是 32 位的。长度大于 2^32 的数组（因此您需要长索引）是不可能的，我什至不确定规范是否允许。

于 2009-01-19T23:46:35.213 回答
13

意识到使用 long[] 的 32 位有符号 int 索引，您正在处理 16GB 的 RAM。

如果你真的很想用筛子得到大素数，那么在你当前的 impl 中你不会逃脱一些事情：

  • 盒装多头的 ArrayList
  • 像 Uri 提到的那样使用 []
  • 没有系统地分页到磁盘
于 2009-01-19T23:51:57.107 回答
10

Java 规范将数组限制为最多 Integer.MAX_VALUE 元素。虽然 aList可能包含更多元素（这通常适用于Collections ），但您只能使用索引添加/获取/删除/设置它们。int

假设您有这么多元素的内存（我认为这不太可能），您可以编写自己的由“连接”数组组成的数据结构。get()andset()方法将获取一个索引long并找出该数组中的相应数组和int索引。

另外，我建议使用布尔值来表示每个数字的状态，而不是显式存储/删除每个数字。这会更好，因为 (1) boolean 比 longs 占用更少的空间，并且 (2)ArrayList在元素移除期间移动元素（如 中所做的）可能很昂贵。

于 2009-01-20T07:09:10.313 回答
4

至少理论上java数组的最大大小是Integer.MAX_VALUE。这是因为数组索引的类型根据规范是 int。实际上，这取决于您的记忆力。

因此，如果您的算法真的依赖于拥有如此大的数组，那么您对 ​​java 数组就不走运了。

因为我怀疑您是否需要所有可以编写自己的集合类的空间，该集合类的作用类似于数组，但不需要太多内存。它会折叠地址空间中的整体（可以这么说）。当然，这可能会改变您对算法所期望的运行时行为。

于 2009-01-19T23:59:55.203 回答
4

已经有人提议通过 Project Coin ( http://mail.openjdk.java.net/pipermail/coin-dev/2009-March/000869.html ) 将长索引数组添加到 Java 中，尽管没有任何内容被接受或安排。

于 2011-04-15T13:52:43.453 回答
2

简单的解决方案：考虑到num您的代码示例中永远不会大于 100，只需将其类型更改为int.

但是其他人提到的关于地址空间的观点也很好。

于 2009-01-20T00:11:34.773 回答
0

jScience 库有一个名为Float64Vector的大向量。虽然我从未使用过这个类，但它可能适合您的需求。没有保证。

编辑：Zach Scrivena 在评论中指出 Float64Vector 的尺寸为整数。我站得更正了。

于 2009-01-20T01:16:11.650 回答