海量数据处理系列----C++中Bitmap算法的实现

发布时间:2017-6-25 15:06:22 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"海量数据处理系列----C++中Bitmap算法的实现",主要涉及到海量数据处理系列----C++中Bitmap算法的实现方面的内容,对于海量数据处理系列----C++中Bitmap算法的实现感兴趣的同学可以参考一下。

     bitmap是一个十分有用的结构。所谓的Bit-map就是用一个bit位来标记某个元素对应的Value, 而Key即是该元素。由于采用了Bit为单位来存储数据,因此在存储空间方面,可以大大节省。      适用范围:可进行数据的快速查找,判重,删除,一般来说数据范围是int的10倍以下 基本原理及要点:使用bit数组来表示某些元素是否存在,比如8位电话号码 扩展:bloom filter可以看做是对bit-map的扩展 问题实例: 1)已知某个文件内包含一些电话号码,每个号码为8位数字,统计不同号码的个数。 8位最多99 999 999,大概需要99m个bit,大概10几m字节的内存即可。 2)2.5亿个整数中找出不重复的整数的个数,内存空间不足以容纳这2.5亿个整数。 将bit-map扩展一下,用2bit表示一个数即可,0表示未出现,1表示出现一次,2表示出现2次及以上。或者我们不用2bit来进行表示,我们用两个bit-map即可模拟实现这个2bit-map。 下面是一个简单的Bitmap的实现: [cpp] view plaincopy #include "stdafx.h"   #include <iostream>   using namespace std;      char *g_bitmap = NULL;     int g_size = 0;     int g_base = 0;       //功能:初始化bitmap    //参数: size:bitmap的大小,即bit位的个数    //      start:起始值    //返回值:0表示失败,1表示成功    int bitmap_init(int size, int start)     {         g_size = size/8+1;       g_base = start;       g_bitmap = new char[g_size];         if(g_bitmap == NULL)       {           return 0;         }       memset(g_bitmap, 0x0, g_size);         return 1;     }        //功能:将值index的对应位设为1    //index:要设的值    //返回值:0表示失败,1表示成功    int bitmap_set(int index)     {             int quo = (index-g_base)/8 ;  //确定所在的字节           int remainder = (index-g_base)%8;  //字节内的偏移             unsigned char x = (0x1<<remainder);               if( quo > g_size)                     return 0;           g_bitmap[quo] |= x;   //所在字节内的特定位置为1             return 1;      }         //功能:取bitmap第i位的值    //i:待取位    //返回值:-1表示失败,否则返回对应位的值    int bitmap_get(int i)     {         int quo = (i)/8 ;         int remainder = (i)%8;         unsigned char x = (0x1<<remainder);         unsigned char res;         if( quo > g_size)             return -1;         res = g_bitmap[quo] & x;         return res > 0 ? 1 : 0;      }             //功能:返回index位对应的值      int bitmap_data(int index)     {         return (index + g_base);     }        //释放内存    int bitmap_free()     {         delete [] g_bitmap;       return 0;   }           int _tmain(int argc, _TCHAR* argv[])    {         int a[] = {5,8,7,6,3,1,10,78,56,34,23,12,43,54,65,76,87,98,89,100};         int i;         bitmap_init(100, 0);         for(i=0; i<20; i++)       {           bitmap_set(a[i]);         }       for(i=0; i<=100; i++)         {             if(bitmap_get(i) > 0 )                 cout << bitmap_data(i)<< " ";       }         cout << endl;         bitmap_free();        return 0;     }     【问题实例】 1)已知某个文件内包含一些电话号码,每个号码为8位数字,统计不同号码的个数。 8位最多99 999 999,大概需要99m个bit,大概10几m字节的内存即可。 (可以理解为从0-99 999 999的数字,每个数字对应一个Bit位,所以只需要99M个Bit==1.2MBytes,这样,就用了小小的1.2M左右的内存表示了所有的8位数的电话) 2)2.5亿个整数中找出不重复的整数的个数,内存空间不足以容纳这2.5亿个整数。 将bit-map扩展一下,用2bit表示一个数即可,0表示未出现,1表示出现一次,2表示出现2次及以上,在遍历这些数的时候,如果对应位置的值是0,则将其置为1;如果是1,将其置为2;如果是2,则保持不变。或者我们不用2bit来进行表示,我们用两个bit-map即可模拟实现这个 2bit-map,都是一样的道理。

上一篇:sqlalchemy 学习教程
下一篇:小孩反复发烧,怎么办

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。