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

Я пытаюсь найти контрпример к гипотезе Pólya, которая будет где-то в 900 миллионов. Я использую очень эффективный алгоритм, который даже не требует какой-либо факторизации (аналогично сите из Eratosthenes, но с еще большей информацией. Поэтому требуется большой массив ints.

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

Ответ 1

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

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

Ответ 2

Java будет содержать до 2 миллиардов элементов массива. Его машина (и ваша ограниченная память), которая не может обрабатывать такое большое количество.

Ответ 3

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

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

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

Ответ 4

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

Ответ 5

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

Ответ 6

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

Ответ 7

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

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

Ответ 8

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

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

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

Ответ 9

Для эффективного хранения больших массивов примитивов (булевых, байтовых,... double я рекомендую нашу библиотеку JLargeArrays, доступную на GitHub (https://github.com/IcmVis/JLargeArrays) - он хранит произвольные большие массивы, обеспечивающие достаточную память, например, массив 12 Гбайт на ПК с 16 ГБ, протестированный на JVM Oracle и IBM с хорошей многопоточной эффективностью.

Ответ 10

Я написал версию сита Эратосфена для Project Euler, которая работала над кусками пространства поиска за раз. Он обрабатывает первые целые числа 1M (например), но сохраняет каждое простое число, которое он находит в таблице. После того, как вы повторили все найденные до сих пор простые числа, массив повторно инициализируется, и найденные простые числа используются для обозначения массива перед поиском следующего.

Таблица отображает штрих в его "смещение" от начала массива для следующей итерации обработки.

Это похоже на концепцию (если не в реализации) на то, как языки функционального программирования выполняют ленивую оценку списков (хотя и с большими шагами). Выделение всей памяти вперед не требуется, так как вас интересуют только те части массива, которые проходят ваш тест на грубость. Хранение непривязанных символов не полезно для вас.

Этот метод также обеспечивает memoisation для последующих итераций по простым числам. Это быстрее, чем сканирование вашей редкой ситовой структуры данных, которая ищет их каждый раз.

Ответ 11

Вторая идея @sfossen и @Aaron Digulla. Я бы пошел на доступ к диску. Если ваш алгоритм может принимать интерфейс List, а не простой массив, вы можете написать адаптер из списка в файл с отображением памяти.

Ответ 12

Используйте Tokyo Cabinet, Berkeley DB или любое другое дисковое хранилище ключей. Они быстрее, чем любая обычная база данных, но позволяют использовать диск вместо памяти.

Ответ 13

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

Ответ 14

Вы могли бы обойтись с 900 миллионами бит? (возможно, хранится как массив байтов).

Ответ 15

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

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

Ответ 16

Вместо этого используйте сопоставленный с памятью файл (пакет Java 5 NIO). Или переместите сито в небольшую библиотеку C и используйте Java JNI.