就内存和 CPU 使用而言，什么更有效 - s 数组boolean或 BitSet？不使用特定的 BitSet 方法，仅使用 get/set/clear（==、=、Arrays.fill 分别为数组）。
Maxim
问问题
43961 次
8 回答
53
Boolean[]每个布尔值使用大约 4-20 个字节。boolean[]每个布尔值使用大约 1 个字节。BitSet每个布尔值使用大约 1 位。
内存大小对您来说可能不是问题，在这种情况下 boolean[] 可能更容易编码。
于 2009-03-03T21:04:06.620 回答
43
从一些使用 Sun JDK 1.6 计算素数的基准测试（最好的 10 次迭代来预热，给 JIT 编译器一个机会，并排除随机调度延迟，Core 2 Duo T5600 1.83GHz）：
除了非常小的尺寸外，BitSet 比 boolean[] 更节省内存。数组中的每个布尔值都占用一个字节。来自 runtime.freeMemory() 的数字对于 BitSet 来说有点混乱，但更少。
boolean[] 的 CPU 效率更高，除了非常大的尺寸，它们大约是均匀的。例如，对于大小为 100 万的 boolean[] 大约快四倍（例如 6 毫秒对 27 毫秒），对于 10 和 1 亿，它们大约是偶数。
于 2009-03-03T07:41:08.687 回答
22
在这里，您可以看到比较 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";
}
}
于 2018-07-19T11:38:53.697 回答
5
您的问题有点左字段，但如果存储是一个问题，您可能需要研究Huffman compression。例如，00000001可以按频率压缩到等价于{(7)0, (1)1}. 更“随机化”的字符串00111010将需要更复杂的表示，例如{(2)0, (3)1, (1)0, (1)1, (1)0}，并占用更多空间。根据您的位数据的结构，您可能会从它的使用中获得一些存储优势，超越BitSet.
于 2009-03-03T21:42:47.667 回答
4
至于内存， a 的文档BitSet具有非常明确的含义。尤其：
每个位集都有一个当前大小，即该位集当前使用的空间位数。请注意，大小与位集的实现有关，因此它可能会随着实现而改变。位集的长度与位集的逻辑长度相关，并且独立于实现来定义。
Java 库类的源代码是公开的，人们可以很容易地自行检查。尤其：
The internal field corresponding to the serialField "bits".
89
90 private long[] words;
至于速度；这取决于一个人在做什么。一般来说，不要提前考虑速度；使用在语义上最有意义的任何工具，并导致最清晰的代码。仅在观察到未满足性能要求并确定瓶颈后进行优化。
由于许多原因，来到 SO 并询问 A 是否比 B 快是愚蠢的，包括但不限于：
- 这取决于应用程序，通常没有响应的人可以访问该应用程序。在使用它的上下文中对其进行分析和分析。确保它是一个实际上值得优化的瓶颈。
- 像这样询问速度的问题通常表明 OP 认为他们关心效率，但不愿意描述并且没有定义性能要求。在表面之下，这通常是一个危险信号，表明 OP 正朝着错误的方向前进。
我知道这是一个老问题，但最近才出现；我相信这是值得补充的。
于 2013-11-05T12:14:56.973 回答
2
这取决于一如既往。是的，BitSet 的内存效率更高，但是一旦您需要多线程访问 boolean[] 可能是更好的选择。例如，对于计算素数，您只需将布尔值设置为 true，因此您实际上并不需要同步。Hans Boehm写了一些关于此的论文，同样的技术可用于标记图中的节点。
于 2009-03-03T15:16:04.320 回答
0
从 Java 到 CPU 完全是特定于 VM 的。例如，过去布尔值实际上是作为 32 位值实现的（今天很可能是这样）。
除非您知道这很重要，否则最好编写清晰的代码，对其进行分析，然后修复速度缓慢或消耗大量内存的部分。
您可以随时执行此操作。例如，我曾经决定不对字符串调用 .intern() ，因为当我在分析器中运行代码时，它会减慢它的速度（尽管使用的内存更少）。
于 2009-03-03T05:45:54.703 回答
-1
我相信 BitSet 的内存和 CPU 效率更高，它可以在内部将位打包成 int、longs 或本机数据类型，而 boolean[] 需要每个数据位一个字节。此外，如果您要使用其他方法（and、or 等），您会发现 BitSet 更有效，因为不需要遍历数组的每个元素；而是使用按位数学。
于 2009-03-03T05:45:06.610 回答