boolean[] 与 BitSet：哪个更高效？

Question

就内存和 CPU 使用而言，哪个更高效 - 布尔值数组还是 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 具有更高的内存效率[ ] 除了非常小的尺寸。 数组中的每个布尔值都占用一个字节。 对于 BitSet 来说，runtime.freeMemory() 中的数字有点混乱，但也比较少。

boolean[] 的 CPU 效率更高，除了非常大的尺寸之外，它们大约是偶数。 例如，对于大小为 100 万的 boolean[] 大约快四倍（例如 6ms 与 27ms），对于 100 万和 1000000000 个，它们大约是偶数。

Answer 3

在这里，您可以看到内存/时间基准测试，比较 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";
    }
}

Answer 4

至于内存，BitSet< 的文档/code>具有非常明显的含义。 尤其：

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

Java 库类的源代码是公开可用的，人们可以轻松自己检查一下。 特别是：

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

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

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

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

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

Answer 5

您的问题有点偏左，但如果存储是一个问题，您可能需要研究霍夫曼压缩< /a>. 例如，00000001 可以按频率压缩为相当于 {(7)0, (1)1} 的值。 更“随机”的字符串 00111010 需要更复杂的表示，例如 {(2)0, (3)1, (1)0, (1)1, (1)0 }，并占用更多空间。 根据位数据的结构，您可能会从其使用中获得除 BitSet 之外的一些存储优势。

Answer 6

这取决于一如既往。
是的，BitSet 的内存效率更高，但一旦您需要多线程访问，boolean[] 可能是更好的选择。 例如，对于计算素数，您只需将布尔值设置为 true，因此实际上并不需要同步。 Hans Boehm 写了一些关于此的论文以及相同的技术可用于标记图中的节点。

Answer 7

从 Java 到 CPU 完全是 VM 特定的。 例如，布尔值过去实际上是作为 32 位值实现的（今天很可能也是如此）。

除非您知道这很重要，否则最好编写清晰的代码，对其进行分析，然后修复速度慢或消耗大量内存的部分。

您可以随时执行此操作。 例如，我曾经决定不在字符串上调用 .intern() ，因为当我在探查器中运行代码时，它会减慢速度太多（尽管使用较少的内存）。

Answer 8

我相信 BitSet 的内存和 CPU 效率更高，因为它可以在内部将位打包为 int、long 或本机数据类型，而 boolean[] 需要每个数据位一个字节。 此外，如果您要使用其他方法（and、or 等），您会发现 BitSet 更有效，因为不需要迭代数组的每个元素； 而是使用按位数学。