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

ゝ一世哀愁。 2022-09-11 06:20 153阅读 0赞

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

**位：内存管理的最小单位是字节，一个字节是8个位。**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]  
**有1亿个整数，最大值不超过1亿，问都有哪些元素重复了？谁是第一个重复的？ 内存限制100M**

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

**内存限制100M，不让我们用哈希表，我们用位图算法：**

## 什么是位图算法？ ##

**我们有下面一行数字：**  
![在这里插入图片描述][a168f68d61624d44913219735fa801a3.png]  
![在这里插入图片描述][d38a23e06be542b88419442f1f4b7e60.png]  
![在这里插入图片描述][c484dc39e09744a1a785a0117e945520.png]  
**我们用一个位存储数字是否出现过的状态，那么这几个数字，我们的位图数组需要定义多长呢？**

**我们一般是这样处理：**  
实现我们要找出这组数据的最大的数字19，因为小的值在位图数组里肯定是靠前存放，大的值靠后存放，只要能够保证把最大值的位能够表示出来，前面这些小的值的位必然也可以表现出来。  
**位图数组的长度怎么算呢？**  
假如我们用 char 来定义：一个char类型的元素1字节，一个字节8个位。  
用最大值19除以8加个1  
3个元素。  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 1]

**那么这些数字分别对应有3个元素的位数组的哪个位呢？**  
如果是char类型，就除以/模上8，如果是short，就除以/模上16，如果是int，就除以/模上32

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 2]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 3]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 4]  
**以此类推。**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_14_color_FFFFFF_t_70_g_se_x_16]  
**我们定义好这个位图数组后，我们要做查重。  
我们先遇到7，然后看这个7对应的这个位是0还是1，是0表示还没出现过，是1表示已经出现过。**  
我们要做查重，第一次遇到，设置成1，第二次遇到，发现是1，表示已经出现过了，这个数字是重复的了。  
**如何获取该位的值？**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 5]  
**如何把这个位置置为1？**

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 6]  
**位图算法的优势：**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 7]

## 大数据查重-位图算法代码实现 ##

#include <iostream>
    #include <vector>
    #include <stdlib.h>
    #include <time.h>
    #include <memory>
    using namespace std;
    
    int main()
    {
        
        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 = new int[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;
            }
        }
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 8]

## 变换一下位图算法 ##

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

## 位图算法的缺陷 ##

![在这里插入图片描述][ed03dc25e9ad40fb8fef3fc0c151b4fc.png]

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

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

如果用位图算法：
    int bitmap[1000000000/32+1]  需要内存大小：30M
    
    此时用哈希表才3*4 = 12 * 2 = 24byte

**使用位图算法，推荐的数据序列：数据的个数 >= 序列里面数字的最大值，要相当**

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/f475e707e1a84ae89e1812d76d7ee9b0.png
[a168f68d61624d44913219735fa801a3.png]: /images/20220828/b03449ce17004f20b8e1ef7657462a7a.png
[d38a23e06be542b88419442f1f4b7e60.png]: /images/20220828/e247d7d20e1f4d6db242e520979b516b.png
[c484dc39e09744a1a785a0117e945520.png]: /images/20220828/6411aa5b65774c3493facbc24d900d22.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/410de5ff1c4d4ba2a307f9b334a6fa42.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/7ff6a0471dc0476288a4554b458a81fc.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220828/3bfb45d234aa414b9df02d7d7ba9d7a4.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 4]: /images/20220828/e408e1977d5d4c888990d304793783d5.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_14_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/1a5f6c6bdeb3451e8d7166119fd97ad7.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 5]: /images/20220828/ddc6e84db6b6440684f975d5d63a4ee1.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 6]: /images/20220828/78fbb2dde2db4f67be6378ae7213253f.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 7]: /images/20220828/320fc073a082415ebbcd8ca1a0d37c44.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 8]: /images/20220828/c390113f3386423d883564370ba3be18.png
[ed03dc25e9ad40fb8fef3fc0c151b4fc.png]: /images/20220828/cb97ff1321aa4cb6901e83bada28bef8.png