【《漫画算法》笔记】位图算法

2023-12-18 23:37:19

问题描述

现有一个商店的数据库,它存储了很多顾客的信息(如:姓名、年龄、身高、体重、职业等等,总之很多项)。
如果想要筛选出“年龄大于25,且身高大于170,且体重大于130,且职业是程序员”的顾客,应该怎么做呢?

可能的解题思路

解答1:使用SQL,但局限在于,当标签很多时,需要的SQL语句会很长;多个用户群做并集时,会有大量的去重操作,从而拖慢计算速度。
解答2:使用位图,举例如下,假设有5个顾客,分别是 顾客0、顾客1、顾客2、顾客3、顾客4;
“年龄大于25”的顾客有 顾客0、顾客1,那么对应的位图是bitmap1= 1,1,0,0,0;
“身高大于170”的顾客有 顾客2、顾客3,那么对应的位图是bitmap2= 0,0,1,1,0;
那么,“年龄大于25,且身高大于170”的位图 bitmap3=bitmap1&bitmap2=0,0,0,0,0,也就是,没有人。
如果找“年龄不大于25,且身高大于170”的顾客,可以先计算它的位图 bitmap4=(~bitmap1)&bitmap2=0,0,1,1,0,也就是,顾客2、顾客3 满足此条件。

位图的定义

“内存中连续的二进制位所组成的数据结构,该算法主要用于大量整数的去重和查询”。

代码

public class Bitmap {
    private long[] words;// every long number is a 64-bit Binary number
    private int size; // Bitmap的位数大小

    public Bitmap(int size){
        this.size=size;
        this.words=new long[getWordIndex(size-1)+1];
    }

    public boolean getBit(int bitIndex){
        if(bitIndex<0||bitIndex>size-1){
            throw new IndexOutOfBoundsException("超过BitMap有效范围");
        }
        int wordIndex=getWordIndex(bitIndex);
        return (words[wordIndex]&(1<<bitIndex))!=0;
    }

    public void setBit(int bitIndex){
        if(bitIndex<0||bitIndex>size-1){
            throw new IndexOutOfBoundsException("exceeds the range of BitMap");
        }
        int wordIndex=getWordIndex(bitIndex);
        words[wordIndex]|=(1<<bitIndex);// 把对应位修改成1
    }

    private int getWordIndex(int bitIndex) {
        return bitIndex>>6;// 向右移6位,相当于÷64。因为long型数值是64bit。在long型数组中,找bitIndex对应的long型元素
    }

    public static void main(String[] args){
        Bitmap bitMap=new Bitmap(128);// 表面上,制造了128个取值为0或1的位子。但实际上这128个位子是用long型数值拼起来的,拼成long[] words
        bitMap.setBit(126);// 设置第126位为1。在实际设置时,在words找到对应的long型数值,再找到对应的位子更新为1
        bitMap.setBit(75);
        System.out.println(bitMap.getBit(126));
        System.out.println(bitMap.getBit(78));
        System.out.println(bitMap.getBit(75));
    }


}

文章来源:https://blog.csdn.net/qq_43448491/article/details/135071770
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。