一、位图
(1)位图概念介绍
先看下面的一道题:
1.有40亿个不重复的无符号整数,无序。给一个无符号整数,如何快速判断一个数是否在这40亿个数中。
如果我们放到哈希表或红黑树中或用排序和二分查找这两种方法。
前两种方法不可行,因为40亿个整数占用大约16G的内存空间,第一要排序需要先把数放到内存,只能用文件归并排,但是不能文件中不能搞二分查找即不能用下标去访问;第二如果放到红黑树但是同样放不进去,如果放到树里面,给一棵树查找一次,但是这里是很多数据,来一个树先读2G查找再释放掉,再来一个树放进去查,不断的查,与其这样不如读的时候判断一下没必要放树里面,直接暴力查找了,还有额外的消耗表里面的结点不光有数据还是有指针。所以上俩种方法不行主要原因就是内存不够。
我们可以用一种直接定址法,我们可以最少用1字节即char标记一个数在不在,一个char数组最少消耗4G,我们还可以最少,即开比特位,比如一个字节开8个比特位,我们也可以开int的,如下图,0到7映射到第一个cha人,8到15映射到第二个char,依次映射,40亿个数,如果是一个整数去存储需要16G,现在是按位去存储,用位去标识,缩小了32倍,也可以这么说,这是40亿个整数看成40亿个比特位,除以8大概就是相当于5亿字节,需要512MB,这里东西就叫位图。
位图:它是一种直接定址法的哈希映射,用来判断整型的在不在的问题,用每一位来存放某种状态,适用于海量数据,数据无重复的场景。
(2)简单模拟实现
template<size_t N>
class bitset
{
public:
bitset()
{
_b.resize(N / 8 + 1, 0);
}
void set(size_t x)
{
size_t i = x / 8;
size_t j = x % 8;
_b[i] |= (1 << j);
}
void reset(size_t x)
{
size_t i = x / 8;
size_t j = x % 8;
_b[i] &= ~(1 << j);
}
bool test(size_t x)
{
size_t i = x / 8;
size_t j = x % 8;
return _b[i] & (1 << j);
}
private:
vector<char> _b;
};
库里面这个函数是有的,我们是不能去按位去开数组的,我们可以用vector数组存储char类型控制char。
我们需要实现里面三个核心接口set和set以及test,set把x映射的那个比特位设置成1,reset把它设置成0,test判断在不在。
初始化构造:我们还需要空间,我们要N个比特位我们需要开N/8,但这样少开一个比特位需要加上1,然后初始都为0。
先实现set:
但是我们怎么去找到对应的比特位?
1、一个字节是8比特位,我们是算它在第几个8比特位,我们可以直接除8算出i即在第i个char数组位置,接着算在第几个8比特第几个上面,可以直接模8算出j即char位置第几个比特位。
2、然后我们把char的第j位设置为1,我们需要进行位运算,我们需要把j位设置成1,其他位不能影响需要用到或,因为或有一个特点0和任何数或还是任何数,我们还需用1进行左移j位,左移是向高位移,最后再或等,这样设置完毕。如下图
实现reset:
同样先算出i和j,想让它第j位设置为0,先左移再取反,但是不能那个影响其它位,就需要按位与等,因为1和1与还是1,0和1与还是0。
实现判断test:
同样先算出i和j,对对应的位置直接与,两种可能性,与之后除了第j位其他位都为0,如果第j位是0,那么结果就是0返回假,如果第j为不是0,那么结果是非0
值,非0值即为真不管是1还是其他非0数,都返回真。注意位运算优先级是很低的需要加括号。
我们测试一下:
那么开头那个问题就可以解决。
(3)位图应用
我们再看几个问题:
2.给100亿个整数,设计算法只出现一次的整数。
部分核心代码:
template<size_t N>
class twobitset
{
public:
void set(size_t x)
{
if (_b1.test(x) == false && _b2.test(x) == false)
{
_b2.set(x);
}
else if (_b1.test(x) == false && _b2.test(x) == true)
{
_b1.set(x);
_b2.reset(x);
}
}
void one_print()
{
for (size_t i = 0; i < N; ++i)
{
if(_b2.test(i))
{
cout << i << endl;
}
}
}
public:
bitset<N> _b1;
bitset<N> _b2;
};
100亿个整数不影响我们开空间,因为可能有重复的,我们可以搞2个位图。出现0次就是00,出现1就是01次,出现1次以上就是10。
直接运用刚才的两个位图,直接复用,两个位进行组合。
_b1和_b2都test一下如果都是00表示没有出现过,就把_b2设置成1即01表示出现了1次,如果是_b1为0,_b2为1就把_b1设置为为,_b2设置为0即10表示出现2次。
接着写个打印函数去找出现1次,N是个范围,只需要遍历,只需要判断_b2是真,就是出现1次,因为01,打印即可
如图:
3.给两个文件,分别有100亿个整数,我们只有1G内存,如何找到两个文件交集?
第一种:可以把其中一个文件的值,读到内存的一个位图中,再读取另一个文件,判断在不在上面位图中,在就是交集。但是找出的交集存在重复的值,还要再次去重。可以改进,每次找到交集,都将上面的位图对应的值设置为0解决重复问题。
第二种:更好的是放到两个位图中,把文件1放到位图1,把文件2放到位图2。
读取文件1的数据映射到位图1,读取文件2的数据映射到位图2,用for循环遍历范围N,如果位图1和位图2都在就是交集。
如果数据量大就选第二种方法,反之第一种。
4.位图应用变形:1个文件有100亿个int,1G内存,设计算法找到出现次数不超过2次的所有整数。
这道类似第二道,用第二道题的思想,出现0次用00表示,出现1用01表示,出现2次用10表示,出现3次以上用11表示。不超过2次的所有整数就去找01和10。
总结:位图也是一种哈希结构,效率很高速度快,O(1),而且还节省内存。
缺点就是:只能映射整型,统计次数也有限。其他类型string,double等不能映射。下面的布隆过滤器就是解决这种问题。
二、布隆过滤器
(1)关于布隆过滤器概念及介绍
如果是大量字符串,位图是没法完成映射的,如果用哈希或红黑树,会有大量消耗,有附带消耗。我们可以用仿函数转成整型,间接映射,但是这样会有一个冲突问题,假如字符串是汉字,字符串的长度是8,会有256^8中组合,会存在多对一冲突。
而布隆过滤器的思想不是解决冲突,而是降低冲突概率,一个值映射一个位置容易误判,映射多个位置就可以降低误判率,即将一个元素用多个哈希函数映射到一个位图中,因此被映射到的位置的比特位一定为1。所以可以按照以下方式进行查找,分别计算每个哈希值对应的比特位置存储的是否为零,只要有一个为零,代表该元素一定不在哈希表中,否则可能在哈希表中。
(2)布隆过滤器的使用场景
首先要找到它的特点,它能容忍误判的场景,比如我们在注册时,快速判断昵称是否使用过。如果没注册过,会立刻给你反馈,说明是准确的;如果它注册过有两种可能性,把昵称放到这个布隆中,第一它真的被用过了,第二它没被用过,存在了误判,但是从用户使用场景上是不知道的,可以允许误判,昵称用户感知不到。
如果是昵称,10亿个用户是存在数据库里面的,数据库的数据本质在磁盘上,快速不判断是不去找磁盘的,因为磁盘IO太慢了,所以我们把昵称全部读到布隆过滤器里面,节省空间,在布隆就直接反馈昵称注册过,不在布隆就反馈没注册过,但是在是会存在误判的,有可能真没被注册过。
如果是手机号,判断不在就直接返回没注册过,不在是准确的,判断在,可能会存在误判,明明没有注册过,这时候要去数据库里面磁盘上确认一下,然后再返回这个结果,以数据库的结果为准。这个跟直接去数据库查找相比,从整体而言效率是高的。因为布隆是在内存当中时间复杂度是O(1),把不在的都快速过滤掉,如果在的话再去找数据库,单拿在的场景多消耗了一点,整而言效率高,减少了数据库的访问。
布隆过滤器为啥叫这个名字,它是先提前做一层过滤,不在就直接走了,在的话再去数据库确认一下再返回。它的优点是快节省内存,缺点存在误判。
如下图:
大部分使用布隆过滤器的数据类型都是用字符串,如果用整型就用位图。
减少磁盘IO和网络请求,一旦一个值必定不存在,就不用进行后面的查询。BF实践当中一般都是做数据过滤,判断在不在,如果不在就不用再往后请求了,如果在继续再往后面请求,如果再次请求数据都在数据库里面,甚至数据库在远程服务器中,还要走一层网络,成本还是蛮高的。
(3)模拟实现
主要先上部分核心代码,后面有原码。
template<size_t N,class K=string,class Hash1= BKDRHash,
class Hash2= APHash,class Hash3= DJBHash>
class BloomFilter
{
public:
void set(const K& key)
{
size_t len = N * _M;
size_t hash1 = Hash1()(key) % len;
_b.set(hash1);
size_t hash2 = Hash2()(key) % len;
_b.set(hash2);
size_t hash3 = Hash3()(key) % len;
_b.set(hash3);
}
bool test(const K& key)
{
size_t len = N * _M;
size_t hash1 = Hash1()(key) % len;
if (!_b.test(hash1))
return false;
size_t hash2 = Hash2()(key) % len;
if (!_b.test(hash2))
return false;
size_t hash3= Hash3()(key) % len;
if (!_b.test(hash3))
return false;
return true;
}
private:
static const size_t _M = 6;
bitset<N*_M> _b;
};
我们在模板里面增加三个hash函数算法,可以在网上搜字符串哈希函数算法,我所取的这个三个hash函数的散列质量及效率是别人进过测试后排在前三的。在set函数里面先给一个哈希映射的第一个位置,把key转成可以去摸的整型值,摸上N,同理3个hash函数,set3个位置。
如果判断在不在,三个位置都要在才在即真,只有一个位置不在就是不在即假。
有一个关键问题:在和不在谁会存在误判?
在是不准确的,会存在误判,如果判断一个位置不在,说明至少有一个位置为0,上面说到只要有一个不在就是不在;如果判断在的话,这个位置不可能为0,三个位置都为1。比如一个字符串,本来不在,但是它映射的位置都跟别人冲突了即都被被人映射了,所以导致认为它在,即误判。
hash函数个数,代表一个值映射几个位,哈希函数越多,误判率越低,但是希函数越多,平均空间越多。
这是下面别人通过实验总结出来的公式,来降低误判率,此图链接来源于:链接。
以上的测试结果可以看出布隆过滤器的长度会直接影响误报率,布隆过滤器越长其误报率越小。哈希函数的个数也需要考虑,但治不了本。因为n插入个数和BF长度存在一个倍数,我们适当增加倍数_M,来验证一下,6是最好的。如图:
找的是不在的字符串去测试,因为本来就在测试时它肯定在,它不在的有可能能会被判断成在,这就是误判,结果是在是不准确的,因为本来不在它会判断成在。
(4)布隆过滤器天生不支持删除reset
因为会对别人造成影响以及其他影响(即使用计数法(由多个比特位控制)也非常不好,不确定删除哪个数据以及本来不在误判成在的数据,把它删了其他的又找不到了),如下图,删除nza,会把2号位置置成0,再查找azn,查找时就不在了,有关联影响。
(5)BF总结
布隆过滤器优点:
1.增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数,一般比较小),与数据量大小无
关
2. 哈希函数相互之间没有关系,方便硬件并行运算
3. 布隆过滤器不需要存储元素本身,在某些对保密要求比较严格的场合有很大优势
4. 在能够承受一定的误判时,布隆过滤器比其他数据结构有这很大的空间优势
5. 数据量很大时,布隆过滤器可以表示全集,其他数据结构不能
6. 使用同一组散列函数的布隆过滤器可以进行交、并、差运算
布隆过滤器缺陷
1.有误判率,即存在假阳性(False Position),即不能准确判断元素是否在集合中(补救方法:再
建立一个白名单,存储可能会误判的数据)
2.不能获取元素本身
3.一般情况下不能从布隆过滤器中删除元素
4.如果采用计数方式删除,可能会存在计数回绕问题
三、海量数据处理
(1) 哈希切割
(1)问题1/2
1.给两个文件,分别有100亿个query,我们只有1G内存,如何找到两个文件交集?分别给出精确算法和近似算法
这里是找交集,不是整型的是字符串。
近似算法:就是之前说的,先把一个文件的数据放到BF中,再去找交集判断在不在,在就是交集,当然后面还有去重的需求。
精确算法:query本质就是一个字符串,假设单个query平均50字节,100亿个就是500G。我们可以如下图把文件A和B文件分别切成1000份(linux指令就可以切,写一个进程帮我们执行切文件的指令。),这样做还是要和每个文件找交集,所以我们可以用hash切分,用一个哈希函数计算出每个文件对应的i即文件号,然后让A0和B0,A1和B1依次找交集,只需要编号相同的小文件直接去找交集,因为一个一个的小文件就像一个桶,进入同一个桶都是冲突的值,A和B相同字符串会进去编号的相同小文件,而且我们用的是相同hash函数。
但是会有一个问题:
某些小文件不是平均切分,可能会出现冲突过多,某个Ai,Bi小文件过大,太大加载不去内存,如果换个哈希函数再切,前提还是要算出这个两个文件多大,才决定你要切多少份,更重要的问题是继续换哈希函数可能切不动,因为有大量重复,而且这里还有两种可能:
第一种可能单个文件有大量重复的query字符串
第二种可能有大量不同的query。
第一种重复的值不管用什么哈希函数都切不动,第二种大量不同的字符串肯定可以继续用哈希函数切分,主要是怎么区分,要分别处理,
解决:
我们可以这样直接使用一个unordered_set/set,依次读取文件query,插入set中
如果读取整个小文件query,都可以成功插入,那就是第一种,因为set插入key,如果有了返回false,没有继续插返回true,插入过程是不会失败的。
如果读取整个小文件query,插入过程抛异常,说明内存满了装不下,会抛bad_alloc异常,那就是第二种,要换其他哈希函数,再次分割,再求交集。
2.如何扩展BloomFilter使得它支持删除元素的操作
把每个映射的值改成引用计数,每个值由多个比特位组成,如01,10,11,分别代表1次,2次。3次,往上加,取决于用几个比特位。但其实没必要,会浪费空间,本身就不支持删除。
(2)问题3/4
3.给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址?
还是一样的,哈希切分500份,依次读取数据,Hash函数计算出i,这个ip就是第i个小文件,直接用unordered_map/map统计出现次数。
如果某个过程中,出现抛异常,则说明单个文件小文件过大,冲突太多,需要重新换哈希函数,再次哈希切分这个小文件,比如这个单个小文件10G再切个30份,AA0到AA29,再生成小文件,和处理源文件的逻辑是一样的;没有异常正常统计,统计完一个小文件,记录最大的,clear,再统计下一个文件。
(3)问题3
4.与上题条件相同,如何找到top K的IP?
找次数最多IP,可以建一个K个数的小堆,小堆每一个位置是pair,key是ip,value是次数,如果比你大我就进去。
总结:相同的IP一定进入相同小文件,读取单个小文件,就可以统计IP出现次数。
四、所有源码(含BF)
bitset.h文章来源:https://www.toymoban.com/news/detail-493949.html
#pragma once
#include<vector>
#include<string>
#include<iostream>
#include<ctime>
using namespace std;
namespace nza
{
template<size_t N>
class bitset
{
public:
bitset()
{
_b.resize(N / 8 + 1, 0);
}
void set(size_t x)
{
size_t i = x / 8;
size_t j = x % 8;
_b[i] |= (1 << j);
}
void reset(size_t x)
{
size_t i = x / 8;
size_t j = x % 8;
_b[i] &= ~(1 << j);
}
bool test(size_t x)
{
size_t i = x / 8;
size_t j = x % 8;
return _b[i] & (1 << j);
}
private:
vector<char> _b;
};
void test1()
{
bitset<100> bs;
bs.set(6);
bs.set(15);
bs.set(66);
cout << bs.test(6) << endl;
cout << bs.test(7) << endl;
cout << bs.test(66) << endl;
cout << endl;
}
template<size_t N>
class twobitset
{
public:
void set(size_t x)
{
if (_b1.test(x) == false && _b2.test(x) == false)
{
_b2.set(x);
}
else if (_b1.test(x) == false && _b2.test(x) == true)
{
_b1.set(x);
_b2.reset(x);
}
}
void one_print()
{
for (size_t i = 0; i < N; ++i)
{
if(_b2.test(i))
{
cout << i << endl;
}
}
}
public:
bitset<N> _b1;
bitset<N> _b2;
};
void test2()
{
int a[] = { 6, 22, 99, 88, 6, 4, 3, 22, 5,};
twobitset<100> tb;
for (auto e : a)
{
tb.set(e);
}
tb.one_print();
cout << endl;
}
struct BKDRHash
{
size_t operator()(const string& s)
{
size_t hash = 0;
for (auto ch : s)
{
hash += ch;
hash *= 31;
}
return hash;
}
};
struct APHash
{
size_t operator()(const string& s)
{
size_t hash = 0;
for (long i = 0; i < s.size(); i++)
{
size_t ch = s[i];
if ((i & 1) == 0)
{
hash ^= ((hash << 7) ^ ch ^ (hash >> 3));
}
else
{
hash ^= (~((hash << 11) ^ ch ^ (hash >> 5)));
}
}
return hash;
}
};
struct DJBHash
{
size_t operator()(const string& s)
{
size_t hash = 5381;
for (auto ch : s)
{
hash += (hash << 5) + ch;
}
return hash;
}
};
template<size_t N,class K=string,class Hash1= BKDRHash,
class Hash2= APHash,class Hash3= DJBHash>
class BloomFilter
{
public:
void set(const K& key)
{
size_t len = N * _M;
size_t hash1 = Hash1()(key) % len;
_b.set(hash1);
size_t hash2 = Hash2()(key) % len;
_b.set(hash2);
size_t hash3 = Hash3()(key) % len;
_b.set(hash3);
}
bool test(const K& key)
{
size_t len = N * _M;
size_t hash1 = Hash1()(key) % len;
if (!_b.test(hash1))
return false;
size_t hash2 = Hash2()(key) % len;
if (!_b.test(hash2))
return false;
size_t hash3= Hash3()(key) % len;
if (!_b.test(hash3))
return false;
return true;
}
private:
static const size_t _M = 6;
bitset<N*_M> _b;
};
void test_BF1()
{
BloomFilter<100> b;
b.set("nza");
b.set("zan");
b.set("qwe");
b.set("ewq");
cout << b.test("nza") << endl;
cout << b.test("zan") << endl;
cout << b.test("qwe") << endl;
cout << b.test("ewq") << endl;
cout << b.test("kd") << endl;
}
void test_BF2()
{
srand(time(0));
const size_t N = 10000;
BloomFilter<N> bf;
std::vector<std::string> v1;
std::string url = "https://www.education.com/-kd/2023/06/12/66666.html";
for (size_t i = 0; i < N; ++i)
{
v1.push_back(url + std::to_string(i));
}
for (auto& str : v1)
{
bf.set(str);
}
std::vector<std::string> v2;
for (size_t i = 0; i < N; ++i)
{
std::string url = "https://www.education.com/-kd/2023/06/12/66666.html";
url += std::to_string(999999 + i);
v2.push_back(url);
}
size_t n2 = 0;
for (auto& str : v2)
{
if (bf.test(str))
{
++n2;
}
}
cout << "相似字符串误判率:" << (double)n2 / (double)N << endl;
std::vector<std::string> v3;
for (size_t i = 0; i < N; ++i)
{
string url = "https://editor.csdn.net/md?articleId=131012473";
url += std::to_string(i + rand());
v3.push_back(url);
}
size_t n3 = 0;
for (auto& str : v3)
{
if (bf.test(str))
{
++n3;
}
}
cout << "不相似字符串误判率:" << (double)n3 / (double)N << endl;
}
}
test.cpp文章来源地址https://www.toymoban.com/news/detail-493949.html
#include"bitset.h"
int main()
{
nza::test1();
nza::test2();
nza::test_BF1();
nza::test_BF2();
return 0;
}
到了这里,关于C++【位图/布隆过滤器—海量数据处理】的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!