bitmap位图 | 你泪如梨花洒满了纸上的天下
Cobb 653 1

为什么使用位图?

bitmap 位图 《= 大数据查重 现在有10亿个整数,让你找出都有哪些数字重复了,数字的最大值不超过1千W 一组数据 23 4 67 89 21 32 43 5 67 89 23 67 78

int arr[10亿]; 10亿 * 4 = 40亿 3.8G的内存才够!!! 23 4 67 89 21 32 43 5 1000 0000 int:32位 int arr[1000 0000 / 32 + 1]; 4 * 1.2M的内存足够!!!

0000 0000 0000 0000 0010 0000 0000 0000 0000 0001 0000 0000 0123 4567 891011

下标:arr[78 / 32] 2 0:32 1:32 2:32 具体位置:78%32 = 14 78在数组arr的2号位元素的第14位

位图分析

问题: 将30亿个int变量查重!!!

使用环境: 最大的优点是: 节省内存空间 如果将40亿个int变量完全存储到内存中,所占内存非常大的,不可接受 使用位图,所占内存是可以接受的

位图思想: 就是用每一 位 来存放某种状态,0和1,有和无,适用于大规模数据,但数据状态又不是很多的情况。通常是用来判断某个数据存不存在的,,也就是数据查重

算法原理: 遍历数组( 巨大的个数量),以数组元素排布为顺序,分别将bitmap中对应的位 置1,并且检查其是否已经为1,若为1,即为重复的元素。

实现过程: 按照一定的规模,创建位图 (和实际数组 位数 对应) 32 < i < 64, 1 要移位对比(选择一个最大的整数,转换成相应的字节,字节要多加一个 int,32位,避免位图不完整,读出出现错误)(选择最大的值,因为要把这个数,放到位图的相应位置。) 遍历数组,将位图中对应的位 置1,并检查其是否已经为1,若为1,即为重复的元素。 */

#include <iostream>
#include <string.h>
#include <stdio.h>

int main()
{
    // 原始的数据    234
    int arr[] = { 12,78,234,89,12,90,78,23 };

    // 查出重复的数字打印出来
    // 1. 先定义位图数组,按照一定的规模,创建位图, 没有除尽,最后位数会少,所以要加一个int
    int bitmap[234 / 32 + 1] = { 0 };

    // 2. 一边遍历原始的数据,一遍判断
    for (int i = 0; i < sizeof arr / sizeof arr[0]; i++)
    {
        // arr[i]  0000 0000 0000 0000 0000 0000 0000 0000
        int index = arr[i] / 32;  // 定位行     1个 int 是32 位
        int offset = arr[i] % 32; // 这一行的第几个位

        // 如果定位的这个位为空
        // 这里&运算,要加上括号,否则因为运算符优先级问题导致出错。
        if ((bitmap[index] & (1 << offset)) == 0)
        {
            // 把相应的位置1
            bitmap[index] |= 1 << offset;
        }
        else
        {
            printf("%d 数字重复出现\n", arr[i]);
            // std::cout << arr[i] <<"数字重复出现" << std::endl;
        }
    }

}

代码实现

评论区

索引目录