漫游位图使用比普通位集更多的存储空间

Question

我有一个位集，我正在使用它来跟踪项目是否存在示例

b=01100110000

它表示第2和第3项存在，而第1和第4项不存在。

在搜索可以优化此位集数组的库时。我偶然发现了Roaring位图，这听起来非常令人兴奋。

我用它做了一个快速测试，

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值运行这个时。我有

漫游位图字节/thead>

prob字节	位集字节
0.001	5056	288
0.01	5056	944
0.1	5056	7872
0.999	5056	65616

当条目数量较少时，情况似乎就是这样，但随着条目数量的增加，差异变得不那么明显。虽然没有得到lib作者的证实(我在这里询问并在这里跟进)

漫游位图位>td>65616<-注意：它不会增加83

	问题	条目数	位集位	节省%
0.001	50000	50048	928	98
0.01	50000	50048	7744	84
0.1	50000	50048	65616	-31
0.999	50000	50048	-31
0.001	500000	500032	8704	98
0.01	500000	500032	80720
0.1	500000	500032	524480	-4
0.999	500000	500032	524480<-注意：它不会增加	-4
0.001	50000000	50000000	835232	98
0.01	50000000	500000000	8036368	83
0.1	50000000	50000000	50016240	-0.03
0.999	50000000	50000000	50016240<-注意：它不会增加	-0.03

漫游位图格式有一个公共规范：

https://github.com/RoaringBitmap/RoaringFormatSpec

内存使用率只是应用程序性能的一个因素。漫游位图寻求提供经济的存储，同时在现实世界的应用程序中提供高性能。

给定[0，x)中的N个整数，则Roaring位图的序列化大小(以字节为单位)不应超过此界限：

8+9*((长)x+65535)/65536+2*N

也就是说，给定universe大小(x)的固定开销，漫游位图使用的每个整数永远不会超过2个字节。

没有什么数据结构总是理想的。您应该确保漫游位图适合您的应用程序配置文件。至少有两种情况下，漫游位图可以很容易地被压缩方面的高级替代方案取代：

在一个大的区间中有几个随机值(即，你有一个非常稀疏的集合)。例如，取集合0、65536、131072、196608、262144。。。如果这是典型的应用程序，您可以考虑使用哈希集或简单排序的数组。

您有一组密集的随机值，这些值永远不会形成连续值的运行。例如，考虑集合0,2,4，。。。，如果这是典型的应用程序，那么使用传统的位集可能会更好。

关于Roaring的相关参考

• Daniel Lemire，Owen Kaser，Nathan Kurz，Luca Deri，Chris O'Hara，François Saint-Jacques，Gregory Ssi Yan Kai，Roaring Bitmaps:优化软件库的实现，软件：实践与经验第48卷，2018年4月4日第867-895页
• Samy Chambi、Daniel Lemire、Owen Kaser、Robert Godin，Roaring位图具有更好的位图性能，软件：实践与经验第46卷第5期，第709–719页，2016年5月
• Daniel Lemire，Gregory Ssi Yan Kai，Owen Kaser，Roaring持续更快更小的压缩位图，软件：实践与经验第46卷第11期，第1547-1569页，2016年11月
• Samy Chambi，Daniel Lemire，Robert Godin，Kamel Boukhalfa，Charles Allen，Fangjin Yang，用咆哮位图优化德鲁伊，IDEAS 20162016

RoaringBitmap有三种类型的容器，在我们的场景中，我们主要使用BitmapContainer。每个BitmapContainer可以存储65535个元素，占用8k的内存。然而，存储器是根据高16位和低16位来划分的。基于高16位来选择相应的桶。如果对应的bucket不存在(元素范围差为65535)，则它将被存储在新的bucket中。在数据过于稀疏的情况下，这可能会导致许多存储桶没有填满，从而导致一些冗余内存。在某些情况下，这可能会导致RoaringBitmap比常规位图使用更多的内存。如果稀疏数据的范围差为65535或元素数量较小，则它将使用比位图更少的内存。它最大的优点是不需要根据最大偏移量来分配空间。