Boolean [] против BitSet: что более эффективно?

Ответ 1

В некоторых тестах с вычислениями SJ JDK 1.6 с ситом (лучше всего из 10 итераций, чтобы разогреться, дать компилятору JIT шанс и исключить случайные задержки планирования Core 2 Duo T5600 1,83 ГГц):

BitSet более эффективен с точки зрения памяти, чем boolean [], за исключением очень небольших размеров. Каждое булево значение в массиве принимает байт. Числа из runtime.freeMemory() немного запутаны для BitSet, но меньше.

boolean [] более эффективен с точки зрения эффективности процессора, за исключением очень больших размеров, где они примерно равны. Например, для размера 1 млн. Булевых [] примерно в четыре раза быстрее (например, 6 мс против 27 мс), для десяти и сто миллионов они примерно равны.

Ответ 2

• Boolean[] использует примерно 4-20 байт за каждое логическое значение.
• Boolean[] использует примерно 1 байт за каждое логическое значение.
• BitSet использует примерно 1 бит за каждое логическое значение.

Размер памяти может не быть проблемой для вас, и в этом случае boolean [] может быть проще для кода.

Ответ 3

Немного левого поля вашего вопроса, но если память вызывает беспокойство, вы можете захотеть заглянуть в сжатие Хаффмана. Например, 00000001 может быть сжат по частоте до уровня, эквивалентного {(7)0, (1)1}. Более "рандомизированная" строка 00111010 требует более сложного представления, например. {(2)0, (3)1, (1)0, (1)1, (1)0} и занимать больше места. В зависимости от структуры ваших битовых данных вы можете получить некоторую выгоду от ее использования, кроме BitSet.

Ответ 4

Это зависит как всегда. Да BitSet более эффективен с точки зрения памяти, но как только вам понадобится многопоточный доступ, логический [] может быть лучшим выбором. Например, для вычисления простых чисел вы устанавливаете значение boolean в true и, следовательно, вам не нужна синхронизация. Hans Boehm написал статью об этом, и тот же метод можно использовать для маркировки узлов в графе.

Ответ 5

Что касается памяти, документация для BitSet имеет довольно явные последствия. В частности:

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

Исходный код для классов библиотеки Java открыто доступен, и можно легко проверить это для себя. В частности:

The internal field corresponding to the serialField "bits".
89 
90     private long[] words;

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

Придя к SO и спрашивая, является ли A быстрее, чем B, является глупым по многим причинам, включая, но не ограничиваясь:

• Это зависит от приложения, к которому никто в целом не имеет доступа. Проанализируйте и профилируйте его в контексте, в котором он используется. Убедитесь, что это узкое место, которое действительно стоит оптимизировать.
• Вопросы, подобные этому, которые задают скорость, обычно показывают, что OP думает, что они заботятся об эффективности, но не желают профилировать и не определяют требования к производительности. Под поверхностью, обычно красным флагом, что OP движется по неправильному пути.

Я знаю, что это старый вопрос, но он появился недавно; и я считаю, что это стоит добавить.

Ответ 6

Переход с Java на CPU полностью зависит от VM. Например, раньше было, что логическое значение было реализовано как 32-битное значение (скорее всего, это верно и по сей день).

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

Вы можете сделать это, когда идете. Например, я однажды решил не вызывать .intern() в Strings, потому что, когда я запускал код в профилировщике, он слишком сильно замедлял его (несмотря на меньшее количество памяти).

Ответ 7

Здесь вы можете увидеть тест памяти/времени, сравнивающий логическую матрицу [] [] треугольника с треугольной матрицей BitSet [].

Я создаю, устанавливаю и читаю значения (size * (size-1)/2) и сравниваю использование и время использования памяти...

Надеюсь, это поможет...

Вот код... (просто проклятый грязный тестовый код, извините;)

import java.util.BitSet;
import java.util.Date;

public class BooleanBitSetProfiler {

