制作一个非常大的 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屋！