Как вы делаете действительно большие логические массивы, используя Java?

Question

Когда я пытаюсь создать очень большой логический массив с использованием Java, например:

    boolean[] isPrime1 = new boolean[600851475144];

Возможно ли получить ошибку потери точности?

Это слишком большой?

Answer 1

Чтобы хранить 600 миллиард бит, вам необходимо абсолютное минимальное адресное пространство 75 гигабайт ! Удачи с этим!

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

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

Answer 2

Поскольку вы пытаетесь решить проблему Эйлера № 3 неверным способом, вот подсказка: вы должны найти все простые факторы числа, а не все простые цифры ниже определенного предела.

Кстати: эта конкретная проблема Эйлера может быть решена с использованием очень небольшого объема оперативной памяти.

Answer 3

Рассмотрите возможность использования BitSet .

Answer 4

Индекс массива - это int, а не long, поэтому ваш "массив" слишком большой, чтобы поместиться в массив. Один из классов java Collection может быть более подходящим. Не берите в голову - Collection.size () также возвращает int, поэтому Collection не может хранить более Integer.MAX_VALUE элементов.

Answer 5

Проблема в том, что вы используете длинное значение вместо значения типа int для размера массива. Java не поддерживает длины массива, превышающие максимальное значение типа int. Java рассматривает вашу длину как long, потому что указанный вами размер превышает максимальное значение для int, но умещается в long. Следовательно, он должен преобразовать длину обратно в int, чтобы создать массив. Преобразование из long -> int выдает предупреждение, которое вы видите

Answer 6

Вы можете использовать массив long, инкапсулированный в класс, который будет обрабатывать все операции в массиве. Что-то вроде вашей собственной реализации BitSet.

Answer 7

Хм ... это будет примерно 70 ГБ логических значений. Не сработает Ни за что.

Answer 8

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

 oldValue = bitArrayBin.setBit(sequenceId, true)
 if (oldVlaue) {
   "message is duplicated"
 }

Метод возвращает старое значение.

Если у - длинный индекс, он используется для получения индекса бина и смещения в нем.

y = bin index * 64 + offset

BitArrayBin - это не что иное, как держатель для многих лотков, размер которых можно определить во время его построения. Каждый бин содержит длинную переменную для хранения битов, поэтому он может хранить до 64 логических значений.

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

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

Answer 9

Какие значения у вас есть в массиве? Для такого большого числа я предполагаю, что это будет разреженный массив, поэтому, возможно, было бы лучше использовать Map / List и просто выделить место и сохранить битовое значение 1. Или для значения 0, если большинство ваших значений будет 1.

Answer 10

Почему бы просто не сохранить значения в файле, а затем найти нужную позицию в файле и выбрать нужное значение. Как уже говорили другие, это 70 ГБ данных. В большинстве случаев вы даже не сможете хранить это в памяти. Если вы собираетесь сохранить его в файле, вы можете даже взглянуть на отдельные биты при сохранении и извлечении данных, используя побитовые операторы для экономии места на диске.

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