логические[] и BitSet: что более эффективно?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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";
    }
}

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