我有一个位集合(bitset)，用来跟踪物品是否存在，例如：
b = 01100110000
它代表第二个和第三个物品存在，而第一个和第四个物品不存在。
在寻找能够优化这个位集合数组的库时，我发现了非常令人兴奋的Roaring bitmaps。
我做了一个快速测试：
public static void main(String[] args) throws IOException {
RoaringBitmap roaringBitMap = new RoaringBitmap();
BitSet bitSet = new BitSet(5000);
double prob = 0.001;
Random random = new Random();
for (int i = 0; i < 5000; i++) {
if (random.nextDouble() < prob) {
bitSet.set(i);
roaringBitMap.add(i);
}
}
System.out.println(bitSet.cardinality());
System.out.println("bitset bytes: "+ bitSet.size());
System.out.println("RoaringBitmap bytes: " + roaringBitMap.getSizeInBytes() * 8);
}
基本上我们设置了一些值并检查数据结构的总大小。
当我们使用多个prob值运行时，我得到了:
| prob byte | bitset bytes | RoaringBitmap bytes |
|---|---|---|
| 0.001 | 5056 | 288 |
| 0.01 | 5056 | 944 |
| 0.1 | 5056 | 7872 |
| 0.999 | 5056 | 65616 |
如果您观察到随着插入更多数字，RoaringBitmap的内存占用增加。
- 这是预期的吗？
- 在最坏的情况下，它不应该只回退到基于位集的实现吗？
- 不能将0.999视为0.001的反向，并将其存储在288个字节中吗？
- 在进行服务间调用并使用jackson库（但不是基于字节的序列化库）时，表示这些位集的字符串的最优方式是什么？
add到底在做什么。它 可能 像调用StringBuilder.append一样，其中存储分配跳跃的因子不是一。似乎没有RoaringBitmap可以为有限数量的字节创建位图。至于String的事情，提醒您，对于我来说，BitSet的每个位的可视化压缩到 69 字节。 - g00se