【数据结构取经之路】位图全解

2024-09-01 15:44
文章标签 数据结构 位图 全解 取经

本文主要是介绍【数据结构取经之路】位图全解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

前言

C++标准库里的位图

位图的设计及实现

位图几个关键接口的实现

set()

reset()

test()

 完整代码

位图的使用场景

位图的优缺点

位图的使用演示 —— 几道面试题的讲解

前言

位图（Bitmap）是一种非常高效的数据结构，主要用于处理大量数据的快速查找、去重等操作。它利用每一位（bit）来表示某个元素是否存在或某种状态，从而极大地节省了存储空间。在内存和存储空间相对受限的环境下，位图尤其有用。下面，我们先瞅一眼C++标准库里的位图，然后再抽出它的核心部分来自己实现。

C++标准库里的位图

template <size_t N> class bitset;

可以看到，bitset是一个类模板，顺便提一下，在一些地方位图也叫bitmap。下面来看一下它的操作。

b.any()b中是否存在置位的二进制位
b.all()b中所有位都置位了吗
b.none()b中不存在置位的二进制位吗
b.count()b中置位的位数
b.test(pos)若pos位置是置位的，则返回true，否则返回false
b.set(pos)将pos位置进行置位
b.reset(pos)将pos位置置为0（false）或者说将pos位置复位
b[pos]访问b中pos位置的位，即直接访问二进制位

以上就是部分bitset的操作了。其中，最核心的是set()、test()、reset()。

这里提一下，C++库中的位图并不是开在堆上的，所以当需要开很大的空间时，它会崩，解决方案是把位图整体开到堆上来，这里演示一下。

std::bitset<UINT_MAX> bs;//error
std::bitset<UINT_MAX>* pbs = new std::bitset<UINT_MAX>;//ok

下面我们开始着手位图的实现。

位图的设计及实现

位图的本质是一个直接地址法的哈希表，直接将整形映射到它所对应的比特位上。但是，遗憾的是C/C++中并没有能直接控制比特位的类型。所以我们只能对char/int等这样的整形通过位运算去控制相应的比特位。举个例子，在32为机器下，整型int的大小为4个字节，一共32个比特位。这32个比特位就可以被32个整型映射。有一个整型值x，下面是计算出x所对应的比特位的步骤。

1）i = x / 32; //这一步是计算出x对应的第几个整型

2）j = x % 32; //这一步是计算出x在第i个整型中对应第几个比特位

 下面，我假设 x = 20，然后计算出20所对应的二进制位。

i = x / 32 -> i = 20 / 32 -> i = 0 -> 可知 x 对应的是第0个int

j = x % 32 -> j = 20 % 32 -> j = 20 -> 可知 x 对应的是第0个int的第20个二进制位

x 映射的二进制位大概就是上图用红色三角形标记的位置。

 还有一个值得注意的细节，因为映射是直接按大小映射的，所以我们要按数据的范围开空间。例如有这样一个数组 {1，23，34，45}；我们不能仅仅只开4个二进制位，我们要根据数据范围开，也就是说，至少要开46个二进制位（0~45）。有了一定的认识之后，下面我们开始实现位图的几个关键接口。

位图几个关键接口的实现

我们以vector为位图的底层，接下来我们将分别实现set()、reset()、test()这三个接口。

set()

把x映射的位标记为1。

上面我们已经知道了如何定位x映射的二进制位，接下来我们探讨如何将x对应的二进制位标记为1。

假设上图中上方数字串中被标记为红的0是x要映射的位。我们发现，当上方数字串或上下方数字串时，x要映射的位就置为1了，并且上方数字串中的其余位数不受影响，如果原来是0，那么或运算了之后还是0，如果原来是1，或运算之后还是1。这样就达到了我们的目的了，但问题来了，下方的数字串是如何得到的呢？其实也很简单，我们只需要将1左移 j 位 即可得到下方的数字串，然后拿该串去与对应的第 i 个整型进行或运算就达到目的了。

void set(size_t x)
{size_t i = x / 32;size_t j = x % 32;_bs[i] |= (1 << j);
}

reset()

把x映射的位标记为0。

我们发现，当上方的数字串与下方的数字串进行与(&)运算后，x映射的位置上原来的1被置成了0。同时，上方数字串中的其余位上，如果原来是0，那么进行与运算后还是0，如果原来是1，进行与运算后还是1，即其余位保持不变。现在，关键问题是如何拿到下方的数字串。其实，我们只需将set()中的数字串 0000 0000 0010 0000 ... 0000进行按位取反即可 。总结一下：将1左移 j 位后，对其左移的结果进行按位取反，然后在拿按位取反的结果去和第 i 个整形进行与运算。

