#include<time.h>
#include<string>
#include<vector>
#include<iostream>
using std::cout;
using std::endl;
using std::string;
namespace test
{
/**位图概念
* 所谓位图，就是用每一位来存放某种状态，适用于海量数据，数据无重复的场景。通常是用来判断某个数据存不存在的。
*
* 位图的应用
* 1. 快速查找某个数据是否在一个集合中
* 2. 排序 + 去重
* 3. 求两个集合的交集、并集等
* 4. 操作系统中磁盘块标记
* 如果能够映射到位图,则会使等价的数据量大大减小,使其能够进入内存
* 位图效率极高,时间复杂度O(1),节省内存
*
* 缺点:只能映射整型
*
*/
template<size_t N> // 非类型模板参数 -- N一般给最大值
class bitset //位图可以叫做bitmap好点,不过stl叫做bitset
{
/** 位图
*
* 位图在C++标准库std中
* https://legacy.cplusplus.com/reference/bitset/bitset/
*
* 位图功能:
* $ 能够操作比特位,在某些场景下能使消耗空间大大 减小,足以容纳进内存,快速执行
*
*
* 需要实现的功能:
* 1.接收数用于开辟多大空间 -- 非类型模板参数 -- 根据不同情况传不同的值,位图还有很多功能,如果计算无符号整型需要传整型最大值
* 2.能够对位图某一比特位 置零 -- reset
* 3.能够对位图某一比特位 置1 -- set
* 4.能够得知某一比特位是0还是1 -- return bool ret
*
* 成员
* 1.成员:char数组 - vectot
*
* 位图调试,在监视窗口中获取原始视图的指针,然后从数组首地址开始看内存,内存是从右往左,从上往下看 ,两个字母为1个字节,字节内按二进制写法
*
*/
private:
std::vector<char> _bits; //不允许访问,因为实现位图必须通过特殊操作
public:
bitset()
{
//1.求所需要的字节数,需要至少有N个bit位,而8bit一个字节,所以至少需要N/8个字节,由于会截断,故需要+1
//2.必须全部置成0,或者1(如果逻辑全部取反的话)
_bits.resize(N / 8 + 1, 0);
}
void set(size_t x) //置1
{
int i = x / 8; //确定下标
int j = x % 8; //确定该字节内的第几位 -- 用来左移,定位到第j比特位
//置1 对左移j位 进行或运算
_bits[i] |= 1 << j;
}
void reset(size_t x) //置0
{
int i = x / 8; //确定下标
int j = x % 8; //确定该字节内的第几位 -- 用来左移,定位到第j比特位
//置0: 对取反后的左移j位的1 进行与运算
_bits[i] &= ~(1 << j);
}
bool test(size_t x) //返回x所在的位是0或1 //标准库就叫做test
{
int i = x / 8; //确定下标
int j = x % 8; //确定该字节内的第几位 -- 用来左移,定位到第j比特位
return _bits[i] & (1 << j);
}
//bitset& filp(size_t x = N) //翻转全部bit位或某一位
//{
//}
};
void test_bitset1()
{
test::bitset<100> bs;//测试用
//test::bitset<-1> bs;//无符号整型最大值 -- 和size_t npos = -1 一样 -- 可以看资源管理器,开的内存空间
bs.set(10);
bs.set(11);
bs.set(15);
cout << bs.test(10) << endl;
cout << bs.test(11) << endl;
bs.reset(10);
bs.reset(11);
cout << bs.test(10) << endl;
cout << bs.test(11) << endl;
}
}
namespace test2
{
/** 位图扩展
*
* 位图玩法多种多样,多练习才能驾驭
*
*
*/
template<size_t N>
class twobitset //开了两个位图的封装
{
public:
void set(size_t x)
{
/** 原理
* 通过双位图,给三种状态 00,01,10;
* 00代表 0次
* 01代表 1次
* 10代表 2次及以上
*
* 个位用bs1控制,十位用bs2控制
* 示例图如:
* _bs1:▭▭▭▭▭▭▭▭▭▭011
* _bs2:▭▭▭▭▭▭▭▭▭▭101
*
*/
if (_bs1.test(x) == false && _bs2.test(x) == false)
{
_bs1.set(x);
}
else if (_bs1.test(x) == true && _bs2.test(x) == false)
{
_bs1.reset(x);
_bs2.set(x);
}
}
bool test(size_t x)
{
return _bs1.test(x) == true && _bs2.test(x) == false;//由题,只出现1次返回真
}
private:
test::bitset<N> _bs1; //已经初始化成0了
test::bitset<N> _bs2;
};
void test_twobitset1()
{
int a[] = { 3, 45, 53, 32, 32, 43, 3, 2, 5, 2, 32, 55, 5, 53,43,9,8,7,8 };
test2::twobitset<100> bs;
for (auto i : a)
{
bs.set(i);
}
for (auto i : a)
{
if (bs.test(i))
{
cout << i << " ";
}
}
}
}
//---------------------------------------------------------------------------------------------------------
//布隆过滤器 --- 解决:某样东西一定不存在或者可能存在
/**
* 布隆过滤器提出
* 我们在使用新闻客户端看新闻时，它会给我们不停地推荐新的内容，它每次推荐时要去重，去掉
* 那些已经看过的内容。问题来了，新闻客户端推荐系统如何实现推送去重的？ 用服务器记录了用
* 户看过的所有历史记录，当推荐系统推荐新闻时会从每个用户的历史记录里进行筛选，过滤掉那
* 些已经存在的记录。 如何快速查找呢？
* 1. 用哈希表存储用户记录，缺点：浪费空间
* 2. 用位图存储用户记录，缺点：位图一般只能处理整形，如果内容编号是字符串，就无法处理
* 了。
* 3. 将哈希与位图结合，即布隆过滤器
* 解决:将所有广告都映射到布隆过滤器中,然后在匹配和比对
*
* 对于字符串的组合有265^n种,n为长度,n如果很大,那将会比无符号整型最大值大很多,所以一般的数据结构是不能支持的
* 单纯使用位图,也一定会存在冲突(有重复的哈希值)问题,位图是不允许冲突的,哈希的话空间开销太大
*
* 布隆过滤器就是在位图和哈希的基础上结合而成,对一个数据计算多个哈希映射到位图上,即一个数据占了位图的多个bit
* 主要目的是降低冲突的概率,允许误判,不是根绝冲突的发生
*
* 布隆过滤器不存在一定是正确的,存在可能是误判 -- 冲突
*
* 本质上布隆过滤器是一种数据结构，比较巧妙的概率型数据结构（probabilistic data structure），特点是高效地插入和查询，
* 可以用来告诉你 “某样东西一定不存在或者可能存在”。相比于传统的 List、Set、Map 等数据结构，它更高效、占用空间更少，但是缺点是其返回的结果是概率性的，而不是确切的。
*
* 显然，过小的布隆过滤器很快所有的 bit 位均为 1，那么查询任何值都会返回“可能存在”，起不到过滤的目的了。布隆过滤器的长度会直接影响误报率，布隆过滤器越长其误报率越小。
* 哈希函数的个数也需要权衡，个数越多则布隆过滤器 bit 位置位 1 的速度越快，且布隆过滤器的效率越低,花费空间也会增多；但是如果太少的话，那我们的误报率会变高。
* 哈希函数个数代表一个值映射几个位
*
* 布隆过滤器不方便删除,可以重建来达到修改目的 -- 一种支持删除的方法:用多个bit位来计数,同理开销会增大,看情况使用
*
* 查找时间复杂度O(1)
*
*/
/** 布隆过滤器优点
*
* 1. 增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数，一般比较小)，与数据量大小无关
* 2. 哈希函数相互之间没有关系，方便硬件并行运算
* 3. 布隆过滤器不需要存储元素本身，在某些对保密要求比较严格的场合有很大优势
* 4. 在能够承受一定的误判时，布隆过滤器比其他数据结构有这很大的空间优势
* 5. 数据量很大时，布隆过滤器可以表示全集，其他数据结构不能
* 6. 使用同一组散列函数的布隆过滤器可以进行交、并、差运算
*
*/
/**布隆过滤器缺陷
* 1. 有误判率，即存在假阳性(False Position)，即不能准确判断元素是否在集合中(补救方法：再
* 建立一个白名单，存储可能会误判的数据)
* 2. 不能获取元素本身
*
*
* 3. 一般情况下不能从布隆过滤器中删除元素
* 4. 如果采用计数方式删除，可能会存在计数回绕问题,丧失低开销优势,还有可能有溢出问题
*
*
* .
*/
/** 布隆过滤器的使用场景 -- 非整型数据存不存在
* 1.快速响应且容许误判的场景:注册昵称是否存在
*
* 2.手机号注册:如果bloom判断不存在,则直接返回,响应很快.如果在,再去数据库中确认后再返回精确结果 --- 精确且效率高 -- 比纯布隆慢一点点
* 布隆过滤器发挥作用,可以快速过滤掉大量数据,剩下极小部分数据可以方便使用其他数据结构解决
* (很实用)
*
* $如果能容忍误判就可以直接用了
* $如果不能容忍误判则当过滤器用 -- 最后一般都在数据库中查找--信息型数据
* 数据分为信息型,数据型,内容型,文件型.....(不准确)
*
* 最佳实践
* 常见的适用常见有，利用布隆过滤器减少磁盘 IO 或者网络请求，因为一旦一个值必定不存在的话，我们可以不用进行后续昂贵的查询请求。
*
*/
//布隆过滤器变量控制
/**
* k 为哈希函数个数，m 为布隆过滤器长度，n 为插入的元素个数，p 为误报率
* $ -1 * (ln2)^2 * m = n * lnp
* $ k * n = m * ln2;
*
*/
namespace BloomFilter
{
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 (size_t 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> //可以有多个hash
class bloomfilter
{
private:
//开辟多少空间根据公式k * n = m * ln2; m 为布隆过滤器长度，n 为插入的元素个数,k为哈希个数
/**
* m = k/ln2 * N ;K=3,3/ln2 = 4.32...=4 ;
*
*/
static const size_t _X = 6; //数字是相当于每个值使用多少位 //计算出来是4,但感觉4误判率高很多,使用6开销也大很多,得具体验证才知好坏
test::bitset<N * _X> _bs; //_X越大消耗越多
public:
void set(const K& key)
{
//Hash1 hash1;具体对象写法:hash1(key)
// 匿名对象写法Hash1()(key);
size_t len = N * _X;//长度
size_t hash1 = Hash1()(key) % len;//匿名对象写法
_bs.set(hash1);
size_t hash2 = Hash2()(key) % len;
_bs.set(hash2);
size_t hash3 = Hash3()(key) % len;
_bs.set(hash3);
//cout << hash1 << " " << hash2 << " " << hash3 << " " << endl; //观察哈希值的数据
}
bool test(const K& key)
{
size_t len = N * _X;//长度
//只要有一个不是1就是不存在,所有都存在才可能存在
size_t hash1 = Hash1()(key) % len;
if (_bs.test(hash1) == false)
{
return false;
}
size_t hash2 = Hash2()(key) % len;
if (_bs.test(hash2) == false)
{
return false;
}
size_t hash3 = Hash3()(key) % len;
if (_bs.test(hash3) == false)
{
return false;
}
return true;
}
};
void test_BloomFilter1()
{
BloomFilter::bloomfilter<100> bs;
bs.set("sort");
bs.set("bloom");
bs.set("hello world hello bit");
bs.set("test");
bs.set("etst");
bs.set("estt");
cout << bs.test("sort") << endl;
cout << bs.test("bloom") << endl;
cout << bs.test("hello world hello bit") << endl;
cout << bs.test("test") << endl;
cout << bs.test("etst") << endl;
cout << bs.test("estt") << endl;
cout << bs.test("ssort") << endl;
cout << bs.test("tors") << endl;
cout << bs.test("ttes") << endl;
}
void test_BloomFilter2()
{
srand((size_t)time(0));
const size_t N = 100000; //切换release,不然很慢
BloomFilter::bloomfilter<N> bf;
//基准,用于与下面两个比较
std::vector<std::string> v1;
std::string url = "https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html";
for (size_t i = 0; i < N; ++i)
{
v1.push_back(url + std::to_string(i));
}
for (auto& str : v1)
{
bf.set(str);
}
//-----------------------------------------------------------------------------
// v2跟v1是相似字符串集，但是不一样
std::vector<std::string> v2;
for (size_t i = 0; i < N; ++i)
{
std::string url = "https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.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 = "zhihu.com";
//string url = "https://www.cctalk.com/m/statistics/live/16845432622875";
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;
}
}
标签：std,set,STL,bitset,bs,test,模拟,size From： https://www.cnblogs.com/DSCL-ing/p/18038633