boolean []与BitSet:哪个更有效？

Question

什么在内存和CPU使用方面更有效 - 一个booleans或BitSet 数组？不使用特定的BitSet方法,只对数组进行get/set/clear(==,=,Arrays.fill).

Answer 1

• Boolean[] 每个布尔值使用大约4-20个字节.
• boolean[] 每个布尔值使用大约1个字节.
• BitSet 每个布尔值使用大约1位.

内存大小可能不是一个问题,在这种情况下boolean []可能更容易编码.

Answer 2

从带有筛子的Sun JDK 1.6计算素数的一些基准测试(最好的10次迭代预热,给JIT编译器一个机会,并排除随机调度延迟,Core 2 Duo T5600 1.83GHz):

除了非常小的尺寸外,BitSet比boolean []更有效.数组中的每个布尔值都需要一个字节.来自runtime.freeMemory()的数字对BitSet来说有点混乱,但更少.

boolean []的CPU效率更高,除了非常大的大小,它们大约是偶数.例如,对于大小为1百万的布尔[]大约快四倍(例如6毫秒对27毫秒),十亿和一亿大约是偶数.

Answer 3

您的问题有点偏左，但如果存储是一个问题，您可能需要研究Huffman compression。例如，00000001可以通过频率压缩到相当于{(7)0, (1)1}. 更“随机”的字符串00111010需要更复杂的表示，例如{(2)0, (3)1, (1)0, (1)1, (1)0}，并占用更多空间。根据位数据的结构，除了BitSet.

Answer 4

至于内存，a 的文档BitSet有非常明确的含义。尤其：

每个位集都有一个当前大小，即该位集当前使用的空间位数。请注意，大小与位集的实现相关，因此它可能会随实现而变化。位集的长度与位集的逻辑长度相关并且独立于实现来定义。

Java 库类的源代码是公开可用的，人们可以轻松地自行检查。尤其：

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

至于速度；这取决于一个人在做什么。一般来说，不要提前考虑速度；使用语义上最有意义的工具并生成最清晰的代码。仅在观察到未满足性能要求并识别瓶颈后进行优化。

来到 SO 并询问 A 是否比 B 快是愚蠢的，原因有很多，包括但当然不限于：

1. 这取决于应用程序，通常没有人响应该应用程序可以访问该应用程序。在使用它的上下文中分析和分析它。确保它是一个真正值得优化的瓶颈。
2. 像这样询问速度的问题通常表明OP认为他们关心效率，但不愿意分析并且没有定义性能要求。在表面之下，这通常是一个危险信号，表明 OP 正走在错误的道路上。

我知道这是一个老问题，但最近才出现；我相信这一点值得补充。

Answer 5

在这里，您可以看到将boolean [] []三角矩阵与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";
    }
}