эффективно перебирать не установленные значения в массивном битовом массиве в Java

Я получил массивный массив битов, сохраненный как массив байтов, который представляет все значения int со знаком (4 294 967 295).

byte[] bitArray = byte[536870912];

Каждый байт в массиве представляет 8 чисел, по одному на каждый бит. Это означает, что byte[0] хранит 1, 2, 3, 4, 5, 6, 7, 8, а byte[1] хранит 9, 10, 11, 12, 13, 14, 15, 16 и т. д.

Я использую это для хранения огромной таблицы, где я могу установить числа либо в true, либо в false (0 или 1). У меня есть несколько довольно эффективных методов, чтобы проверить, установлен ли бит, и установить бит (только с использованием побитовых операторов).

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

Как я могу эффективно перебирать не заданные значения в битовом массиве несколько раз?


java bitarray iterate
person Horse SMith    schedule 26.02.2015    source источник
comment
Какая часть всех чисел, скорее всего, окажется истинной? Если он очень маленький, вы можете использовать Set<Integer> для хранения истинных чисел, а не использовать byte[536870912].   -  person Paul Boddington    schedule 27.02.2015
comment
@pbabcdefp Это очень случайно.   -  person Horse SMith    schedule 27.02.2015
comment
@pbabcdefp Я согласен, что это много, но это не мой выбор. Мне нужно использовать не установленные биты снова и снова. Я полностью понимаю, что я должен просто пройтись по нему один раз и составить из него упорядоченный список/массив, но тогда я бы сохранил их как фактические числа. Мне нужно хранить только около 10% из них, но они будут использовать как минимум в 32 раза больше места... :p   -  person Horse SMith    schedule 27.02.2015

Ответы (1)


arrow_upward
4
arrow_downward

Как я могу эффективно перебирать этот битовый массив?

Один из способов сделать это — использовать BitSet. Это будет сканировать long[], исследуя 64-бита за раз, но его базовые методы превращаются во встроенные функции. то есть отдельные инструкции машинного кода, которые, вероятно, будут быстрее, чем все, что вы можете написать на Java.

Если вы действительно хотите написать это самостоятельно, я предлагаю вам посмотреть, как работает BitSet, и скопировать его код. (Или используйте BitSet)

Я предлагаю вам взглянуть на методы Лонга numberOfLeadingZeros(long) numberOfTrailingZeros(long) bitCount(длинный)

Внутренний — это метод, который JVM «распознает» и заменяет специальными инструкциями машинного кода. Это может сделать его намного быстрее, чем копирование кода и запуск того же кода в Java.

Как я могу эффективно перебирать не заданные значения в битовом массиве несколько раз?

В BitSet используется следующий цикл

public int nextSetBit(int fromIndex) {
    if (fromIndex < 0)
        throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex);

    checkInvariants();

    int u = wordIndex(fromIndex);
    if (u >= wordsInUse)
        return -1;

    long word = words[u] & (WORD_MASK << fromIndex);

    while (true) {
        if (word != 0)
            return (u * BITS_PER_WORD) + Long.numberOfTrailingZeros(word);
        if (++u == wordsInUse)
            return -1;
        word = words[u];
    }
}

Примечание: здесь проверяется 64-битная версия на каждой итерации.

person Peter Lawrey    schedule 26.02.2015
comment
Ба, я думаю, что немного испортил этот вопрос, см. Мое редактирование. ›_‹ - person Horse SMith; 27.02.2015
comment
Обратите внимание, что BitSet.html# nextSetBit делает именно то, что хочет OP. - person Adrian Leonhard; 27.02.2015
comment
Битсет это интересно! Есть ли способ сохранить точные числа, которые я ищу, более эффективным способом, чем в объектах Integer в упорядоченном списке или списке массивов и т. д. Порядок действительно имеет значение, но только то, что они в числовом порядке. Я ожидаю, что только около 10% не будут установлены. - person Horse SMith; 27.02.2015
comment
@HorseSMith Целочисленный объект использует 24 байта, поэтому вам будет трудно превзойти установленный бит, если только ваши 10% не распределены равномерно, например, IP и платья не распределены. В любом случае он использует только 1/2 ГБ, и экономить немного больше памяти вряд ли стоит. - person Peter Lawrey; 27.02.2015