    Runtime runtime;
    int sum = 0;
    public void doIt() {

        runtime = Runtime.getRuntime();
        long[][] bitsetMatrix = new long[30][2];
        long[][] booleanMatrix = new long[30][2];
        int size = 1000;
        for (int i = 0; i < booleanMatrix.length; i++) {
            booleanMatrix[i] = testBooleanMatrix(size);
            bitsetMatrix[i] = testBitSet(size);
            size += 2000;
        }
        int debug = 1;
        for (int j = 0; j < booleanMatrix.length; j++){
            System.out.print(booleanMatrix[j][0] + ";");
        }
        System.out.println();
        for (int j = 0; j < booleanMatrix.length; j++){
            System.out.print(booleanMatrix[j][1] + ";");
        }
        System.out.println();
        for (int j = 0; j < bitsetMatrix.length; j++){
            System.out.print(bitsetMatrix[j][0] + ";");
        }
        System.out.println();
        for (int j = 0; j < bitsetMatrix.length; j++){
            System.out.print(bitsetMatrix[j][1] + ";");
        }
        System.out.println();
    }

    private long memory () {
        return runtime.totalMemory() - runtime.freeMemory();
    }
    private long[] testBooleanMatrix(int size) {
        runtime.gc();
        long startTime = new Date().getTime();
        long startMemory = memory();
        boolean[][] matrix = new boolean[size][];
        for (int i = 0; i < size; i++) {
            matrix[i] = new boolean[size - i - 1];
        }
        long creationMemory = memory();
        long creationTime = new Date().getTime();
        for (int i = 0; i < size; i++)  {
            for (int j = 0; j < matrix[i].length; j++) {
                matrix[i][j] = i % 2 == 0;
            }
        }
        long setMemory = memory();
        long setTime = new Date().getTime();
        for (int i = 0; i < size; i++)  {
            for (int j = 0; j < matrix[i].length; j++) {
                if (matrix[i][j]) sum++;
            }
        }
        long readTime = new Date().getTime();
        System.out.println("Boolean[][] (size " + size + ")");
        System.out.println("Creation memory " + printMem(creationMemory-startMemory) + ", set memory " + printMem(setMemory-startMemory));
        System.out.println("Creation time " + printTime(creationTime-startTime) + ", set time " + printTime(setTime - creationTime) + " read time " + printTime(readTime - setTime) + "\n");
        runtime.gc();
        return new long[]{(setMemory-startMemory)/(1024*1024), (readTime-startTime)};
    }
    private long[] testBitSet(int size) {
        runtime.gc();
        long startTime = new Date().getTime();
        long startMemory = memory();
        BitSet[] matrix = new BitSet[size];
        for (int i = 0; i < size; i++) {
            matrix[i] = new BitSet(size - i - 1);
        }
        long creationMemory = memory();
        long creationTime = new Date().getTime();
        for (int i = 0; i < size; i++)  {
            for (int j = 0; j < matrix[i].size(); j++) {
                matrix[i].set(j, (i % 2 == 0));
            }
        }
        long setMemory = memory();
        long setTime = new Date().getTime();
        for (int i = 0; i < size; i++)  {
            for (int j = 0; j < matrix[i].size(); j++) {
                if (matrix[i].get(j)) sum++;
            }
        }
        long readTime = new Date().getTime();
        System.out.println("BitSet[] (size " + size + ")");
        System.out.println("Creation memory " + printMem(creationMemory-startMemory) + ", set memory " + printMem(setMemory-startMemory));
        System.out.println("Creation time " + printTime(creationTime-startTime) + ", set time " + printTime(setTime - creationTime) + " read time " + printTime(readTime - setTime) + "\n");
        runtime.gc();
        return new long[]{(setMemory-startMemory)/(1024*1024), (readTime-startTime)};
    }

    private String printMem(long mem) {
        mem = mem / (1024*1024);
        return mem + "MB";
    }
    private String printTime(long milis) {
        int seconds = (int) (milis / 1000);
        milis = milis % 1000;
        return seconds > 0 ? seconds + "s " + milis + "ms" : milis + "ms";
    }
}

Ответ 8

Я считаю, что BitSet более эффективен с точки зрения памяти и ЦП, может ли он внутренне упаковывать биты в типы int, longs или native, тогда как для boolean [] требуется байт для каждого бита данных. Кроме того, если вы использовали другие методы (и, или, и т.д.), Вы обнаружите, что BitSet более эффективен, так как нет необходимости перебирать каждый элемент массива; вместо этого используется побитовая математика.