我有一个位集，我用它来跟踪一个项目是否存在，例如
b = 0110011万
则表示第2和第3项存在，而第1和第4项不存在。
在寻找可以优化这个位集数组的库时，我遇到了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值运行这个的时候
| 探测字节|位集字节|咆哮位图字节|
| - ------|- ------|- ------|
| 千分之一|小行星5056|二百八十八|
| 0.01 |小行星5056|九四四|
| 0.1 |小行星5056|小行星7872|
| 0.999|小行星5056|小行星65616|
如果您看到我们插入的数字越来越多，那么RoaringBitmap的内存占用量也在增加。
1.这是预期的吗？
1.在最坏的情况下，它不应该仅仅退回到基于位集的实现吗？
- 0.999能不能被当作0.001的倒数，然后我们就能把它存储在288字节里？
1.当我们进行内部服务调用并使用jackson库（而不是基于字节的序列化库）时，将这些位集表示为字符串的最佳方式是什么？
2条答案
按热度按时间jobtbby31#
这似乎是当条目数很小时的情况，但随着条目数的增加，差异变得不那么明显。虽然这没有得到lib作者的证实（我询问了here，并跟踪了here）
| 探针|条目数|位集位|咆哮位图位|节省百分比|
| - ------|- ------|- ------|- ------|- ------|
| 千分之一|五万|小行星50048|九二八|九十八|
| 0.01 |五万|小行星50048|小行星7744|八十四|
| 0.1 |五万|小行星50048|小行星65616|-31|
| 0.999|五万|小行星50048|65616〈-注意，它不会增加|-31|
| 千分之一|五十万|小行星500032|小行星8704|九十八|
| 0.01 |五十万|小行星500032|小行星80720|八十三|
| 0.1 |五十万|小行星500032|小行星524480|-4个|
| 0.999|五十万|小行星500032|524480〈-注意，它不会增加|-4个|
| 千分之一|五亿|五亿|小行星835232|九十八|
| 0.01 |五亿|五亿|小行星8036368|八十三|
| 0.1 |五亿|五亿|小行星5001| -0.03 |
| 0.999|五亿|五亿|50016240〈-注意，它不会增加| -0.03 |
看这个，似乎随着条目数量的增长，他们可能只在幕后使用位图。注意不要盲目使用库，测试你的用例。
whlutmcx2#
Roaring Bitmap格式有一个公共规范：
https://github.com/RoaringBitmap/RoaringFormatSpec
内存的使用只是影响应用程序性能的一个因素，高速位图在提供经济的存储空间的同时，也能在实际应用中提供高性能。
在[0，x）中给定N个整数，则Roaring位图的以字节为单位的序列化大小不应超过此界限：
8 + 9 *（（长）x+65535）/65536 + 2 * N
也就是说，给定Universe大小（x）的固定开销，Roaring位图使用的每个整数永远不会超过2个字节。
没有一种数据结构总是理想的。您应该确保Roaring位图适合您的应用程序配置文件。至少在两种情况下，Roaring位图可以很容易地被上级的压缩方式替代：
在一个较大的区间内几乎没有随机值（即，您有一个非常稀疏的集合）。例如，以集合0、65536、131072、196608、262144...为例，如果这是您的应用程序的典型情况，则可以考虑使用散列集或简单排序数组。
你有一个密集的随机值集，这些随机值从来不会形成连续值的游程。例如，考虑集合0，2，4，...，10000。如果这是你的应用程序的典型情况，那么使用传统的位集可能会更好。