学习笔记------海量数据处理题集锦与bit-map详解

By | 05月09日
Advertisement

最近学习了“海量数据处理题集锦与bit-map详解” 这篇网文,在此摘取文章中的一些内容作为笔记。

什么是Bit-map

所谓的Bit-map就是用一个bit位来标记某个元素对应的Value, 而Key即是该元素。由于采用了Bit为单位来存储数据,因此在存储空间方面,可以大大节省。

如果说了这么多还没明白什么是Bit-map,那么我们来看一个具体的例子,假设我们要对0-7内的5个元素(4,7,2,5,3)排序(这里假设这些元素没有重复)。那么我们就可以采用Bit-map的方法来达到排序的目的。要表示8个数,我们就只需要8个Bit(1Bytes),首先我们开辟1Byte的空间,将这些空间的所有Bit位都置为0(如下图:)

学习笔记------海量数据处理题集锦与bit-map详解

然后遍历这5个元素,首先第一个元素是4,那么就把4对应的位置为1(可以这样操作 p+(i/8)|(0×01<<(i%8)) 当然了这里的操作涉及到Big-ending和Little-ending的情况,这里默认为Big-ending),因为是从零开始的,所以要把第五位置为一(如下图):

学习笔记------海量数据处理题集锦与bit-map详解

然后再处理第二个元素7,将第八位置为1,,接着再处理第三个元素,一直到最后处理完所有的元素,将相应的位置为1,这时候的内存的Bit位的状态如下:

学习笔记------海量数据处理题集锦与bit-map详解

然后我们现在遍历一遍Bit区域,将该位是一的位的编号输出(2,3,4,5,7),这样就达到了排序的目的。下面的代码给出了一个BitMap的用法:排序。

//定义每个Byte中有8个Bit位   #include <memory.h>   #define BYTESIZE 8   void SetBit(char *p, int posi)   {       for(int i=0; i < (posi/BYTESIZE); i++)       {           p++;       }          *p = *p|(0x01<<(posi%BYTESIZE));//将该Bit位赋值1       return;   }      void BitMapSortDemo()   {       //为了简单起见,我们不考虑负数       int num[] = {3,5,2,10,6,12,8,14,9};          //BufferLen这个值是根据待排序的数据中最大值确定的       //待排序中的最大值是14,因此只需要2个Bytes(16个Bit)       //就可以了。       const int BufferLen = 2;       char *pBuffer = new char[BufferLen];          //要将所有的Bit位置为0,否则结果不可预知。       memset(pBuffer,0,BufferLen);       for(int i=0;i<9;i++)       {           //首先将相应Bit位上置为1           SetBit(pBuffer,num[i]);       }          //输出排序结果       for(int i=0;i<BufferLen;i++)//每次处理一个字节(Byte)       {           for(int j=0;j<BYTESIZE;j++)//处理该字节中的每个Bit位           {               //判断该位上是否是1,进行输出,这里的判断比较笨。               //首先得到该第j位的掩码(0x01<<j),将内存区中的               //位和此掩码作与操作。最后判断掩码是否和处理后的               //结果相同               if((*pBuffer&(0x01<<j)) == (0x01<<j))               {                   printf("%d ",i*BYTESIZE + j);               }           }           pBuffer++;       }   }      int _tmain(int argc, _TCHAR* argv[])   {       BitMapSortDemo();       return 0;   }

可进行数据的快速查找,判重,删除,一般来说数据范围是int的10倍以下

基本原理及要点

使用bit数组来表示某些元素是否存在,比如8位电话号码

扩展

Bloom filter可以看做是对bit-map的扩展(关于Bloom filter,请参见:海量数据处理之Bloom filter详解)。

问题实例

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,都是一样的道理。

原文的连接

http://blog.csdn.net/v_july_v/article/details/6685962

http://blog.redfox66.com/post/2010/09/26/mass-data-4-bitmap.aspx

Similar Posts:

  • 【Ext.Net学习笔记】03:Ext.Net DirectEvents用法详解、DirectMethods用法详解

    Ext.Net通过DirectEvents进行服务器端异步的事件处理.[Ext.Net学习笔记]02:Ext.Net用法概览.Ext.Net MessageBus用法.Ext.Net布局 中已经简单的介绍了DirectEvents,今天将详细的介绍一下DirectEvents. DirectEvents异步执行服务器端事件 我们首先来看一下Ext.Net DirectEvents的一个最简单用法,通过点击按钮触发服务器端的事件处理方法,并在前台弹出一个提示框. <ext:Window runat

  • TCP/IP学习笔记(入门篇)(摘自VC++深入详解)

    TCP/IP学习笔记(入门篇) 协议需求 传输层:传输控制协议TCP.用户数据报协议UDP. 协议UDP:无需建立连接,没有数据确认和重传机制,实时性高,多用于视频会议. 协议TCP:安全性高,数据完整性好. 数据封装 打包数据叫做封装.封装就是在数据前面加上特定的协议头部.OSI数据模型中,对等层协议之间的交换的信息单元统称为协议数据单元.OSI参考模型中每一层都要依靠下一层提供的服务. TCP/IP模型 7层的OSI模型,TCP/IP为4层模型. 4个层次:应用层,传输层,网络层,网络接口层

  • 《应届生求职笔试全攻略》学习笔记(七)——招聘笔试题分类详解

    十一.情景模拟题 将情景模拟应用于人才选拔是基于心理学家勒温的著名公式:B=f(P,E) 这个公式的意思是说:一个人的行为(Behavior)是其人格或个性(Personality)与其当时所处情景或环境(Environment)的函数.换句话说,候选者面试时的表现是由他们自身的素质和当时面对的情景共同决定的.如果考官能够恰当地选择情景并保证情景对不同候选者的一致性,那么,不仅可以诱发候选者的相应行为,而且能够说明候选者行为的不同是由其素质不同所致.这种面试题是没有标准答案的,它主要是考查面试者

  • 【Struts2学习笔记(13)】Struts2中OGNL详解

    一.OGNL表达式语言 (1)OGNL是Object Graphic Navigation Language(对象图导航语言)的缩写,它是一个开源项目. Struts 2框架使用OGNL作为默认的表达式语言. (2)相对EL表达式,它提供了平时我们需要的一些功能,如: 1.支持对象方法调用,如xxx.sayHello(): 2.支持类静态方法调用和值访问,表达式的格式为@[类全名(包括包路径)]@[方法名 | 值名],例如:@[email protected]('foo %s', '

  • Spring学习笔记(十) Spring MVC之@RequestParam @RequestBody @RequestHeader 详解

    引言: 接上一篇文章,对@RequestMapping进行地址映射讲解之后,该篇主要讲解request 数据到handler method 参数数据的绑定所用到的注解和什么情形下使用: 简介: handler method 参数绑定常用的注解,我们根据他们处理的Request的不同内容部分分为四类:(主要讲解常用类型) A.处理requet uri 部分(这里指uri template中variable,不含queryString部分)的注解: @PathVariable; B.处理reques

  • JMeter学习-025-JMeter 命令行(非GUI)模式详解(三)-测试图形化 HTML 报表(dashboard)生成

    JMeter学习-025-JMeter 命令行(非GUI)模式详解(三)-测试图形化 HTML 报表(dashboard)生成 http://www.cnblogs.com/fengpingfan/p/5589635.html      6.生成测试报表   生成测试报表前,需要先生成性能测试结果 jtl 或 csv 文件,用于测试结果的生成. jmeter -n -t JMeter分布式测试示例.jmx -r -l report\01-result.csv -j report\01-log.l

  • ARM学习笔记3——数据处理指令

    一.数据处理指令概述 1.概念 数据处理指令是指对存放在寄存器中的数据进行处理的指令.主要包括算术指令.逻辑指令.比较与测试指令以及乘法指令 如果在数据处理指令前使用S前缀,指令的执行结果将会影响CPSR中的标志位. 2.语法格式 数据处理指令的基本语法格式 <opcode>{<condition>}{S} <Rd>,<Rn>,<shifter_operand> 3.参数说明 <S>:标志指令的条件域是否更新CPSR <Rn&g

  • [Java] 学习笔记一(String,for循环,多线程,正则表达式,map用法)

    String String.equals (String) 判断两个字符串对象的内容是否相同. 值得注意的是,String.equals与'=='操作不同.前者比较的是两者的内容是否相同,而后者比较的是两者的地址是否相同.举个栗子, public class stringtest { public static void main(String[] args){ String S1=new String("abc"); String S2="abc"; System

  • 【Linux学习笔记四】磁盘管理中文件压缩与解压

    [注]文章中的所有截图均为centos下实验结果,亲测命令正确= ̄ω ̄= [参考资料]<Linux从入门到精通(第2版)>刘忆智 等编著 1.查看磁盘使用情况:df可以显示当前挂载的文件系统的统计数据,但信息繁杂,可以用带 -t 的 df 命令显示特点的文件系统信息.      $ df            ##显示挂载文件系统的名称.容量.已用.可用.已用百分比.挂载路径      $ df -t ext4            ##ext4文件系统信息 [转载请注明文章出处:http:/

  • java核心知识点学习----多线程间的数据共享和对象独立,ThreadLocal详解

    线程内的数据共享与对象独立,举例:张三给李四转钱,开启A线程去执行转钱这个动作,刚好同时王五给赵六转钱,开启B线程去执行转钱,因为是调用的同样一个动作或者说对象,所以如果不能保证线程间的对象独立,那么很有可能发生,张三给李四转钱时把王五转给赵六的转钱一块提交了,而王五转钱整个动作还未完成,那么就造成了转钱错误, 所以线程间一方面要保证数据的共享,另一方面要保证对象的对立. 1.用Map封装对象以数据实现共享 package com.amos.concurrent; import java.uti

Tags: