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

小开

我认为 BitSet 更加节省内存和 CPU，因为它可以在内部将比特打包成 int、 longs 或本机数据类型，而 boolean []需要为每个比特的数据打包一个字节。此外，如果您使用其他方法(和，或，等) ，您会发现 BitSet 更有效，因为不需要遍历数组的每个元素; 而是使用按位数学。

小开

从 Java 到 CPU 完全是 VM 特有的。例如，过去布尔值实际上是作为32位值实现的(现在很可能也是这样)。

除非你知道这很重要，否则最好还是写代码清晰明了，分析它，然后修复那些速度慢或消耗大量内存的部分。

你可以边走边做。例如，我曾经决定不打电话。因为当我在分析器中运行代码时，它会大大降低速度(尽管使用了更少的内存)。

小开

最佳答案

从一些基准测试中可以看出，Sun JDK 1.6计算质数带有筛子(10次迭代中最好的一次进行预热，给 JIT 编译器一次机会，并排除随机调度延迟，Core 2 Duo T56001.83 GHz) :

BitSet 比 boolean []更有效的内存，除了非常小的尺寸。数组中的每个布尔值都接受一个字节。FreeMemory ()中的数字对 BitSet 来说有点混乱，但是比较少。

Boolean []的 CPU 效率更高，除了非常大的大小，它们大约是偶数。例如，对于大小为100万的布尔值[] ，它的速度要快四倍(比如6ms 比27ms) ，而对于100万和1亿的布尔值，它们的速度大约是平均的。

小开

这要看情况。是的，BitSet 的内存效率更高，但是一旦您需要多线程访问布尔值[]可能是更好的选择。例如，对于计算素数，您只需将布尔值设置为 true，因此实际上并不需要同步。汉斯 · 博姆已经就此写了一些文章，同样的技术也可以用来标记图中的节点。

小开

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 快是愚蠢的，原因有很多，包括但肯定不限于:

它取决于应用程序，通常没有响应者可以访问该应用程序。根据它所处的环境分析和描述它。确保这是一个值得优化的瓶颈。
像这样问速度的问题通常表明 OP 认为他们关心效率，但是不愿意分析，也没有定义性能需求。在表面之下，这通常是一个危险信号，表明 OP 正在朝着错误的方向前进。

我知道这是一个古老的问题，但它是最近才提出来的; 我相信这是值得补充的。

小开

这里你可以看到一个 Memory/Time 基准测试，比较布尔型[][]三角矩阵和 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";
}
}