你好,游客 登录 注册 搜索
背景:
阅读新闻

Bit-map法处理大数据问题

[日期:2015-08-17] 来源:博客园  作者:灵感之源 [字体: ]

问题引入:

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类,可以通过构造对象时传入数据规模,动态申请所需的内存,然后处理用户的大量数据:

复制代码
  1 #include<iostream>
  2 #include<fstream>
  3 #include<ctime>
  4 using namespace std;
  5 const unsigned SIZE = 512000000;//512兆静态存储区可处理40.96亿数据
  6 
  7 class Bitmap {
  8     typedef struct Byte {
  9         unsigned char bit8;
 10         static const unsigned char mask[9];//用来取得一个字节每一位的辅助数组
 11         Byte()
 12         {
 13             bit8 = 0;
 14         }
 15         //设置该位,就是存储该数
 16         void set1(unsigned at)
 17         {
 18             bit8 |= mask[at];
 19         }
 20         //读取该位是否有数
 21         bool get1(unsigned at)
 22         {
 23             return bit8 & mask[at];
 24         }
 25     } Byte;
 26     Byte *m_byte;
 27     unsigned m_size;
 28 public:
 29     Bitmap(unsigned _size)
 30     {
 31         m_byte = new Byte[(_size+7)/8];
 32         m_size = _size;
 33     }
 34     virtual ~Bitmap()
 35     {
 36         delete[] m_byte;
 37         m_size = 0;
 38     }
 39     //存储一个数据
 40     bool push(unsigned data)
 41     {
 42         if(data>=m_size)
 43             return false;
 44         m_byte[data/8].set1(data%8);
 45         return true;
 46     }
 47     //读取一个数据是否存在
 48     bool find(unsigned data)
 49     {
 50         return data>=m_size ? 0 : m_byte[data/8].get1(data%8);
 51     }
 52     //返回能存储的数据个数
 53     unsigned size()
 54     {
 55         return m_size;
 56     }
 57     //重载运算符实现常用功能
 58     //存储一个数据
 59     bool operator>>(unsigned data)
 60     {
 61         return push(data);
 62     }
 63     //读取一个数据是否存在
 64     bool operator<<(unsigned data)
 65     {
 66         return find(data);
 67     }
 68     //访问到某个数据块
 69     Byte& operator[](unsigned i)
 70     {
 71         if(i>=m_size/8)
 72             throw "index out of range";
 73         return m_byte[i];
 74     }
 75 };
 76 const unsigned char Bitmap::Byte::mask[9] = {0x80,0x40,0x20,0x10,0x8,0x4,0x2,0x1};//用来取得一个字节每一位的辅助数组
 77 
 78 int main()
 79 {
 80     Bitmap bitmap(8*SIZE);//可以存储40+亿数据
 81     ifstream file("in.txt");//从文件内录入一些整数
 82     unsigned read, i=0, t1 = clock();
 83     for(i=0; i<SIZE; ++i)
 84         if(file>>read)
 85             bitmap>>read;
 86         else
 87             break;
 88     file.close();
 89     cout<<"共存储"<<i/10000<<"W 数据, "<<"耗时: "<<clock()-t1<<"ms"<<endl;
 90     t1 = clock();
 91     for(i=0; i<1000000; ++i)
 92         if(bitmap<<i)
 93             ;
 94     cout<<"访问"<<i/10000<<"W 数据共耗时: "<<clock()-t1<<"ms"<<endl;
 95     cout<<"请输入需要检索的数据:"<<endl;
 96     while(cin>>read) {
 97         if(bitmap<<read)
 98             cout<<"已存储"<<read<<endl;
 99         else
100             cout<<"Error: 未存储"<<read<<endl;
101     }
102     return 0;
103 }
复制代码

 运行结果如下:

在程序中,先读取一个文本文件中随机产生的6W个整数,存到这个bitmap中,然后测试了一下从这个建立好的bitmap中查找100W数据耗时情况(11ms左右),接下来的部分是用户可以手动输入一些整数,程序会自动检索bitmap中是否已存储该数据。

这样就可以解决引入话题中的第一个问题了,把输入的文本数据改为已知的40亿数据就可以了(40亿数据的录入可能需要一会儿,大概1300秒)。

下面给出引入的剩余三个问题的解题思路。

问题2:先建立一个足够大的Bitmap对象,然后依次录入这些数据,如果录入某数据前发现该位已经为1,则该数据重复,依次得到重复的数据即可。

问题3:先建立一个足够大的Bitmap对象,然后依次录入这些数据,从Bitmap开始位置起遍历,如果某位不为0,则表示有该数据,依次输出不为0的位的位序就是排序好的数组(输出太多没意义,可以将输出转换到写入文件,那么新文件中数据就是排序好的)。

问题4:方法1,建立2个足够大的Bitmap对象,依次录入数据,录入前先判断 该数据在bitmap1中是否存在(即对应位是否为1),不存在则录入到bitmap1中,存在就录入到bitmap2中;全部录入完后,依次遍历 bitmap1中每一位,如果某一位为1但是bitmap2中对应位不为1,则表示该数据只出现过一次,依次输出即可。

          方法2,建立一个足够大的Bitmap对象,不过用两位表示一个数据,00表示数据不存在,01数据出现一次,10表示数据出现多次。11呢?一边凉快去 吧,不要你了,哈哈。这样依次录入数据时,如果该对应位(其实是两位)为00则改为01,01就改为10,10就不管了。录入完成后,遍历整个 bitmap,找到01位就输出。

  好了,常见的大数据题目就通过bitmap这个神奇的结构给解决了,不过 bitmap也不是万能的,很明显,它暂时只适合存储整形数据,当然这里只考虑了unsigned类型数据,如果是int类型的话,对应映射一下就可以了 也是没问题的。不过即使如此,也只能处理10亿级别的数据,如果数据量更大、类型不只是整形呢?

  比如:需要写一个网络蜘蛛(web crawler)。由于网络间的链接错综复杂,蜘蛛在网络间爬行很可能会形成“环”。为了避免形成“环”,就需要知道蜘蛛已经访问过哪那些URL。给一个URL,怎样知道蜘蛛是否已经访问过?

  不难想到如下几种方案:

  1. 将访问过的URL全部保存到数据库;

  2. 用HashSet将访问过的URL保存起来。那只需接近O(1)的代价就可以查到一个URL是否被访问过;

  3. URL经过MD5或SHA-1等单向哈希后再保存到HashSet或数据库。

  4. Bit-Map方法。建立一个BitSet,将每个URL经过一个哈希函数映射到某一位。

  方法1~3都是将访问过的URL完整保存,方法4则只标记URL的一个映射位。

  以上方法在数据量较小的情况下都能完美解决问题,但是当数据量变得非常庞大时问题就来了。

  方法1:数据量变得非常庞大后关系型数据库查询的效率会变得很低。而且每来一个URL就启动一次数据库查询是不是太小题大做了?

  方法2:太消耗内存。随着URL的增多,占用的内存会越来越多。就算只有1亿个URL,每个URL只算50个字符,就需要5GB内存。

  方法3:由于字符串经过MD5处理后的信息摘要长度只有128Bit,SHA-1处理后也只有160Bit,因此方法3比方法2节省了好几倍的内存。

  方法4:消耗内存是相对较少的,但缺点是单一哈希函数发生冲突的概率太高。还记得数据结构课上学过的Hash表冲突的各种解决方法么?若要降低冲突发生的概率到1%,就要将BitSet的长度设置为URL个数的100倍。

  但是我们可以考虑如果在一定程度上忽略误判的情况,那么是不是可以通过改进方法4实现这一功能?其实这就是Bloom Filter的算法 的 思想:Bloom Filter是由Bloom在1970年提出的一种多哈希函数映射的快速查找算法。通常应用在一些需要快速判断某个元素是否属于集合,但是并不严格要求 100%正确的场合。其思想就是在方法4基础上做了一些改进,不是映射到一位,而是通过K个哈希函数映射到K位上,这样只有当新的URL计算得到的K位都 为1时才判断为该URL已经访问过(有误判的可能性,不过有相关研究证明,取得合适的K值和bitmap位数时可以让误判率很小以至于可以忽略,参见细节)

  当然,还可以通过map-reduce来处理,毕竟人家mapreduce可是行家,专业的大数据处理技术嘛!

  参考文献:

  Bitmap位图法

  BloomFilter——大规模数据处理利器

  BloomFilter概念及原理 

  欢迎浏览我的博客,小生初来乍到,哪里有问题请多多指教,转载请注明出处!http://www.cnblogs.com/webary/p/4733247.html





收藏 推荐 打印 | 录入:Cstor | 阅读:
本文评论   查看全部评论 (4)
表情: 表情 姓名: 字数
点评:
       
评论声明
  • 尊重网上道德,遵守中华人民共和国的各项有关法律法规
  • 承担一切因您的行为而直接或间接导致的民事或刑事法律责任
  • 本站管理人员有权保留或删除其管辖留言中的任意内容
  • 本站有权在网站内转载或引用您的评论
  • 参与本评论即表明您已经阅读并接受上述条款