国内做网上旅游业务的网站,营销型网站建设需要备案吗,给金融的做网站 犯法吗,西安seo排名收费位图
概念
题目
给40亿个不重复的无符号整数#xff0c;没排过序。给一个无符号整数#xff0c;如何判断一个数是否在这40亿个整数中
1.遍历#xff0c;时间复杂度O(N) 2.二分查找#xff0c;需要先排序#xff0c;排序(N*logN)#xff0c;二分查找#xff0c;logN。…位图
概念
题目
给40亿个不重复的无符号整数没排过序。给一个无符号整数如何判断一个数是否在这40亿个整数中
1.遍历时间复杂度O(N) 2.二分查找需要先排序排序(N*logN)二分查找logN。1个g大约存储10g字节40亿个整数就需要160g字节需要16个g的连续空间内存中无法开出这么大的容量。 3.位图。判断一个数在不在的最小单位可以是位将整数的范围全部做一个映射有的值设置为1没有就设置为0。这样需要的空间就是42亿个位0.5个g就可以存下 上面是3个字节的值一个字节32位可以表示的数的范围。计算一个值在第几个字节在这个字节的第几个位。将一个数除以32就知道在第几个字节取模就知道在第几个位比如40在第1个字节里在第8位
位图概念
用每一位存放某种状态适用于海量数据数据无重复的场景判断某个数据村部还存在的
实现
成员函数
可以用内置数组这里直接用vector成员类型是int
构造
为vector开辟需要的空间每一位代表一个值看需要多大的值用非类型模板参数传入值。传入的是位除以32再补上去的余数的一位就是开辟多大整形的空间
set
将这个数据映射的值设为1。计算出数据所在的位设置为1。i和j分别计算在第几个字节和第几位让一个数的一位变为1其他位不变化可以或一个数这个数这一位为1其他位为0。可以将1左移j位就有了这个数
内存有大端和小端存储左移都是往高位移动
reset
将这个数据清除变为0。计算出i和j让某一位变为0可以与一个数这个数这一位为0其他都为1。1左移j位然后取反
test
查询一个数是否存在。1左移j位与操作 全
#pragma once
#include vector//N是需要多少位
template size_t N
class bitset
{
public:bitset(){//多开一个防止不够_bit.resize(N / 32 1, 0);//_bit.resize( (N 5) 1, 0)}void set(size_t x){int i x / 32;int j x % 32;_bit[i] _bit[i] | (1 j);}void reset(size_t x){int i x / 32;int j x % 32;_bit[i] _bit[i] ~(1 j);}bool test(size_t x){int i x / 32;int j x % 32;return _bit[i] (1 j);}
public:std::vectorint _bit;
};测试
40亿的整数需要开辟的空间必须是无符号的整形大小int是有符号的所以用0xffffffff或-1
bitset0xffffffff bs;
bs.set(39256);
bs.set(43450);
bs.reset(40);cout bs.test(24515) endl;
cout bs.test(32329) endl;
cout bs.test(39256) endl;
cout bs.test(2314) endl;
cout bs.test(43450) endl;应用
1.快速查找某个数据是否在一个集合中 2.排序去重 3.求两个集合的交集、并集等 4.操作系统重磁盘块标记
题目
1.给定100亿个整数设计算法找到只出现一次的整数 位图用一个位标识两种状态存在和不在找到出现一次的数需要第三种状态可以用两个位来保存一个数。也可以复用前面的位图用一个结构成员两个位图。set时当两个位图表示的是00的时候就设置为01,01就设置为10,10就不做任何改变。打印的时候打印出01状态的数字
template size_t N
class twobitset
{
public:void set(size_t x){//00 0次//01 1次//10 2次或以上int i x / 32;int j x % 32;if (_bs1.test(x) false _bs2.test(x) false){_bs2.set(x);}else if (_bs1.test(x) false _bs2.test(x) true){_bs1.set(x);_bs2.reset(x);}}void printOne(){for (size_t i 0; i N; i){if (_bs1.test(i) false _bs2.test(i) true){printf(%d , i);}}printf(\r\n);}public:bitsetN _bs1;bitsetN _bs2;
};2.给两个文件分别有100亿个整数我们只有1G内存如何找到两个文件交集
和上面的方法一样无论多少整数还是申请42亿两个位图里都有的就是交集
3.位图变形一个文件有100亿个int1G内存设计算法找到出现次数不超过2次的所有整数
还是上面的类型稍微修改set函数10的时候变为11,11不变
template size_t N
class twobitset
{
public:void set(size_t x){//00 0次//01 1次//10 2次或以上int i x / 32;int j x % 32;if (_bs1.test(x) false _bs2.test(x) false){_bs2.set(x);}else if (_bs1.test(x) false _bs2.test(x) true){_bs1.set(x);_bs2.reset(x);}else if (_bs1.test(x) true _bs2.test(x) false){_bs1.set(x);_bs2.set(x);}}void printOne(){for (size_t i 0; i N; i){if (_bs1.test(i) false _bs2.test(i) true){printf(一次%d , i);}else if (_bs1.test(i) true _bs2.test(i) false){printf(两次%d , i);}}printf(\r\n);}public:bitsetN _bs1;bitsetN _bs2;
};布隆过滤器
提出
每次看新闻时会不断推荐新的内容去掉已经看过的内容。问题来了如何实现推送去重的用服务器记录所有看过的记录当推荐系统推荐新闻时从每个用户的历史记录里筛选过滤掉已经存在的记录怎么快速查找
目前搜索采用的各种方法 1.暴力查找数据量太大了效率就低 2.排序二分查找问题a:排序有代价 问题b:数组不方便增删 3.搜索树avl树红黑树 上面的数据结构对空间消耗的都很高如果面对数据量很大的 5.[整形]在不在及其扩展问题位图和变形节省空间 6.[其他类型] 在不在哈希和位图结合布隆过滤器
概念
布隆过滤器是由布隆Burton Howard Bloom在1970年提出的一种紧凑型的、比较巧妙的概率性数据结构特点是高效的插入和查询可以判断一个东西一定不在或可能在是用多个哈希函数将一个数据映射到位图结构中此种方式不仅可以提升查询效率也可以节省大量的内存空间 一个值映射一个比特位冲突的概率很大两个不同的字符串正好映射在一个比特位这时判断的存在就是错误的。为了降低误判的概率多映射几个比特位映射的越多消耗的空间就越多
插入
上图中当k3个时100m数据误判率0.01已经很低了 按公式计算 3个哈希函数n和m的关系是4.3约为4倍容量
查找
将一个元素用多个哈希函数映射到一个位图中因此被映射到的位置比特位一定为1.所以可以按照以下方式进行查找分别计算每个哈希值对应的比特位置存储的是否为零只要有一个零代表该元素一定不在哈希表中否则可能在哈希表中
注意布隆过滤器如果说某个元素不存在时一定不存在如果该元素存在时可能存在因为存在一定的误判
删除
不能直接支持删除操作因为在删除一个元素时可能影响到其他元素 比如删除上图的tecent”元素如果直接将该元素对应的二进制比特位置置为0“baidu”元素也被删除了因为这两个元素在多个哈希函数计算的比特位有重叠
一种支持删除的方法将布隆罗氯气每个比特位扩展成一个小的计数器插入元素时给k个计数器k个哈希函数计算出的哈希地址加一删除元素时给k个计数器减一通过多占用几倍存储空间的代价来增加删除操作。如果引用计数最大为255时映射的单位就必须扩展为8位
缺陷 1.无法确认元素是否真正在布隆过滤器中 2.存在计数回绕
实现
#pragma once
#include bitsetstruct BKDRHash
{size_t operator()(const std::string key){// BKDRsize_t hash 0;for (auto e : key){hash * 31;hash e;}return hash;}
};struct APHash
{size_t operator()(const std::string key){size_t hash 0;for (size_t i 0; i key.size(); i){char ch key[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 std::string key){size_t hash 5381;for (auto ch : key){hash (hash 5) ch;}return hash;}
};template size_t N, class K std::string,class HashFunc1 BKDRHash,class HashFunc2 APHash,class HashFunc3 DJBHash
class BloomFilter
{
public:void set(const std::string key){size_t hashi1 HashFunc1()(key) % N;size_t hashi2 HashFunc2()(key) % N;size_t hashi3 HashFunc3()(key) % N;_bs.set(hashi1);_bs.set(hashi2);_bs.set(hashi3);}// 一般不支持删除删除一个值可能会影响其他值// 非要支持删除也是可以的用多个位标记一个值存引用计数// 但是这样话空间消耗的就变大了void Reset(const K key);bool test(const std::string key){size_t hashi1 HashFunc1()(key) % N;if (_bs.test(hashi1) false)return false;size_t hashi2 HashFunc2()(key) % N;if (_bs.test(hashi2) false)return false;size_t hashi3 HashFunc3()(key) % N;if (_bs.test(hashi3) false)return false;return true;}private:std::bitsetN _bs;
};测试
#include time.h
#include vector
#include iostream
#include string
#include bloom.hint main()
{srand(time(0));const size_t N 100000;BloomFilterN * 4 bf;std::vectorstd::string v1;//std::string url https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html;std::string url 猪八戒;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::vectorstd::string v2;for (size_t i 0; i N; i){std::string urlstr url;urlstr std::to_string(9999999 i);v2.push_back(urlstr);}size_t n2 0;for (auto str : v2){if (bf.test(str)) // 误判{n2;}}std::cout 相似字符串误判率: (double)n2 / (double)N std::endl;// 不相似字符串集std::vectorstd::string v3;for (size_t i 0; i N; i){//string url zhihu.com;std::string url 孙悟空;url std::to_string(i rand());v3.push_back(url);}size_t n3 0;for (auto str : v3){if (bf.test(str)){n3;}}std::cout 不相似字符串误判率: (double)n3 / (double)N std::endl;return 0;
}优点
1.增加和查询元素的时间复杂度为O(K),k为哈希函数个数一般比较小与数据数量无关 2.哈希函数相互之间没有关系方便硬件并行计算 3.布隆过滤器不需要存储元素本身在某些对保密要求比较严格的场合有很大优势 4.能够承受一定的误判时布隆过滤器比其他数据结构有很大的空间优势 5.数据量很大时布隆过滤器可以表示全集其他数据结构不能 6.使用同一组散列函数的布隆过滤器可以进行交、并、差运算
例如网页注册时判断用户名存不存在。如果需要更进一步正确可以将判断为存在的和数据库对比
缺陷
1.有误判率即存在假阳性False Position即不能准确判断元素是否在集合中补救方法再建立一个白名单存在可能会误判的数据 2.不能获取元素本身 3.一般情况下不能从布隆过滤器中删除元素 4.如果采用计数方式删除可能会存在计数回绕问题
哈希切割
1. 给定两个文件分别有100亿个query字符串只有1G内存找到文件交集精确算法和近似算法
近似算法就是上面的布隆过滤器 精确算法 假设一个query有50个字节100亿数据就需要500G内存存不下可以用哈希切分 读取每个query计算iHash(query)%500i是几query就进入Ai小文件
A和B相同的字符串会进入相同编号的块里只需要比较两个相同编号的块就能找到交集 如果切分的某个文件大于10G还是无法加载到内存里 1.这个小文件大多数都是1个query 2.这个小文件有很多不同的query
不管文件大小直接读到内存插入set如果是情况1文件有很多重复会去重 如果是情况2插入后就会内存不足抛异常换一个哈希函数二次划分再找交集
2. 给一个超过100G大小的logfile存ip地址设计找出次数最多的ip地址
还是用哈希切分相同的ip就进入了同一个小文件然后用map统计次数。如果找topk也可以用堆来解决
