当前位置:  编程技术>c/c++/嵌入式

海量数据处理系列之:用C++实现Bitmap算法

    来源: 互联网  发布时间:2014-10-16

    本文导语:  bitmap是一个十分有用的结构。所谓的Bit-map就是用一个bit位来标记某个元素对应的Value, 而Key即是该元素。由于采用了Bit为单位来存储数据,因此在存储空间方面,可以大大节省。 适用范围:可进行数据的快速查找,判重,删...

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的实现:
代码如下:

#include "stdafx.h"
#include
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

    
 
 
 
本站(WWW.)旨在分享和传播互联网科技相关的资讯和技术,将尽最大努力为读者提供更好的信息聚合和浏览方式。
本站(WWW.)站内文章除注明原创外,均为转载、整理或搜集自网络。欢迎任何形式的转载,转载请注明出处。












  • 相关文章推荐
  • 海量数据库的查询优化及分页算法方案
  • 海量小文件如何快速读到内存?
  • c中如何存取海量数据?
  • [高手进]海量数据网络通讯,当访问请求达3万以上时,出现coredump错误。一般是什么原因?
  • SQL Server 海量数据导入的最快方法
  • 在 SQLSERVER 中快速有条件删除海量数据
  • 如何在 SQL SERVER 中快速有条件删除海量数据
  • 如何在SQLSERVER中快速有条件删除海量数据
  • 公告:CSDN AIX论坛有奖话题讨论活动(七)——本期话题:在海量运算方面,和Linux系统相比,AIX系统有优势吗?
  • 公告:CSDN AIX论坛五月有奖话题讨论活动(一)——本期话题:海量数据时代,云基础架构的瓶颈有哪些?比如内存、带宽、CPU计算速度、安全性等
  • 海量数据引擎 SF1R
  • mysql 海量数据的存储和访问解决方案
  • 海量数据库查询语句




  • 特别声明:169IT网站部分信息来自互联网,如果侵犯您的权利,请及时告知,本站将立即删除!

    ©2012-2021,,E-mail:www_#163.com(请将#改为@)

    浙ICP备11055608号-3