логический [] против BitSet: что является более эффективным?

Question

Что является более эффективным с точки зрения использования памяти и процессора - массив boolean с или BitSet? Определенные методы BitSet не используются, только get / set / clear (==, =, Arrays.fill соответственно для массива).

Answer 1

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

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

Answer 2

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

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

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

Answer 3

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

Answer 4

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

Я создаю, устанавливаю и считываю (размер * (размер-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";
    }
}

Answer 5

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

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

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

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

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

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

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

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

Answer 6

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

Answer 7

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

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

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

Answer 8

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