数组/集合压缩技术

一个数据可能关联了多个年级,一般的做法是建一个年级关联表。数据为
data_key gradeId
1            1
1            3
2            1
这样的。但还有一种做法是把多个年级压缩为一个字段,不同值表示不同年级的组合。
压缩函数:
Integer zip(List gradeIds){
    int zip=0;
    for(Integer gradeId:gradeIds){
        zip+=Math.pow(2,gradeId);
    }
    return zip;
    
}
检查是否包含函数:
public boolean existGrade(Long gradeId,Integer gradeIds){
    if(gradeId ==null) {
        return false;
    }
    int g = (int)Math.pow(2,gradeId.intValue());
    if((g & gradeIds) ==g) return true;
    return false;

}

这里扩展一下按位与的运算”(g & gradeIds)==g“,表示gradeIds里包含g。为什么是这样算的?首先,g是2的n次,这个数在二进制形式上是一定是第1位为1,后面全是0,如1000. 其次,gradeIds的值是多个2的n(n>=1)次方的和,二制进形式没有明显规律。最后,按位与(&)的二进制性质有什么,0与任何数与都是0,1与1按位与才会得到1。 那么,也可以这么写(g&gradeIds)!=0 。为什么?因为g除了第1位,别的位按位与的结果已经确定,都是0。而第1位,与之对应的gradeIds的所在位有两种可能,一种是1,另一种是0。就是说最后的结果只会有两种可能,要么是10000(g),要么是00000(0)。



这种方法,适合多少个数据以内的压缩?
log2(N)=Integer.MAX_VALUE
n=Math.log(Integer.MAX_VALUE)/Math.log(2)
30个以内的数都可以用这种方法。当然,用long的话,可以再扩点。


数据多时可以用布隆过滤器(BloomFilter),先把原始数据压缩到一个大的数里,比如Integer可以容纳20亿数,那么就对应了20亿个原始数据。
再后数据来了,要判断是否存在,先计算它映射击的数,如果这个数存在(可用二进制的位与计算),那么可能存在此原始数据。如果数不存在,那么原始数据一定不存在。
文/中中 浏览次数:0次   2019-11-08 15:29:33

相关阅读

微信扫描-捐赠支持
加入QQ群-技术交流

评论: