1.给40亿个不重复的unsigned int的整数,没排过序的,然后再给一个数,如何快速判断这个数是否在那40亿个数当中?
2.给定一个千万级别数据量的整数集合,判断哪些是重复元素。
3.给定一个千万级别数据量的整形数组,对其进行排序。
4.在5亿个整数中找出不重复的整数(注意,内存不足以容纳这5亿个整数)。
从数据量上看,使用常规的解法(普通排序算法,逐个比较等)明显不合适,所以这里我们引入一个新的解法,就是Bitmap。
Bitmap就是用一个bit位来标记某个元素对应的Value, 而Key即是该bit的位序。由于采用了Bit为单位来存储数据,因此可以大大节省存储空间。 bitmap通过1个位表示一个状态,比如:int类型有2^32个数字,即4G个数字,那么每个数字一个状态,就是2^32个bit,即512 MB(也就是说,用512兆存储空间就可以处理4G个数据,即40+亿数据)。
下面是我用C++写的一个bitmap类,可以通过构造对象时传入数据规模,动态申请所需的内存,然后处理用户的大量数据:
#include<iostream>
#include<fstream>
#include<ctime>
using namespace std;
const unsigned SIZE = 512000000;//512兆静态存储区可处理40.96亿数据
class Bitmap {
typedef struct Byte {
unsigned char bit8;
static const unsigned char mask[9];//用来取得一个字节每一位的辅助数组
Byte()
{
bit8 = 0;
}
//设置该位,就是存储该数
void set1(unsigned at)
{
bit8 |= mask[at];
}
//读取该位是否有数
bool get1(unsigned at)
{
return bit8 & mask[at];
}
} Byte;
Byte *m_byte;
unsigned m_size;
public:
Bitmap(unsigned _size)
{
m_byte = new Byte[(_size+7)/8];
m_size = _size;
}
virtual ~Bitmap()
{
delete[] m_byte;
m_size = 0;
}
//存储一个数据
bool push(unsigned data)
{
if(data>=m_size)
return false;
m_byte[data/8].set1(data%8);
return true;
}
//读取一个数据是否存在
bool find(unsigned data)
{
return data>=m_size ? 0 : m_byte[data/8].get1(data%8);
}
//返回能存储的数据个数
unsigned size()
{
return m_size;
}
//重载运算符实现常用功能
//存储一个数据
bool operator>>(unsigned data)
{
return push(data);
}
//读取一个数据是否存在
bool operator<<(unsigned data)
{
return find(data);
}
//访问到某个数据块
Byte& operator[](unsigned i)
{
if(i>=m_size/8)
throw "index out of range";
return m_byte[i];
}
};
const unsigned char Bitmap::Byte::mask[9] = {0x80,0x40,0x20,0x10,0x8,0x4,0x2,0x1};//用来取得一个字节每一位的辅助数组
int main()
{
Bitmap bitmap(8*SIZE);//可以存储40+亿数据
ifstream file("in.txt");//从文件内录入一些整数
unsigned read, i=0, t1 = clock();
for(i=0; i<SIZE; ++i)
if(file>>read)
bitmap>>read;
else
break;
file.close();
cout<<"共存储"<<i/10000<<"W 数据, "<<"耗时: "<<clock()-t1<<"ms"<<endl;
t1 = clock();
for(i=0; i<1000000; ++i)
if(bitmap<<i)
;
cout<<"访问"<<i/10000<<"W 数据共耗时: "<<clock()-t1<<"ms"<<endl;
cout<<"请输入需要检索的数据:"<<endl;
while(cin>>read) {
if(bitmap<<read)
cout<<"已存储"<<read<<endl;
else
cout<<"Error: 未存储"<<read<<endl;
}
return 0;
}
运行结果如下: