Создание очень большого массива Java

Question

Я пытаюсь найти контрпример к гипотезе Поли , которая будет где-то в 900 миллионах. Я использую очень эффективный алгоритм, который даже не требует какой-либо факторизации (похож на «Сито Эратосфена», но содержит еще больше информации. Поэтому требуется большой массив целых.

Программа эффективна и корректна, но требует массив до x, который я хочу проверить (она проверяет все числа из (2, x)). Итак, если контрпример составляет 900 миллионов, мне нужен массив, который будет таким же большим. Ява не позволит мне больше 20 миллионов. Могу ли я что-нибудь сделать, чтобы получить такой большой массив?

Answer 1

Возможно, вы захотите увеличить максимальный размер кучи JVM. Вы можете сделать это с помощью параметра командной строки.

Я считаю, что это -Xmx3600m (3600 мегабайт)

Answer 2

Java-массивы индексируются с помощью int, поэтому массив не может быть больше 2 ^ 31 (нет беззнаковых целых). Таким образом, максимальный размер массива составляет 2147483648, который потребляет (для простого int []) 8589934592 байта (= 8 ГБ).

Таким образом, int-index обычно не является ограничением, так как в любом случае вам не хватит памяти.

В вашем алгоритме вы должны использовать список (или карту) вместо структуры данных и выбрать реализацию списка (или карты), которая может выйти за пределы 2 ^ 31. Это может быть сложно, так как «обычная» реализация ArrayList (и HashMap) использует массивы внутри. Вам нужно будет реализовать собственную структуру данных; например используя двухуровневый массив (список / массив). Когда вы на это, вы также можете попытаться упаковать биты более плотно.

Answer 3

Java допускает до 2 миллиардов записей массива. Ваша машина (и ваша ограниченная память) не могут обрабатывать такое большое количество.

Answer 4

900 миллионов 32-битных целых без дополнительных издержек - и всегда будет больше служебных данных - потребует чуть более 3,35 ГБ. Единственный способ получить столько памяти - это использовать 64-битную JVM (на компьютере с ОЗУ не менее 8 ГБ) или использовать кэш-память на диске.

Answer 5

Если вам не нужно, чтобы все сразу загружалось в память, вы можете разбить его на файлы и сохранить на диске.

Answer 6

Что вы подразумеваете под "не позволят". Вы, вероятно, получаете OutOfMemoryError, поэтому добавьте больше памяти с параметром командной строки -Xmx.

Answer 7

В зависимости от того, как вам нужен доступ к массиву, вы можете найти RandomAccessFile , который позволит вам использовать файл, который больше, чем умещается в памяти. Однако производительность, которую вы получаете, очень зависит от вашего поведения доступа.

Answer 8

Если ваш алгоритм это позволяет:

• Вычислить его по кусочкам, которые помещаются в память.

  Вам придется повторить вычисления для каждого среза, но часто это будет достаточно быстро.

• Использовать массив меньшего числового типа, например, байта.

Answer 9

Вы можете определить свой собственный класс, который хранит данные в 2d массиве, который был бы ближе к sqrt (n) по sqrt (n). Затем используйте функцию индекса для определения двух индексов массива. При необходимости это может быть расширено до большего размера.

Основная проблема, с которой вы столкнетесь, - это нехватка ОЗУ. Если вы приблизитесь к этому пределу, вам придется переосмыслить свой алгоритм или рассмотреть внешнее хранилище (то есть файл или базу данных).

Answer 10

Вы можете попробовать разбить его на несколько массивов.

for(int x = 0; x <= 1000000; x++){
    myFirstList.add(x);
}
for(int x = 1000001; x <= 2000000; x++){
    mySecondList.add(x);
}

затем итерируйте их.

for(int x: myFirstList){
    for(int y: myFirstList){
        //Remove multiples
    }
}
//repeat for second list