大家好，又见面了，我是全栈君，今天给大家准备了Idea注册码。
题目： 给40个亿不重复的无符号整数，没有排序过，随机给出一个无符号整数，快速的判断这个数在或者不在40亿个数中?
1. 思路
有的人一看到这个题，很简单嘛最麻烦的就是从头遍历一遍的事情嘛. 不过要看清楚题！ 40亿个无符号整数. 我们生活中1G内存占用的字节数1024*1024*1024为1073741824个字节.粗略就是10亿个字节. 而40亿个无符号整数是160亿个字节. 也就是这些数据存储下来需要16G的内存. 那么问题来了，普通的工作电脑的内存都4G，好点的就是8G. (如果你是16G内存光速吃鸡那么当我没说)我们可以发现这些数据的内存大于电脑的内存所以存储不下. 这个时候就很头大了,内存都存不下那么你怎么读取呢？ 当然你说你直接去硬盘里面读.好！ 没问题.从硬盘里面读取数据的速度和从内存中读取的速度根本没得比的.如果你的时间多也可以.不过我们有一个更厉害的方法就是我们的位图.位图就是给定一段连续的空间然后让这个空间的每一位都为0，再然后让每一个位表示一个数字.再然后当你这个数字出现的 时候将它对应的那个位->置为1.这样的话存储40亿个数据，也就是存储40亿个位.也就是5亿个字节.大概512MB的样子. 这样的话我们的内存存储这些数据也就是绰绰有余了.所以位图对于大数据的问题有着显著的效果。
2. 代码实现
#include "stdio.h" // 用位图的方式实现大数据的查找 #include <vector> #include <iostream> using namespace std; class CBitmapFind { enum{INFOBITS_IN_VECT = 8}; public: // 确定容器大小 explicit CBitmapFind(size_t nRange = 0) { BitmapVect.resize(nRange / INFOBITS_IN_VECT + 1); } // 添加单个元素并标记该元素 void AddElement(int nNum) { // 确定该数据所在vect中的位置 int nVectIndex = nNum / INFOBITS_IN_VECT; // 确定在vect索引中的byte位置 int nByteIndex = nNum % 8; BitmapVect[nVectIndex] |= (1 << nByteIndex); } // 删除单个元素并移除单个元素 void MoveElement(int nNum) { // 确定该数据所在vect中的位置 int nVectIndex = nNum / INFOBITS_IN_VECT; // 确定在vect索引中的byte位置 int nByteIndex = nNum % 8; BitmapVect[nVectIndex] &= ~(1 << nByteIndex); } bool TestBit(int nNum) { // 确定该数据所在vect中的位置 int nVectIndex = nNum / INFOBITS_IN_VECT; // 确定在vect索引中的byte位置 int nByteIndex = nNum % 8; return (BitmapVect[nVectIndex] & (1 << nByteIndex)? true:false); } private: vector<char> BitmapVect; };
3. 扩展：判断出现是次数是否大于3
// 用位图的方式实现大数据的查找,判断出现的次数,下面的代码只能处理出现次数小于等于3的情况 // 00 01 10 11 class CNBitmapFind { public: enum{ INFOBITS_IN_VECT = 4 }; // 确定容器大小 explicit CNBitmapFind(size_t nRange = 0) { BitmapVect.resize(nRange / INFOBITS_IN_VECT + 1); } // 添加单个元素并标记该元素出现的次数 void AddElement(int nNum) { // 确定该数据所在vect中的位置 int nVectIndex = nNum / INFOBITS_IN_VECT; // 确定元素在vect索引中的byte位置 int nByteIndex = nNum % INFOBITS_IN_VECT; nByteIndex *= 2; bool first = BitmapVect[nVectIndex] & (1 << nByteIndex); bool second = BitmapVect[nVectIndex] & (1 << (nByteIndex + 1)); if (!(first && second)) { BitmapVect[nVectIndex] += (1 << nByteIndex); } } int Test(int nNum) { // 确定该数据所在vect中的位置 int nVectIndex = nNum / INFOBITS_IN_VECT; // 确定元素在vect索引中的byte位置 int nByteIndex = nNum % INFOBITS_IN_VECT; nByteIndex *= 2; int first = BitmapVect[nVectIndex] & (1 << nByteIndex)?1:0; int second = BitmapVect[nVectIndex] & (1 << (nByteIndex + 1))?1:0; return second * 2 + first; } private: vector<char> BitmapVect; };
4. 测试
void main() { int nReange = 4 * pow(10, 2); CBitmapFind BitmapFind(nReange); for (int i = 0; i < nReange; i++) { BitmapFind.AddElement(i); } cout << "CBitmapFind测试：" << endl; BitmapFind.TestBit(401) ? (cout << "找到:" << 401 << endl) : (cout << "未找到" << 401 << endl); BitmapFind.TestBit(388) ? (cout << "找到" << 388 << endl) : (cout << "未找到" << 388 << endl); CNBitmapFind NBitmapFind(6); NBitmapFind.AddElement(1); NBitmapFind.AddElement(1); NBitmapFind.AddElement(1); NBitmapFind.AddElement(2); NBitmapFind.AddElement(2); NBitmapFind.AddElement(3); cout << "CNBitmapFind测试：" << endl; cout << "1出现的次数：" << NBitmapFind.Test(1) << endl; cout << "2出现的次数：" << NBitmapFind.Test(2) << endl; cout << "3出现的次数：" << NBitmapFind.Test(3) << endl; }
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/120125.html原文链接：https://javaforall.net