//将x映射的位标记为0
void reset(size_t x)
{size_t i = x / 32;size_t j = x % 32;_bs[i] &= (~(1 << j));
}

test()

如果x对应的映射位置为1，则返回true，否则返回false。

假设上方数字串中被标记的0为x映射的位置。

我们发现，将上方的数字串与下方的数字串进行与运算，其结果是0，正好得到x映射的位置的值。我们知道，在进行与运算时，只有都是1与的结果才是1，而下方数字串中，除了红色的1以外，其余全为0，所以与运算的结果仅取决于x映射的位置的值是1还是0。如果x映射的位置的值是0，那么与的结果就是0，如果x映射的位置的值是1，那么与的结果为非0。下方的数字串如何得到上面已经提到过，就是将1左移 j 位即可。和上面两个函数不同的是，这里并不需要改变x映射的二进制位的值，只想知道是多少，所以就不能像reset()那样用 &= 了，与运算之后把结果返回就行了。

//如果x映射的二进制位为1，
//则返回true，否则放回false
bool test(size_t x)
{size_t i = x / 32;size_t j = x % 32;return _bs[i] & (1 << j);
}

 完整代码

#pragma once
#include <vector>namespace pcz
{template <size_t N>class bitset{public:bitset() { _bs.resize(N / 32 + 1, 0); } //开空间//将x映射的位标记为1void set(size_t x){size_t i = x / 32;size_t j = x % 32;_bs[i] |= (1 << j);}//将x映射的位标记为0void reset(size_t x){size_t i = x / 32;size_t j = x % 32;_bs[i] &= (~(1 << j));}//如果x映射的二进制位为1，//则返回true，否则放回falsebool test(size_t x){size_t i = x / 32;size_t j = x % 32;return _bs[i] & (1 << j);}private:std::vector<size_t> _bs;};
}

位图的使用场景

位图的使用场景其实在前言部分有提到了，为了文章结构的完整性，我在这里再总结一下~

位图主要用于在大量数据中，判断某个元素是否存在。举个例子：在一个集合中，有40亿个无符号整数，未排序。给你一个无符号整数，如何快速判断这个数是否在这40亿个无符号整数中(腾讯\百度等公司出过的面试题)。在这种场景下，就非常适合使用位图了。这个例子中的问题会在下文演示位图的使用时模拟解决这个问题。

位图的优缺点

1）优点：可以快速判断一个元素是否在一个大的集合中，节省空间。

2）缺点：只适用于整型。

位图的使用演示 —— 几道面试题的讲解

1）一个集合中，有40亿个无符号整数，未排序。给你一个无符号整数，如何快速判断这个数是否在这40亿个无符号整数中(腾讯\百度等公司出过的面试题)。

思路一：暴力查找 —— 直接遍历一遍数据，时间复杂度为O(N)。

思路二：排序 + 二分查找 —— 时间复杂度为O(N*logN) + O(logN)。

思路三：位图。

接下来我们分析以上三种方法的可行性。

首先，第一种方法，效率太低了，弃用。

其次，针对第二种方法，我们先来算一算40亿个整型大概需要多少内存(二分查找是在内存中进行的，磁盘上不行)。1G = 1024MB = 1024 * 1024KB = 1024 * 1024 * 1024Byte ≈ 10亿Byte。一个整型4个字节，40亿个整型需要：40亿 * 4 = 160亿Byte，即 160亿 / 10亿 = 16G。16个G的数据是无法放到内存中的，只能存在磁盘里，但是二分查找只能对内存数组中的有序数据进行查找。所以第二种方法也是不可行的。

最后，我们来看看位图是如何解决这个问题的。判断一个整型是否在给定的整型数据集合中，结果只有两种——在或者不在。这两种状态正好可以用一个二进制位来表示(一个二进制位可以表示0也可以表示1)，0表示给定数据不在40亿个整型数据中，1表示给定数据在40亿个整型数据中。我们只需要把这40亿个数据全部映射到位图中(set())，再test()即可。

看到这，你可能会有疑问——这40亿个数据放到位图中需要多少空间，它们能成功的映射到位图上吗？下面我们算一算。       

40亿个数据需要的二进制位：40亿个二进制位（每一个整型映射一个二进制位）

40亿个二进制位占用的字节数：40亿 / 8 = 5亿Byte（1Byte = 8 bit）

1G ≈ 10亿Byte   --->   5亿Byte ≈ 0.5G即500兆左右，堆上的空间完全够用（我们的位图底层为vector，vector在堆上开空间）

 方法三的可行性已得到验证，下面我们模拟解决一下这个问题。这里解释一下，所谓模拟解决就是不真的从40亿个数中判断某个数是否存在，而是我们造一组数据出来，然后通过我们写的程序判断某个元素是否在该组数据中，减少了数据量，但方法不变。

void TestBitSet()
{int arr[] = { 1, 2, 12, 5, 8, 9, 31, 21, 22, 10, 42 };pcz::bitset<45> bs;			//根据数据范围开空间for (auto val : arr){bs.set(val);			//将数组中的元素全部映射到位图中}cout << bs.test(11) << endl;//判断11是否在数组中，预计结果为false，即输出0
}

                      

2）一个文件有100亿个整数，我们只有1G内存，设计算法找到出现次数不超过2次的所有整数。 

这道题是上一题的进阶版本，接下来我们思考一下如何解决这个问题。

我们的位图中，每一个整数映射到一个二进制位，而且每个二进制位只能表示两种状态，0表示不存在，1表示存在，根本无法标识出现次数。如果每一个整数映射2个二进制位，那么就可以表示4种状态：00 -> 出现0次，01 -> 出现1次，10 -> 出现2次，11 -> 出现3次及以上。这样一来就可以标识次数了，我们的问题也就迎刃而解。但另一个关键的问题来了：让一个整数映射2个二进制位，是不是意味着我们需要改造刚才实现的位图呢？也可以，但没必要。我们只需使用两个位图即可。上面我们已经算过了，开一个可以映射42亿整数的位图大概要500兆，开两个正好1G，所以是可行的。

x从原来的只映射一个位图中的一个二进制位到映射两个位图中相同的二进制位，接下来我们模拟解决。

#pragma once
#include <vector>namespace pcz
{template <size_t N>class bitset{public:bitset() { _bs.resize(N / 32 + 1, 0); } //开空间//将x映射的位标记为1void set(size_t x){size_t i = x / 32;size_t j = x % 32;_bs[i] |= (1 << j);}//将x映射的位标记为0void reset(size_t x){size_t i = x / 32;size_t j = x % 32;_bs[i] &= (~(1 << j));}//如果x映射的二进制位为1，//则返回true，否则放回falsebool test(size_t x){size_t i = x / 32;size_t j = x % 32;return _bs[i] & (1 << j);}private:std::vector<size_t> _bs;};template <size_t N>class towbitset{public:void set(size_t x){//检查两个位图中对应的位是0or1bool flag1 = _bs1.test(x);bool flag2 = _bs2.test(x);if (!flag1 && !flag2)    //00 -> 01{_bs2.set(x);}else if (!flag1 && flag2)//01 -> 10{_bs1.set(x);_bs2.reset(x);}else if (flag1 && !flag2)//10 -> 11{_bs2.set(x);}}void reset(size_t x){_bs1.reset(x);_bs2.reset(x);}size_t get_count(size_t x){bool flag1 = _bs1.test(x);bool flag2 = _bs2.test(x);if (!flag1 && !flag2)return 0;				//出现0次else if (!flag1 && flag2)return 1;				//出现1次else if (flag1 && !flag2)return 2;				//出现2次elsereturn 3;				//出现3次及以上}private:bitset<N> _bs1;bitset<N> _bs2;};void TestTowBitSet(){towbitset<100> tbs;int arr[] = { 1, 12, 22, 13, 11, 7, 5, 8, 9, 32, 99, 99 };for (auto val : arr){tbs.set(val);}for (auto val : arr){if (tbs.get_count(val) == 2)cout << val << " ";}cout << endl;}
}

3） 给两个文件，分别有100亿个整数，只有1G内存，如何找到两个文件的交集。

这道题的解题思路是：开两个位图，分别将两个文件的数据映射到两个位图上，其中同一个数据在两个位图中映射的位置是一样的。所以我们只需判断x是否都在两个位图中，如果都在，就是交集。

namespace pcz
{template <size_t N>class bitset{public:bitset() { _bs.resize(N / 32 + 1, 0); } //开空间//将x映射的位标记为1void set(size_t x){size_t i = x / 32;size_t j = x % 32;_bs[i] |= (1 << j);}//将x映射的位标记为0void reset(size_t x){size_t i = x / 32;size_t j = x % 32;_bs[i] &= (~(1 << j));}//如果x映射的二进制位为1，//则返回true，否则放回falsebool test(size_t x){size_t i = x / 32;size_t j = x % 32;return _bs[i] & (1 << j);}private:std::vector<size_t> _bs;};void TestBitSet(){int arr1[] = { 1, 11, 2, 12, 99, 72, 31, 34, 88 };int arr2[] = { 5, 15, 66, 88 };bitset<100> _bs1;bitset<100> _bs2;for (auto val : arr1){_bs1.set(val);}for (auto val : arr2){_bs2.set(val);}for (size_t i = 0; i < 100; i++){if (_bs1.test(i) && _bs2.test(i))cout << i << endl;}}
}

本文到这就结束啦，感谢你的支持~ 

这篇关于【数据结构取经之路】位图全解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1127358。

相关文章

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）
阅读更多...
《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多，算法平均时间性能比直接插入排序差。当初始记录无序，n较大时， 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In
阅读更多...
哈希表的封装和位图

哈希表的封装和位图

文章目录 2 封装2.1 基础框架2.2 迭代器(1)2.3 迭代器(2) 3. 位图3.1 问题引入3.2 左移和右移？3.3 位图的实现3.4 位图的题目3.5 位图的应用 2 封装 2.1 基础框架 文章 有了前面map和set封装的经验，容易写出下面的代码 // UnorderedSet.h#pragma once#include "HashTable.h"
阅读更多...
【408数据结构】散列 （哈希）知识点集合复习考点题目

【408数据结构】散列 （哈希）知识点集合复习考点题目

苏泽  “弃工从研”的路上很孤独，于是我记下了些许笔记相伴，希望能够帮助到大家    知识点 1. 散列查找 散列查找是一种高效的查找方法，它通过散列函数将关键字映射到数组的一个位置，从而实现快速查找。这种方法的时间复杂度平均为(
阅读更多...
浙大数据结构：树的定义与操作

浙大数据结构：树的定义与操作

四种遍历 #include<iostream>#include<queue>using namespace std;typedef struct treenode *BinTree;typedef BinTree position;typedef int ElementType;struct treenode{ElementType data;BinTree left;BinTre
阅读更多...
Python 内置的一些数据结构

Python 内置的一些数据结构

文章目录 1. 列表 (List)2. 元组 (Tuple)3. 字典 (Dictionary)4. 集合 (Set)5. 字符串 (String) Python 提供了几种内置的数据结构来存储和操作数据，每种都有其独特的特点和用途。下面是一些常用的数据结构及其简要说明： 1. 列表 (List) 列表是一种可变的有序集合，可以存放任意类型的数据。列表中的元素可以通过索
阅读更多...
浙大数据结构：04-树7 二叉搜索树的操作集

浙大数据结构：04-树7 二叉搜索树的操作集

这道题答案都在PPT上，所以先学会再写的话并不难。 1、BinTree Insert( BinTree BST, ElementType X ) 递归实现，小就进左子树，大就进右子树。 为空就新建结点插入。 BinTree Insert( BinTree BST, ElementType X ){if(!BST){BST=(BinTree)malloc(sizeof(struct TNo
阅读更多...
【数据结构入门】排序算法之交换排序与归并排序

【数据结构入门】排序算法之交换排序与归并排序

前言         在前一篇博客，我们学习了排序算法中的插入排序和选择排序，接下来我们将继续探索交换排序与归并排序，这两个排序都是重头戏，让我们接着往下看。  一、交换排序 1.1 冒泡排序 冒泡排序是一种简单的排序算法。 1.1.1 基本思想 它的基本思想是通过相邻元素的比较和交换，让较大的元素逐渐向右移动，从而将最大的元素移动到最右边。 动画演示： 1.1.2 具体步
阅读更多...
数据结构：线性表的顺序存储

数据结构：线性表的顺序存储

文章目录 🍊自我介绍🍊线性表的顺序存储介绍概述例子 🍊顺序表的存储类型设计设计思路类型设计 你的点赞评论就是对博主最大的鼓励 当然喜欢的小伙伴可以：点赞+关注+评论+收藏（一键四连）哦~ 🍊自我介绍   Hello,大家好，我是小珑也要变强（也是小珑），我是易编程·终身成长社群的一名“创始团队·嘉宾” 和“内容共创官” ,现在我来为大家介绍一下有关物联网-嵌入
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2