海量数据取交集、并集-bitmap VS Redis

昨天在《程序的那些事》上看到一个bitmap算法，《漫画：什么是 Bitmap 算法？》非常有意思。

有这样一个需求，一个社交论坛，用户数量在千万级别，每个用户都有不同的标签，而标签的种类有上千种，为了方便找出每一种标签对应的用户，以及共同拥有相同几种标签的人。数据存储结构采用 标签：用ID，例如： 90后: 1,3,5,7.   研究生：3,7,10,30 这样的结构。

但实际运算的时候，只是把1,3,5,7分别把第1位，第3位，第5位，第7位置1，其他位为0，类似于二进制，根据需求进行与、或、异或运算。

假设用户有1000W, 90后：10W个人, 研究生： 100W 个人， 身高超过170：10W;

取出既是90后， 又是研究生的人数：

BitSet Bitmap1 = BitSet.bitmapOf(arr1);
BitSet Bitmap2 = BitSet.bitmapOf(arr2);
BitSet andbitmap = Bitmap1.clone();
andbitmap.and(Bitmap2);

平均时间在100ms左右。

2、换Redis进行测试

使用无序集合，90后为：set-1, 研究生:set-2, 身高超过170:set-3

$res = $redis->sinter("set-1", "set-2", "set-3");

计算结果只花了0.0067s.速度比bitmap更快

bitmap 获取地址：http://mvnrepository.com/artifact/com.googlecode.javaewah/JavaEWAH

GitHub： https://github.com/lemire/javaewah

API：http://www.javadoc.io/doc/com.googlecode.javaewah/JavaEWAH/1.1.6