制作一个非常大的 Java 数组 [英] Making a very large Java array
问题描述
我试图找到 Pólya Conjecture 的反例,它将大约是 9 亿.我正在使用一种非常有效的算法,它甚至不需要任何因式分解(类似于 Eratosthenes 筛分法,但具有更多信息.因此,需要大量整数.
I'm trying to find a counterexample to the Pólya Conjecture which will be somewhere in the 900 millions. I'm using a very efficient algorithm that doesn't even require any factorization (similar to a Sieve of Eratosthenes, but with even more information. So, a large array of ints is required.
该程序高效且正确,但需要一个数组,直到我要检查的 x 为止(它检查 (2, x) 中的所有数字).所以,如果反例是 9 亿,我需要一个同样大的数组.Java 不允许我超过 2000 万.我有什么办法可以得到这么大的数组吗?
The program is efficient and correct, but requires an array up to the x i want to check for (it checks all numbers from (2, x)). So, if the counterexample is in the 900 millions, I need an array that will be just as large. Java won't allow me anything over about 20 million. Is there anything I can possibly do to get an array that large?
推荐答案
Java 数组由 int 索引,因此数组不能大于 2^31(没有无符号整数).因此,数组的最大大小为 2147483648,它消耗(对于普通 int[])8589934592 字节(= 8GB).
Java arrays are indexed by int, so an array can't get larger than 2^31 (there are no unsigned ints). So, the maximum size of an array is 2147483648, which consumes (for a plain int[]) 8589934592 bytes (= 8GB).
因此,int-index 通常不是限制,因为无论如何你都会耗尽内存.
Thus, the int-index is usually not a limitation, since you would run out of memory anyway.
在您的算法中,您应该使用 List(或 Map)作为您的数据结构,并选择可以增长超过 2^31 的 List(或 Map)实现.这可能会变得棘手,因为通常"实现 ArrayList(和 HashMap)在内部使用数组.您必须实现自定义数据结构;例如通过使用 2 级数组(列表/数组).当你在做的时候,你也可以试着把这些东西塞得更紧.
In your algorithm, you should use a List (or a Map) as your data structure instead, and choose an implementation of List (or Map) that can grow beyond 2^31. This can get tricky, since the "usual" implementation ArrayList (and HashMap) uses arrays internally. You will have to implement a custom data structure; e.g. by using a 2-level array (a list/array). When you are at it, you can also try to pack the bits more tightly.
这篇关于制作一个非常大的 Java 数组的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!