数据结构：位图法

Size: px

Start display at page:

Download "数据结构：位图法"

雪洞方
3 years ago
Views:

一定义位图法就是 bitmap 的缩写所谓 bitmap, 就是用每一位来存放某种状态, 适用于大规模数据, 但数据状态又不是很多的情况通常是用来判断某个数据存不存在的在 STL 中有一个 bitset 容器, 其实就是位图法, 引用 bitset 介绍 : A bitset is a special container class that is designed to store

the class is very similar to a regular array, but optimizing for space allocation: each element occupies only one bit (which is eight times less than the smallest elemental type in C++: char).

1 一定义位图法就是 bitmap 的缩写所谓 bitmap, 就是用每一位来存放某种状态, 适用于大规模数据, 但数据状态又不是很多的情况通常是用来判断某个数据存不存在的在 STL 中有一个 bitset 容器, 其实就是位图法, 引用 bitset 介绍 : A bitset is a special container class that is designed to store bits (elements with only two possible values: 0 or 1,true or false,...).the class is very similar to a regular array, but optimizing for space allocation: each element occupies only one bit (which is eight times less than the smallest elemental type in C++: char).each element (each bit) can be accessed individually: for example, for a given bitset named mybitset, the expression mybitset[3] accesses its fourth bit, just like a regular array accesses its elements. 二数据结构 unsigned int bit[n]; 在这个数组里面, 可以存储 N * sizeof(int) * 8 个数据, 但是最大的数只能是 N * sizeof(int) * 8-1 假如, 我们要存储的数据范围为 0-15, 则我们只需要使得 N=1, 这样就可以把数据存进去如下图 : 数据为 5,1,7,15,0,4,6,10, 则存入这个结构中的情况为三相关操作 1, 写入数据定义一个数组 : unsigned char bit[8 * 1024]; 这样做, 能存 8K*8=64K 个 unsigned short 数据 bit 存放的字节位置和位位置 ( 字节 0~8191, 位 0~7 ) 比如写 1234, 字节序 : 1234/8 = 154; 位序 : 1234 &0b111 = 2, 那么 1234 放在 bit 的下标 154 字节处, 把该字节的 2 号位 ( 0~7) 置为 1 1 / 6

2 字节位置 : int nbytepos =1234/8 = 154; 位位置 : int nbitpos = 1234 & 7 = 2; // 把数组的 154 字节的 2 位置为 1 unsigned short val = 1<<nBitPos; bit[nbytepos] = bit[nbytepos] val; // 写入 1234 得到 arrbit[154]=0b 再比如写入 1236, 字节位置 : int nbytepos =1236/8 = 154; 位位置 : int nbitpos = 1236 & 7 = 4 // / 把数组的 154 字节的 4 位置为 1 val = 1<<nBitPos; arrbit[nbytepos] = arrbit[nbytepos] val; // 再写入 1236 得到 arrbit[154]=0b 函数实现 : #define SHIFT 5 #define MAXLINE 32 #define MASK 0x1F void setbit(int *bitmap, int i){ bitmap[i >> SHIFT] = (1 << (i & MASK)); 2, 读指定位 bool getbit(int *bitmap1, int i){ return bitmap1[i >> SHIFT] & (1 << (i & MASK)); 四位图法的缺点 1. 可读性差 2. 位图存储的元素个数虽然比一般做法多, 但是存储的元素大小受限于存储空间的大小位 2 / 6

3 图存储性质 : 存储的元素个数等于元素的最大值比如, 1K 字节内存, 能存储 8K 个值大小上限为 8K 的元素 ( 元素值上限为 8K, 这个局限性很大!) 比如, 要存储值为的数, 就必须要 65535/8=8K 字节的内存要就导致了位图法根本不适合存 unsigned int 类型的数 ( 大约需要 2^32/8=5 亿字节的内存 ) 3. 位图对有符号类型数据的存储, 需要 2 位来表示一个有符号元素这会让位图能存储的元素个数, 元素值大小上限减半比如 8K 字节内存空间存储 short 类型数据只能存 8K*4=32K 个, 元素值大小范围为 -32K~32K 五位图法的应用 1 给 40 亿个不重复的 unsigned int 的整数, 没排过序的, 然后再给一个数, 如何快速判断这个数是否在那 40 亿个数当中首先, 将这 40 亿个数字存储到 bitmap 中, 然后对于给出的数, 判断是否在 bitmap 中即可 2 使用位图法判断整形数组是否存在重复遍历数组, 一个一个放入 bitmap, 并且检查其是否在 bitmap 中出现过, 如果没出现放入, 否则即为重复的元素 3 使用位图法进行整形数组排序首先遍历数组, 得到数组的最大最小值, 然后根据这个最大最小值来缩小 bitmap 的范围这里需要注意对于 int 的负数, 都要转化为 unsigned int 来处理, 而且取位的时候, 数字要减去最小值 4 在 2.5 亿个整数中找出不重复的整数, 注, 内存不足以容纳这 2.5 亿个整数参考的一个方法是 : 采用 2-Bitmap( 每个数分配 2bit,00 表示不存在,01 表示出现一次,10 表示多次,11 无意义 ) 其实, 这里可以使用两个普通的 Bitmap, 即第一个 Bitmap 存储的是整数是否出现, 如果再次出现, 则在第二个 Bitmap 中设置即可这样的话, 就可以使用简单的 1- Bitmap 了六实现要求在里面 #include <iostream> #include <cstdlib> #include <cstdio> #include <cstring> #include <fstream> #include <string> #include <vector> #include <algorithm> #include <iterator> #define SHIFT 5 #define MAXLINE 32 #define MASK 0x1F 3 / 6

4 using namespace std; // w // // void setbit(int *bitmap, int i){ bitmap[i >> SHIFT] = (1 << (i & MASK)); bool getbit(int *bitmap1, int i){ return bitmap1[i >> SHIFT] & (1 << (i & MASK)); size_t getfilesize(ifstream &in, size_t &size){ in.seekg(0, ios::end); size = in.tellg(); in.seekg(0, ios::beg); return size; char * fillbuf(const char *filename){ size_t size = 0; ifstream in(filename); if(in.fail()){ cerr<< "open " << filename << " failed!" << endl; exit(1); getfilesize(in, size); char *buf = (char *)malloc(sizeof(char) * size + 1); if(buf == NULL){ cerr << "malloc buf error!" << endl; exit(1); in.read(buf, size); in.close(); buf[size] = ' '; return buf; void setbitmask(const char *filename, int *bit){ char *buf, *temp; temp = buf = fillbuf(filename); char *p = new char[11]; int len = 0; 4 / 6

5 while(*temp){ if(*temp == '\n'){ p[len] = ' '; len = 0; //cout<<p<<endl; setbit(bit, atoi(p)); else{ p[len++] = *temp; temp++; delete buf; void comparebit(const char *filename, int *bit, vector &result){ char *buf, *temp; temp = buf = fillbuf(filename); char *p = new char[11]; int len = 0; while(*temp){ if(*temp == '\n'){ p[len] = ' '; len = 0; if(getbit(bit, atoi(p))){ result.push_back(atoi(p)); else{ p[len++] = *temp; temp++; delete buf; int main(){ vector result; unsigned int MAX = (unsigned int)(1 << 31); unsigned int size = MAX >> 5; int *bit1; bit1 = (int *)malloc(sizeof(int) * (size + 1)); if(bit1 == NULL){ cerr<<"malloc bit1 error!"<<endl; exit(1); 5 / 6

6 Powered by TCPDF ( memset(bit1, 0, size + 1); setbitmask("file1", bit1); comparebit("file2", bit1, result); delete bit1; cout<<result.size(); sort(result.begin(), result.end()); vector< int >::iterator it = unique(result.begin(), result.end()); ofstream of("result"); ostream_iterator output(of, "\n"); copy(result.begin(), it, output); return 0; ( 转载请注明 : 请不要用于商业目的 ) 本博客文章除特别声明, 全部都是原创! 原创文章版权归过往记忆大数据 ( 过往记忆 ) 所有, 未经许可不得转载本文链接 : () 6 / 6

迅速在两个含有大量数据的文件中寻找相同的数据

迅速在两个含有大量数据的文件中寻找相同的数据求解问题如下 : 在本地磁盘里面有 file1 和 file2 两个文件, 每一个文件包含 500 万条随机整数 ( 可以重复 ), 最大不超过 2147483648 也就是一个 int 表示范围要求写程序将两个文件中都含有的整数输出到一个新文件中要求 : 1. 程序的运行时间不超过 5 秒钟 2. 没有内存泄漏 3. 代码规范, 能要考虑到出错情况