我有一个位集合(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