用BitMap结构实现快速取差集

本文主要是介绍用BitMap结构实现快速取差集，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在流式计算对比基线无数据告警场景中，利用基线数据对比来源数据，如果发现该时间窗口内的数据不在基线数据中则产生告警，因此基线数据和来源数据需要进行对比计算，基线数据去掉来源数据中已有的数据，余下的数据作为产生的告警数据。在数据量较小时直接进行集合运算取差集即可，但是但基线数据和来源数据量达百万甚至千万时则计算缓慢，出现延时，因此需要找到其它方式方法。

基线数据的定义：
基线数据是一组带时分的时序数据，时分是根据配置对24小时进行分割得到，比如配置1分钟内没数据则告警，则24小时按1分钟进行分割，则分割成00:01, 00:02…的时序数据,总共1440条记录，1440条表示每个1分钟窗口内有一条数据。配置5分钟内没数据则告警，则按5分钟进行分割，则分割成00:05, 00:10…的时序数据,每个时间窗口内有且仅有一条数据。每个任务对应一组基线数据。

假设基线数据量为一百万条，窗口内来源数据为九十九万九千条，基线数据中移除来源数据即取差集后则只有一千条。

2.1 集合的取差集方法
1）List.removeAll(sublist)方法取差集

private static void testRemoveAll() {List<String> listA = new ArrayList<>();for(int i=0;i<OneMillion;i++){ //随机创建百万条基线数据String key1="ip(192.168.199.10"+i+")#port("+i+")#service_name(orcl)#time(23:30:00)"+i;listA.add(key1);}//从百万条基线数据中随机获取九十九万九千条作为来源数据List<String> listB = createRandomList(listA,999000);Date date = new Date();listA.removeAll(listB);Date date1 = new Date();System.out.println("testRemoveAll:"+(date1.getTime()-date.getTime())/1000+"秒");System.out.println(listA.size());
}

测试结果：
30分钟未计算出结果，手动kill程序。

2）List.removeAll(new HashSet(sublist))方法取差集
分析removeAll方法的源码，发现removeAll方法中有subList.contain(value)的方法，如果subList为list集合，则调用indexOf()方法，一个一个地遍历查找。最坏时间复杂度为O(总数据量)。如果先将subList转为HashSet，在调用contain方法时，则时间复杂度为O(1)，加快对比计算速度。

private static void testRemoveAll() {List<String> listA = new ArrayList<>();for(int i=0;i<OneMillion;i++){ //随机创建百万条基线数据String key1="ip(192.168.xxx.10"+i+")#port("+i+")#service_name(orcl)#time(23:30:00)"+i;listA.add(key1);}//从百万条基线数据中随机获取九十九万九千条作为来源数据List<String> listB = createRandomList(listA,999000);Date date = new Date();//listA.removeAll(listB);listA.removeAll(new HashSet(listB));Date date1 = new Date();System.out.println("testRemoveAll:"+(date1.getTime()-date.getTime())/1000+"秒");System.out.println(listA.size());
}
//0.3秒

测试结果：
计算耗时仅0.3s，这个结果相比上一步有巨大提升。

2.2 BitMap的取差集方法
BitMap，直译为位图，是一种数据结构，代表了有限域中的稠集（Dense Set），每一个元素至少出现一次，没有其他的数据和元素相关联。在索引，数据压缩等方面有广泛应用。
计算机中1 byte = 8 bit，一个比特（bit，称为比特或者位）可以表示1或者0两种值，通过一个比特去标记某个元素的值，而KEY或者INDEX就是该元素，构成一张映射关系图。因为采用了Bit作为底层存储数据的单位，所以可以极大地节省存储空间。同时还支持去重，交集，差集等各种运算Bitmap的实现有很多，例如Java原生的BitSet，第三方的RoaingBitmap等。

1）Java原生的BitSet

private static void testBitSet() {List<String> listA = new ArrayList<>();BitSet bitmap = new BitSet();for(int i=0;i<OneMillion;i++){String key1="ip(192.168.XXX.10"+i+")#port("+i+")#service_name(orcl)#time(23:30:00)"+i;bitmap.set(Math.abs(key1.hashCode()));listA.add(key1);}BitSet bitmap1 = new BitSet();List<String> listB = createRandomList(listA,999000);for(String s:listB){bitmap1.set(Math.abs(s.hashCode()));}Date date = new Date();bitmap.andNot(bitmap1);Date date1 = new Date();System.out.println("testBitSet:"+(double)(date1.getTime()-date.getTime())/1000+"秒");
}
//testBitSet:0.02秒

测试结果：
计算耗时仅0.02s，这个结果相比上一步时间缩短一个数量级。
2）RoaingBitmap
Bitmap的主要缺陷是占用大量的内存空间。Bitmap是一种使用位图来表示数据集合的数据结构，每个位代表一个元素的存在与否。当数据集合很大时，Bitmap需要使用大量的位来表示，导致内存占用较高。
RoaringBitmap是一种改进的Bitmap数据结构，它能够解决Bitmap的内存占用问题。RoaringBitmap使用了一种压缩算法，能够有效地压缩位图数据，减少内存占用。具体来说，RoaringBitmap将位图分成多个块，每个块使用不同的压缩算法进行压缩。这样，当数据集合中存在大量连续的元素时，RoaringBitmap能够更好地压缩数据，减少内存占用。另外，RoaringBitmap还支持快速的位图操作，如并集、交集和差集等，使得对数据集合的操作更加高效。RoaringBitmap还支持动态增长，可以动态地添加和删除元素，而不需要重新分配内存。
总的来说，RoaringBitmap通过压缩算法和优化的位图操作，能够有效地解决Bitmap的内存占用问题，提高了位图数据结构的性能和可扩展性。

private static void testRoaringBitmap() {List<String> listA = new ArrayList<>();RoaringBitmap bitmap = new RoaringBitmap();for(int i=0;i<OneMillion;i++){String key1="ip(192.168.xxx.10"+i+")#port("+i+")#service_name(orcl)#time(23:30:00)"+i;bitmap.add(Math.abs(key1.hashCode()));listA.add(key1);}RoaringBitmap bitmap1 = new RoaringBitmap();List<String> listB = createRandomList(listA,999000);for(String s:listB){bitmap1.add(Math.abs(s.hashCode()));}Date date = new Date();bitmap.andNot(bitmap1);Date date1 = new Date();System.out.println("testRoaringBitmap:"+(double)(date1.getTime()-date.getTime())/1000+"秒");
}
//testRoaringBitmap:0.022秒

测试结果：
计算耗时仅0.022s，这个结果和Java原生的BitSet时间基本相同。
总 结：
通过上述测试对比，相比其它方式采用BitMap和升级的RoaingBitmap在时间上能缩小一个数量级，效果十分明显，但是使用BitMap和RoaingBitmap存在的问题是BitMap结构只支持数字，如果是字符串需要先将字符串转成数字，字符串转数字时有一定的概率出现hash碰撞（不同的字符串转成相同的数字），因此如果能允许一定的误差，用Bitmap和RoaingBitmap是最快的。

这篇关于用BitMap结构实现快速取差集的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---