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

Question

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

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

Answer 1

не могли бы вы обойтись с 900 миллионами бит? (может храниться в виде байтового массива).

Answer 2

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

Answer 3

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

Answer 4

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

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

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

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

Answer 5

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