武汉c培训
达内武汉中心

15271940953

热门课程

武汉C++培训:位图&布隆过滤器

  • 时间:2016-05-25
  • 发布:fun
  • 来源:51CTO

位图定义:

  利用位的状态来存放一个数是否存在,其实就是把一个数映射成一个简单的数用以标记他是否存在,一般使用情况为查找一个数是否存在。

数据结构:

1/8=0    1%8=1   1<<1(第二个bit位置1)

2/8=0    2%8=2   1<<2(第3个bit位置1)

3/8=0    3%8=3  1<<3(第4个bit位置1)

4/8=0    ....

查找这个数是否存在:

  先算出这个数的存在位置,然后找这个位置是否为1,如果是则存在否则不存在。

缺点:可读性差。

应用:
    1、给40亿个不重复的unsigned int的整数,没排过序的,然后再给一个数,如何快速判断这个数是否在那40亿个数当中
将这40亿个数字存储到bitmap中,然后对于给出的数,判断是否在bitmap中即可。
    2、使用位图法判断整形数组是否存在重复
      遍历数组,一个一个放入bitmap,并且检查其是否在bitmap中出现过,如果没出现放入,否则即为重复的元素。
    3、使用位图法进行整形数组排序
      首先遍历数组,得到数组的最大最小值,然后根据这个最大最小值来缩小bitmap的范围。这里需要注意对于int的负数,都要转化为unsigned int来处理,而且取位的时候,数字要减去最小值。
    
#define  _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
#include<vector>
class BitMap
{
public:
BitMap(size_t size)
{
_bm.resize(size / 32 + 1);
_size = 0;
}
BitMap()
:_size(0)
{}
void Set(size_t num)
{
size_t index = num >> 5;
if ((_bm[index] & 1 << (num % 32)) == 0)
{
_bm[index] |= 1 << (num % 32);
++_size;
}
}
void Reset(size_t num)
{
size_t index = num >> 5;
if ((_bm[index] & (1 << (num % 32))) == 1 << (num % 32))
{
_bm[index] &= ~(1 << (num % 32));
--_size;
}
}
bool Test(size_t num)
{
size_t index = num >> 5;
if ((_bm[index] & (1 << (num % 32))) == 1 << (num % 32))
{
return true;
}
return false;
}
size_t Size()
{
return _size;
}
private:
vector<unsigned int> _bm;
size_t _size;
};
//
//void test()
//{
//BitMap x(100);
//x.Set(0);
//x.Set(1);
//x.Set(2);
//x.Set(3);
//x.Set(4);
//x.Set(5);
//x.Reset(1);
//x.Reset(3);
//int ret=x.Test(4);
//
//
//}
//int main()
//{
//test();
//system("pause");
//return 0;
//}

利用上述的位图实现布隆过滤器:

仿函数:

   就是使一个类的使用看上去像一个函数。其实现就是类中实现一个operator(),这个类就有了类似函数的行为,就是一个仿函数类了。

布隆过滤器:

  布隆过滤器(Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法,缺点是有一定的误识别率和删除困难。

应用场景:

     字处理软件中,需要检查一个英语单词是否拼写正确(也就是要判断 它是否在已知的字典中);在 FBI,一个嫌疑人的名字是否已经在嫌疑名单上;在网络爬虫里,一个网址是否被访问过等等。最直接的方法就是将集合中全部的元素存在计算机中,遇到一个新 元素时,将它和集合中的元素直接比较即可。一般来讲,计算机中的集合是用哈希表(hash table)来存储的。它的好处是快速准确,缺点是费存储空间。当集合比较小时,这个问题不显著,但是当集合巨大时,哈希表存储效率低的问题就显现出来 了。

优点:

           布隆过滤器存储空间和插入/查询时间都是常数。另外, Hash 函数相互之间没有关系,方便由硬件并行实现。布隆过滤器不需要存储元素本身,在某些对保密要求非常严格的场合有优势。

缺点:

     误算率。随着存入的元素数量增加,误算率随之增加。
    
#define  _CRT_SECURE_NO_WARNINGS
#include"Map.h"
#include<string>

上一篇:武汉C++培训:c++晚捆绑的实现机制
下一篇:武汉C++培训:对象在使用之前的初始化
选择城市和中心
贵州省

广西省

海南省