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

Question

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

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

Answer 1

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

Answer 2

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

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

Answer 3

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

Answer 4

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

Answer 5

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

Answer 6

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

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

Answer 7

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

Answer 8

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

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

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

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

Answer 9

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

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

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

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

Answer 10

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

Answer 11

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

Answer 12

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

Answer 13

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

Answer 14

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

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

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

Answer 15

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

Answer 16

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

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