160-大数据查重-位图算法

大数据查重-位图算法

位： 内存管理的最小单位是字节，一个字节是8个位。

问题： 有1亿个整数，最大值不超过1亿，问都有哪些元素重复了？谁是第一个重复的？ 内存限制100M

1亿 =100M
如果是放到哈希表上：100M *4=400M *2=800M

1、什么是位图算法？

我们有下面一行数字：



我们用一个位存储数字是否出现过的状态，那么这几个数字，我们的位图数组需要定义多长呢？
处理方法：

• 我们要找出这组数据的最大的数字19；
• 因为小的值在位图数组里肯定是靠前存放，大的值靠后存放，只要能够保证把最大值的位能够表示出来，前面这些小的值的位必然也可以表现出来。

位图数组的长度怎么算呢？
假如我们用 char 来定义：一个char类型的元素1字节，一个字节8个位。
用最大值19除以8加个1，数组长度为3。

那么这些数字分别对应有3个元素的位数组的哪个位呢？

• 如果是char类型，就除以/模上8，如果是short，就除以/模上16，如果是int，就除以/模上32

元素8在1号位的第0位上！

15在1号位的第7位，后面数据以此类推。

我们定义好这个位图数组后

查重运算：

• 我们先遇到7，然后看这个7对应的这个位是0还是1，是0表示还没出现过，是1表示已经出现过。
• 我们要做查重，第一次遇到，设置成1，第二次遇到，发现是1，表示已经出现过了，这个数字是重复的了。

位操作：

• 与(‘&’)： 取值
• 或(‘|’)： 赋值

2、如何把位图上对应位置置为1？

bitmap[index] | (1 << offset)

，再将这个值赋给

bitmap[index]

3、如何获取该位的值？

bitmap[index] & (1 << offset)

以7位例：

• index= 0，offset = 7；
• 此时构建好的位图bitmap[0] = 1000 0000;
• 我们运用上面式子：1000 0000 & 100 0000 = 1，对应位的中为1。

4、位图算法的优势

位图算法代码实现

#include<iostream>#include<vector>#include<stdlib.h>#include<time.h>#include<memory>usingnamespace std;intmain(){
    vector<int> vec{12,78,90,78,123,8,9,90};//定义位图数组int max = vec[0];for(int i =1; i < vec.size(); i++)//O(n){if(vec[i]> max)
            max = vec[i];}int* bitmap =newint[max /32+1]();//int是32个位，new把所有元素初始化为0 
    unique_ptr<int>ptr(bitmap);//为了可以自动释放内存 //找第一个重复出现的数字for(auto key : vec){int index = key /32;int offset = key %32;//取key对应的位的值if(0==(bitmap[index]&(1<< offset)))//0表示key没有出现过{
            bitmap[index]|=(1<< offset);//把当前位记为1 }else{//cout << key << "是第一个重复出现的数字" << endl;//return 0;
            cout << key <<"重复出现过!"<< endl;}}return0;}

可以看到8、9、12都放在了bitmap[0]中

变换一下位图算法

找谁是第一个不重复的？

• (用2个位保存数据的状态)
• 2的2次方：4个值了
• 我们只需要记录1和2就可以了。
• 先把所有的元素往位图数组上放1遍，判断，不存在的话，置为1，如果发现是1，就置为2。
• 第一个不重复的安装位图数组的顺序去找第一个位是1的值，就是第一个不重复的数字。

位图算法的缺陷

• 位图法有一个很大的缺点，就是数据没有多少，但是最大值却很大，比如有10个整数，最大值是10亿，那么就得按10亿这个数字计算开辟位图数组的大小，太浪费内存空间。

int的上限值是20亿    unsignedint的上限值是40亿

现在有3个值，1,3，10亿

如果用位图算法：
int bitmap[1000000000/32+1]  需要内存大小：30M

此时用哈希表才3*4=12*2=24byte

**使用位图算法，推荐的数据序列：

数据的个数 >= 序列里面数字的最大值

，要相当**