建一个网站的手机电脑,新塘 网站建设,网站开发的开题报告模板,公司企业网站建设方案书文章目录 一、位图的概念二、位图的实现三、库中的 bitset四、位图的应用五、哈希切割 一、位图的概念
我们以一道面试题来引入位图的概念#xff1a; 给40亿个不重复的无符号整数#xff0c;没排过序。给一个无符号整数#xff0c;如何快速判断一个数是否在这40亿个数中 我… 文章目录 一、位图的概念二、位图的实现三、库中的 bitset四、位图的应用五、哈希切割 一、位图的概念
我们以一道面试题来引入位图的概念 给40亿个不重复的无符号整数没排过序。给一个无符号整数如何快速判断一个数是否在这40亿个数中 我们的第一反应可能是将数据进行排序之后进行二分查找或者将数据放入unordered_map/unordered_set中然后再进行查找。但是这两种方式看似能够实现但是实际上是不行的因为数据量太大了在内存中存放不下
40亿个整数每个整数占4个字节一共160个字节而1G大约10亿字节那么我们存储40个整数就大约需要16G而我们的内存一般只有4个G如果我们使用排序之后进行二分查找那么就需要开辟一个16G大小的数组显然是无法实现的如果我们使用红黑树或者哈希表的方式这也是不行的因为红黑树每个节点需要存放节点的值三个指针和颜色每个节点就需要消耗16个字节而哈希表中每个桶要存放一个指向下一个节点也有一定的消耗
我们换一个思考的方式题目中只要判断一个数在不在并没有其他的要求所以我们不需要将这些树存储下来只需要用一个值来对他们进行标记即可而标记一个数只需要一个比特位即可如果二进制比特位为1则表示存在为0表示不存在
数据是否在给定的整形数据中结果是在或者不在刚好是两种状态那么可以使用一个二进制比特位来代表数据是否存在的信息如果二进制比特位为1代表存在为0代表不存在。
所谓位图就是用每一位来存放某种状态适用于海量数据数据无重复的场景。通常是用来判断某个数据存不存在的。
二、位图的实现
对于位图一般我们只需要提供一下三个接口即可
1.set : 用于将某一数值对应的比特位置为1即进行标记(插入数据)
2.reset将某一数值对应的比特位置为0即删除标记(删除数据)
3.test : 用于测试某一数值对应的比特位是否为1即查找数据
这里我们需要一个非类型模板参数–N是给定的数据的范围不是数据的个数因为C中最小的数据类型是char占一个字节的空间一个字节占8个比特位可以用于标记8个位置。我们可以用一个vector来进行存储数据所以我们在构造函数中我们将vector resize到N/81即可加1是因为C中的除法是整除法即直接舍弃余数而我们这里应该采取进1法即需要多开辟一个空间。此外我们还可以将vector中的数据的类型定义为int此时我们开辟空间的时候应该resize到N/321
对于三个重要接口的实现我们使用目标值x/8就可以得到x应该被映射到哪一个下标即在第几个char的位置x%8就可以得到x应该被映射到该下标的第几个比特位然后再将对应的位置置为1或0即可
对于set我们可以使用或等的方法找到一个数这个数的第j个比特位(j为在下标中的第几个位置)为1其他的位置为0我们使用1向左移动j为即可然后再进行或等
对于reset:我们可以使用与等的方法找到一个数第j为0其他位为1我们只需要将1向左移动j位i然后再进行按位取反即可然后再进行与等
对于test我们知道在逻辑关系中0为假非0为真那么我们就可以将那个位置的数进行与注意是与不是与等与1左移j为如果那个位置为1那么都为0判断为假如果那个位置不为0与之后也不为0此时转换为bool类型为真这里会进行整形提升但是将一个数从0提升到非0或者从非0提升到0所以符号我们的要求
代码实现如下
namespace hdp
{templatesize_t Nclass bitset{public:bitset(){_bits.resize(N / 8 1, 0);}void set(size_t x){size_t i x / 8;size_t j x % 8;_bits[i] | (1 j);}void reset(size_t x){size_t i x / 8;size_t j x % 8;_bits[i] (~(1 j));}bool test(size_t x){size_t i x / 8;size_t j x % 8;return _bits[i] (1 j);}private:vectorchar _bits;};
}有了位图之后我们就可以解决上面的面试题了–由于题目中说明了数据是无符号整数那么我们就可以将N定义为-1(有符号的-1等于无符号的最大值)然后我们只需要将这40亿个数据依次进行set然后进行test即可
无符号的最大值大约为42亿九千万也就是需要这么多的比特位来进行标记计算得大约需要5亿字节即512M这是可以在内存中存放得下的
三、库中的 bitset
C提供了类似于位图的东西–位的集合–bitset它的功能比我们实现的更加的丰富但是主要功能还是setreset和test 四、位图的应用
位图主要运用于一下几个方面
1.快速查找某个数据是否在一个集合中
2.排序 去重
3.求两个集合的交集、并集等
4.操作系统中磁盘块标记
我们来看看下面几道位图应用的题目
1.给定100亿个整数设计算法找到只出现一次的整数
我们发现使用传统的位图并不能解决这个问题因为位图只能表示存在和不存在只能够表示两种状态这个问题中就存在多种状态但是我们可以将上面的问题分为3种状态–没有出现出现1次出现一次以上。那么我们就可以使用两个位图结合在一起使用两个比特位来进行标识两个比特位最多可以标识4种状态我们取3种即可
00没有出现
01出现1次
10出现1次以上
代码实现如下
templatesize_t N
class twobitset
{
public:void set(size_t x){if (!_bs1.test(x) !_bs2.test(x)) //00{_bs2.set(x);//01}else if (!_bs1.test(x) _bs2.test(x)) //01{_bs1.set(x);_bs2.reset(x); //10}}private:bitsetN _bs1;bitsetN _bs2;
};2.1个文件有100亿个int1G内存设计算法找到出现次数不超过2次的所有整数
这道题和上面求只出现一次的数字的思路一致这里我们需要将出现0次1次2次2次以上的状态都表示处出来使用两个标记位即可
templatesize_t N
class twobitset
{
public:void set(size_t x){if (!_bs1.test(x) !_bs2.test(x)) //00{_bs2.set(x);//01}else if (!_bs1.test(x) _bs2.test(x)) //01{_bs1.set(x);_bs2.reset(x); //10}else if(_bs1.test(x) !_bs2.test(x)) // 10{_bs1.set(x);_bs2.set(x); //11}}private:bitsetN _bs1;bitsetN _bs2;
};3.给两个文件分别有100亿个整数我们只有1G内存如何找到两个文件交集
我们可以将第一个文件的数据全部映射到一个位图中然后再遍历取出第二个位图中的数据进行test即可返回true的数据即为交集但是这样就会得到许多重复的数据所以最终的结果需要进行去重处理。我们也可以使用两个位图分别进行映射然后进行遍历两者进行与运算为1则为交集的数据
五、哈希切割
对于下面这道题目
给一个超过100G大小的log fifile, log中存着IP地址, 设计算法找到出现次数最多的IP地址
和前面我们的题目不同这道题我们不能使用位图来解决因为我们不知道相同的ip会出现多少次所以就无法确定使用多少个比特位来进行标记
100G数据太大内存放不下我们能不能将这个文件平均分为100分大小的文件这样每个问题都只有一个G的大小此时再依次插入map中进行统计次数这样其实也是不行的因为在统计下一个小的文件时我们需要将之前的文件的统计结果即map中的数据进行clear否则就会因为数据过多导致内存不足的情况这样就不能够很好的统计出IP出现的次数。
我们可以想办法将相同的IP放入同一个小文件中即我们可以使用哈希切割的方法–先使用字符哈希函数将IP转换为整数然后再使用除留余数法将100G文件的IP地址划分到不同的小文件中
size_t Ai HashFunc(IP) % 100;经过哈希切割之后相同的IP一定会被划分到同一个小文件中因为相同的字符串经过哈希映射之后一定会得到相同的整数那么模出来的结果也也一定相同即会在同一个小文件中但是不同的IP也可能会被划分到同一个文件中因为会发生哈希冲突此时文件的大小就可能会操作一个G并且划分非结果有两种
1.子文件中有许多相同的IP地址此时我们可以直接使用map统计这些IP地址的数量(所有相同的IP地址一定会出现在同一个子文件中)
2.子文件中有许不同的IP地址大多是不重复的map统计不下那么此时我们就需要换一个哈希函数递归再切分
使用map统计如果是第一种情况可以统计出来的不会报错
如果是第二种情况map的insert插入失败那是没有内存相当于new节点失败new失败会抛异常
最终出现次数最多的那个IP地址会被全部映射到某一个子文件中我们对子文件使用map进行统计就可以得到其出现的次数
