文章目录
位图
位图概念
给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中。【腾讯】
思路一:遍历，时间复杂度 O ( N ) O(N) O(N)
思路二: 排序 O ( N l o g N ) O(NlogN) O(NlogN)，利用二分查找: O ( l o g N ) O(logN) O(logN)
但是问题是,40亿个无符号整数,16G。压力很大。
思路三:放进set或unordered_set，再查找。
问题是空间撑不住，红黑树一个节点还有额外的空间，哈希的需要的空间更大。
正确的思路是用位图解决。
用一个位映射一个位置。只需要标记一个值在还是不在。
因此对于40个亿数，开 2 32 2^{32} 232个位就可以存下。(因为无符号整数大小 2 32 − 1 2^{32}-1 232−1)
而所占用空间为 2 32 / 8 = 512 M 2^{32}/8=512M 232/8=512M。
因此设定bitset的大小可以说设置为(4294967295u)或者直接就给(-1)。
数据是否在给定的整形数据中，结果是在或者不在，刚好是两种状态，那么可以使用一个二进制比特位来代表数据是否存在的信息，如果二进制比特位为1，代表存在，为0代表不存在。
每一个bit位可以当作bool来判定一个数存在与否。
位图的实现
#pragma once
namespace Y
{
template<size_t N>/*非类型模板参数定义可变的大小*/
class BitSet
{
public:
BitSet
{
_bits.resize( N/32 + 1 ,0 ); /*上取整*/
}
/*把x映射的位标记成1*/
void Set(size_t x)
{
assert(x < N);
/*算出x映射的位在第几个整数*/
size_t i = x / 32;
/*算出x映射的位在这个整数的第几个位*/
size_t j = x % 32;
//_bits[i]的第j位标记成1，并且不影响他的其他位
_bits[i] |= (1 << j);
}
/*把x映射的位标记成0*/
void Reset(size_t x)
{
assert(x < N);
size_t i = x / 32;
size_t j = x % 32;
_bits[i] &= (~(1 << j));
}
/*算x是1还是0*/
bool Test(size_t x)
{
size_t i = x / 32;
size_t j = x % 32;
/*如果第j位是1,结果非0,则返回真*/
/*如果第j位是0,结果为0,则返回假*/
return _bits[i] & (1 << j);
}
private:
vector<int> _bits;
};
void TestBitSet()
{
//BitSet<4294967295u> bs;
BitSet<-1> bs;
}
}
相关应用
- 给定100亿个整数，设计算法找到只出现一次的整数
- 给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集
- 位图应用变形：1个文件有100亿个int，1G内存，设计算法找到出现次数不超过2次的所有整数
- 文件系统中的数据块位图(datamap)和索引块位图(inodemap)。
- 给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集。
整数最多只有 2 32 2^{32} 232个，因此100亿个必定有重复。
方案1：把依次读取第一个文件的中的所有整数标记映射到一个位图。再读取读取另一个文件中的所有整数，判断在不在位图。在就是交集中的数，不在就不是。
方案2：由引例可得一个位图达到512M，依次读取第一个文件的所有整数标记映射为位图1，再读取第二个文件所有整数标记映射为位图2，再对两个位图进行与到一起。（依次与位图中的整数），与完以后还是1的位映射的整数就是交集。
- 给定100亿个整数，设计算法找到只出现一次的整数
第一种思路：
标记位在或者不在，一个位就可以。
那么标记的一个整数的以下几种状态：
出现0次，出现1次，出现2次及以上。分别是00,01,10。只要用2个bit就可以标记。
因此可以把原来的一张位图32位改造成2个位标记一个值，原来的 / 32 /32 /32变成 / 16 /16 /16即可。
Set的时候检查2个位，如果是00，则变成01。如果是01则变成10。如果是10则不变。
第二种思路：
不改造原来的位图。开两张位图。最后遍历两个位图。把所有01状态标记的整数统计出来。
Bitset<-1> _bs1,_bs2;
void Set(size_t x)
{
//00 -> 01
if(!_bs1.Test(x) && !_bs2.Test(x))
{
_bs2.set(x);
}
else if(!_bs1.Test(x) && _bs2.Test(x)) //01->10
{
_bs1.Set(x);
_bs2.ReSet(x);
}
else if( _bs1.Test(x) && !_bs2.Test(x))// 10->>10
{
//不处理
}
else{
assert(false);
}
}
- 位图应用变形：1个文件有100亿个int，1G内存，设计算法找到出现次数不超过2次的所有整数
类似上一题。给两个位图，出现3次及以上的设计成11。
最后遍历两个位图。把所有01和10状态标记的整数统计出来。
Bitset<-1> _bs1,_bs2;
void Set(size_t x)
{
//00 -> 01
if(!_bs1.Test(x) && !_bs2.Test(x))
{
_bs2.set(x);
}
else if(!_bs1.Test(x) && _bs2.Test(x)) //01->10
{
_bs1.Set(x);
_bs2.ReSet(x);
}
else if( _bs1.Test(x) && !_bs2.Test(x))// 10->>10
{
_bs2.Set(x);
}
else{
//不处理;
}
}
因此，遇到多次的就考虑多少位能组合出来即可。