丝绸之路网站建设报告,vuejs做视频网站,智能做网站,口碑好的移动网站建设文章目录位图概念位图操作位图代码位图应用位图概念
boss直接登场#xff1a;
给40亿个不重复的无符号整数#xff0c;没排过序。给一个无符号整数#xff0c;如何快速判断一个数是否在这40亿个数中❓
40亿个整数#xff0c;大概就是16GB。40亿个字节大概就是4GB。 1Byt…
文章目录位图概念位图操作位图代码位图应用位图概念
boss直接登场
给40亿个不重复的无符号整数没排过序。给一个无符号整数如何快速判断一个数是否在这40亿个数中❓
40亿个整数大概就是16GB。40亿个字节大概就是4GB。 1Byte8bit 1KB1024Byte 1MB1024KB1024*10241048576字节 1GB1024MB1024*1048576≈10亿字节所以4GB约等于40亿字节 1TB1024GB 如果采用排序二分的做法来查找排序要用到数组要开出16GB大的数组排在数组里才能进行二分查找但是这些数组在内存里放不下所以排序都排不了。那只能放到磁盘上那数据在磁盘上就不能用二分了不支持下标效率也慢。
如果用红黑树和哈希表数组都存放不下红黑树和哈希表更不用说了红黑树三叉链结构颜色消耗更大哈希表也有消耗存放_next指针负载因子等问题内存放不下。
下面我们解决这个问题的方法是位图
这个问题是在不在的问题是key的模型那我们可以标记在还是不在我们只需要一个比特位就可以标记在还是不在
数据是否在给定的整形数据中结果是在或者不在刚好是两种状态那么可以使用一个二进制比特位来代表数据是否存在的信息如果二进制比特位为1代表存在为0代表不存在。 位图概念 所谓位图就是用每一位来存放某种状态适用于海量数据数据无重复的场景。通常是用来判断某个数据存不存在的 位图操作
位图核心的三个操作是set、reset和test。
set是将x对应的比特位置设为1reset是将x对应的比特位置设为0test用来查看x在不在 set将对应的比特位置设为1_bits[i]|(1j) reset将对应的比特位置设为0_bits[i](~(1j)) test查看x在或不在:_bits[i](1j) 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);}位图代码
#pragma once
#include iostream
#include vector
using namespace std;namespace hwc
{templatesize_t Nclass bitset{public:bitset(){_bits.resize(N/81, 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;};void test_bitset(){//bitset100 bs1;//bitset-1 bs2;//bitset0xffffffff bs2;bs2.set(10);bs2.set(20);bs2.set(3000);cout bs2.test(10) endl;cout bs2.test(20) endl;cout bs2.test(3000) endl;cout bs2.test(666) endl;cout bs2.test(777) endl endl;bs2.reset(20);bs2.set(666);cout bs2.test(10) endl;cout bs2.test(20) endl;cout bs2.test(3000) endl;cout bs2.test(666) endl;cout bs2.test(777) endl;}
}小细节:(-1)的size_t类型
实际上库里面也有位图 位图应用 \1. 快速查找某个数据是否在一个集合中 \2. 排序 \3. 求两个集合的交集、并集等 \4. 操作系统中磁盘块标记 给定 100 亿个整数设计算法找到只出现一次的整数 100亿个数字找到只出现一次的整数这是KV模型的统计次数数字有三种状态0次、1次、1次以上,。这三种状态需要用两个比特位就可以表示分别位00代表0次,01代表1次,10代表1次以上既可以。我们可以采用两个位图来实现复用上面所实现的位图即可解决问题 templatesize_t Nclass 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}//10不变}void PrintOnce(){for (size_t i 0; i N; i){if (!_bs1.test(i) _bs2.test(i)){cout i endl;}}cout endl;}private:bitsetN _bs1;bitsetN _bs2;};void test_twobitset(){twobitset100 tbs;int a[] { 2,3,4,56,99,55,3,3,2,2,10 };for (auto e : a){tbs.set(e);}tbs.PrintOnce();}给两个文件分别有100亿个整数我们只有1G内存如何找到两个文件交集 1 个文件有 100 亿个 int1G内存设计算法找到出现次数不超过2次的所有整数 这与上面的类似多判断一次把10-11,最后找不超过两次的整数 给一个超过100G大小的log filelog中存着IP地址设计算法找到出现次数最多的IP地址 统计次数自然是要map的map有附带消耗三叉链。位图只能判断在不在。所以还是要用map统计的 我们可以把整个文件通过哈希切分成小的文件然后去进行统计次数但是如果小的文件超过1G说明了这个小文件有两种情况 1.这个小文件冲突的ip很多但都是不同的ipmap统计不下-------map的insert插入失败没有内存相当于new节点失败new失败会抛出异常 2.这个肖文杰冲突的ip很多大多都是相同的ipmap可以统计--------直接用map统计可以统计不会报错 位图特点位图只能处理整形。采用位图标记字符串时必须先将字符串转化为整形的数字找到位图对应的比特位置
