flickr wordpress,网站seo站长工具,2016年做水果行业专业网站,深圳做装修网站费用目录
1、位图的概念
2、位图的设计与实现 2.1 set
2.2 reset
2.3 test
3、C库中的位图
4、位图的优缺点
5、位图相关题目 1、位图的概念
面试题#xff1a;给40亿个不重复的无符号整数#xff0c;没排过序。给一个无符号整数#xff0c;如何快速判断一个数是否在这4…目录
1、位图的概念
2、位图的设计与实现 2.1 set
2.2 reset
2.3 test
3、C库中的位图
4、位图的优缺点
5、位图相关题目 1、位图的概念
面试题给40亿个不重复的无符号整数没排过序。给一个无符号整数如何快速判断一个数是否在这40亿个数中。
法一遍历时间复杂度是O(N)太慢
法二排序 二分查找。时间复杂度是O(N * logN) O(logN)。只是第一次比较慢后面就快了。使用这个方法有一个致命的缺陷是存放40亿个数据需要的内存太过庞大。
1GB 1024MB 1024 * 1024KB 1024 * 1024 * 1024Byte
所以40亿个数据约等于16GB说明40亿个数据是无法直接放到内存中的只能放到硬盘文件中。而二分查找只能对内存数组中的有序数据就行查找。这里使用数组是最节省空间的因为每个位置只存放数据如果使用红黑树或哈希表需要的空间还要更大
法三使用位图
数据是否在给定的整型数据中结果是在或不在刚好是两种状态那么可以用一个二进制比特位来代表数据是否存在的信息如果二进制比特位为1代表存在如果二进制比特位为0代表不存在。那么我们就可以设计一个用位表示数据是否存在的数据结构这个数据结构就是位图。
2、位图的设计与实现
实现中要注意的是C/C中没有对应位的类型只能看char/int这样的整型类型我们再通过位运算去控制对应的比特位。比如我们数据存到vectorint中相当于每个Int映射对应的32个值比如第一个整型映射0~31对应的位第二个整型映射32~63对应的位后面依次类推。那么来一个无符号整型xi x / 32j x % 32x映射的位置就是vector第i个整型数据的第j位。 我的机器是小端存储所以一个整型中低位是在右边 对于上面40亿个无符号整型我们开空间需要开2^32个因为无符号整型有2^32个不是根据数据个数来开空间
namespace cxf
{templatesize_t N // 开N个位的位图class bitset{public:bitset(){_bs.resize(N / 32 1); // 因为N除32可能会除不尽所以多开一个整型保证位够}private:std::vectorint _bs;};
} 2.1 set
向位图中插入数据也就是将插入数据映射到的位标记成1
假设要向位图中插入数据77要如何操作呢
首先计算出位为77的地方位于第几个整型数据的第几个位。会发现位于第3个整型数据的第13个位然后将1左移13个位的结果与第3个整型数据按位或就可以将插入数据映射到的位标记成1
void set(size_t x)
{size_t i x / 32;size_t j x % 32;_bs[i] | (1 j);
}
2.2 reset
向位图中删除数据也就是将传入数据映射到的位标记成0
假设要向位图中删除数据77要如何操作呢
首先计算出位为77的地方位于第几个整型数据的第几个位。会发现位于第3个整型数据的第13个位然后将1左移13个位再按位取反的结果与第3个整型数据按位与就可以将插入数据映射到的位标记成0
void reset(size_t x)
{size_t i x / 32;size_t j x % 32;_bs[i] (~(1 j));
}
2.3 test
若传入数据映射到的位是1就返回真是0就返回假
bool test(size_t x)
{size_t i x / 32;size_t j x % 32;return _bs[i] (1 j);
}
可以测试一下
void test_bitset()
{cxf::bitset100 bs; // 开一个100个位的位图bs.set(77);bs.set(66);cout bs.test(77) endl;cout bs.test(66) endl;bs.reset(66);cout bs.test(77) endl;cout bs.test(66) endl;
}
结果是1 1 1 0是正确的
那要如何开2^32个空间呢有3种方法
cxf::bitset-1 bs1;
cxf::bitset0xffffffff bs2;
cxf::bitsetUINT_MAX bs3;
namespace cxf
{templatesize_t N // 开N个位的位图class bitset{public:bitset(){_bs.resize(N / 32 1); // 因为N除32可能会除不尽所以多开一个整型保证位够}void set(size_t x){size_t i x / 32;size_t j x % 32;_bs[i] | (1 j);}void reset(size_t x){size_t i x / 32;size_t j x % 32;_bs[i] (~(1 j));}bool test(size_t x){size_t i x / 32;size_t j x % 32;return _bs[i] (1 j);}private:std::vectorint _bs;};
}
3、C库中的位图 与前面我们自己实现的位图是差不多的operator[]可以像数组一样控制某个位
要注意库中的位图是不能直接开2^32个空间的
void test_bitset2()
{std::bitsetUINT_MAX bs;
}
像这样程序会崩溃的因为我们自己实现的位图底层是使用vector是去堆上开空间而库中的位图是用一个静态数组实现的没办法开太大。我们可以对其就行测试
void test_bitset2()
{cxf::bitset100 bs1;cxf::bitset10000 bs2;std::bitset100 bs3;std::bitset10000 bs4;cout sizeof(bs1) ;cout sizeof(bs2) ;cout sizeof(bs3) ;cout sizeof(bs4) ;
}
结果是16 16 16 1256
当然是可以通过指针来解决的
std::bitset-1* ptr new std::bitset-1();
4、位图的优缺点
优点增删查改快时间复杂度均为O(1)节省空间
缺点只适用于整型
5、位图相关题目
位图的应用
题目一给定100亿个整数设计算法找到只出现一次的整数。
注意此时虽然是100亿个整数但是还是按范围开空间所以还是开2^32个位与前面一样
法一可以用两个位来标记一个数,00表示没出现过01表示出现了1次10表示出现了2次及以上法二用两个位图一个数在每个位图中各占一个位规则与法一相同
题目二一个文件有100亿个整数1G内存设计算法找到出现次数不超过2次的所有整数
与上面类似只不过这里是00表示没出现过01表示出现了1次10表示出现了2次11表示出现3次及以上
我们来复用前面实现的位图来对这两个问题就行实现
namespace cxf
{templatesize_t N // 开N个位的位图class bitset{public:bitset(){_bs.resize(N / 32 1); // 因为N除32可能会除不尽所以多开一个整型保证位够}void set(size_t x){size_t i x / 32;size_t j x % 32;_bs[i] | (1 j);}void reset(size_t x){size_t i x / 32;size_t j x % 32;_bs[i] (~(1 j));}bool test(size_t x){size_t i x / 32;size_t j x % 32;return _bs[i] (1 j);}private:std::vectorint _bs;};templatesize_t Nclass twobitset{public:void set(size_t x){bool bit1 _bs1.test(x);bool bit2 _bs2.test(x);if (!bit1 !bit2) // 00-01{_bs2.set(x);}else if (!bit1 bit2) // 01-10{_bs1.set(x);_bs2.reset(x);}else if (bit1 !bit2) // 10-11{_bs2.ser(x);}}int get_count(size_t x) // 返回x出现的次数{bool bit1 _bs1.test(x);bool bit2 _bs2.test(x);if (!bit1 !bit2) return 0;else if (!bit1 bit2) return 1;else if (bit1 !bit2) return 2;else return 3;}private:bitsetN _bs1;bitsetN _bs2;};
}
题目三给两个文件分别有100亿个整数我们只有1G内存如何找到两个文件的交集
把数据读出来分别放到两个位图依次遍历同时在两个位图的值就是交集
