西安网站建设xs029,免费代理ip最新,网站建设书 模板下载,网络艺术设计是什么一、位图
1.1 位图的概念
面试题 给40亿个不重复的无符号整数#xff0c;没排过序 给一个无符号整数#xff0c;如何快速判断一个数是否在 这40亿个数中。【腾讯】 能想到的解决思路#xff1a;
遍历#xff0c;时间复杂度O(N)排序(O(NlogN)) 利用二分查找: logN放到哈…
一、位图
1.1 位图的概念
面试题 给40亿个不重复的无符号整数没排过序 给一个无符号整数如何快速判断一个数是否在 这40亿个数中。【腾讯】 能想到的解决思路
遍历时间复杂度O(N)排序(O(NlogN)) 利用二分查找: logN放到哈希表或红黑树
40亿整数就是16GB无法全部加载到内存 遍历、排序和二分查找就都不太现实 虽然可以在文件中归并但就慢了很多 文件中不能用下标自然无法二分查找
虽然可以将数据一段一段放进哈希表和红黑树 但每次将数据插入进红黑树又释放 相当于暴力查找40亿数据 红黑树的特性完全没用上 所以以上3点都是不合适的 最大的原因就是内存不足 位图解决 数据是否在给定的整形数据中 结果是在或者不在刚好是两种状态 那么可以用比特位表示数据是否存在 1为存在0为不存在
比如数据{1,2,4,9,1517,23}在位图的样子 所谓位图就是用每一位来存放某种状态 适用于海量数据数据无重复的场景 通常是用来判断某个数据存不存在的 一个比特位就能表示一个整型数据在或不在 一个整型就是32比特位相当于缩小了32倍 也就是说16G的数据只需要0.5G 1.2 位图的模拟实现 位图的三个主要接口
set将数据映射位置置成1表示存在 reset将数据映射位置置成0表示删除test检测数据是否存在于位图
template size_t N
class bitset
{
public:bitset(){_bits.resize(N / 8 1, 0); // 需求N个比特位,按字节给,所以除8.除会去余,所以加1}void set(size_t x) // 将x比特位置1{size_t i x / 8; // 计算x映射的位在第i个char数组位置size_t j x % 8; // 计算x映射的位在这个char的第j个比特位_bits[i] | (1 j);}void reset(size_t x) // 将x比特位置0{size_t i x / 8;size_t j x % 8;_bits[i] ~(1 j);}bool test(size_t x) // 检测位图中x是否为1{size_t i x / 8; size_t j x % 8; return _bits[i] (1 j);}
private:vectorchar _bits;
};1.3 位图的应用 1、给定100亿个整数设计算法找到只出现一次的整数 方法
创建两个位图对象bs1、bs2遍历数据 出现0次用00表示 出现1次用01表示 出现2次用10表示 出现3次及以上用11表示
如果数据映射的位置在bs1里为1 在bs2里为0表示此数据出现过2次 如果在bs1和bs2里都为1表示出现3次及以上 方法实现
template size_t N
class twobitset
{
public:void set(size_t x) {// 00 - 01if (_bs1.test(x) false _bs2.test(x) false){_bs2.set(x);}else if (_bs1.test(x) false _bs2.test(x) true){// 01 - 10_bs1.set(x);_bs2.reset(x);}// 10 不变}void print(){for (size_t i 0; i N; i) {if (_bs2.test(i))cout i ;}}
private:bitsetN _bs1;bitsetN _bs2;
};void test_twobitset3()
{twobitset1000 bs;int a[] { 0, 12, 12, 0, 20, 12, 12, 0, 223, 22, 45, 4 };for (auto e : a){bs.set(e);}bs.print();
}2、给两个文件分别有100亿个整数 我们只有1G内存如何找到两个文件交集 方法1 其中的一个文件读到内存的位图中 再读另一个文件判断在不在上面的位图 在就是交集
问题 找出的交集存在重复值
解决方法1 一个数为交集就在第一个文件set那个数
解决方法2 读取文件1映射到位图1 读取文件2映射到位图2 判断数据映射的位置在这两个位图中 是否都为1
for (int i 0; i N; i)
{if (bs1.test(i) bs2.test(i)){// 交集}
}或者按位与这两个位图 3、位图应用变形1个文件有100亿个int 1G内存设计算法找到出现次数不超过2次的所有整数 定义两个位图对象 将数据插入到位图 出现0次用00表示 出现1次用01表示 出现2次用10表示 出现3次及以上用11表示
除了两个位图对应位置都为1 其他都打印
二、布隆过滤器
位图的优点
速度快、节省空间
缺点
只能映射整形其他如浮点数、string等 不能存储映射
布隆过滤器便是解决此缺点
2.1 布隆过滤器提出
我们在使用新闻客户端看新闻时 它会给我们不停地推荐新的内容 它每次推荐时要去重 去掉那些已经看过的内容问题来了 新闻客户端推荐系统如何实现推送去重的 用服务器记录了用户看过的所有历史记录 当推荐系统推荐新闻时会从每个用户 的历史记录里进行筛选 过滤掉那些已经存在的记录 如何快速查找呢
用哈希表存储用户记录 缺点浪费空间用位图存储用户记录 缺点位图一般只能处理整形 如果内容编号是字符串 就无法处理了将哈希与位图结合即布隆过滤器
2.2 布隆过滤器概念
布隆过滤器是由布隆(Burton Howard Bloom) 在1970年提出的 一种紧凑型的、比较巧妙的概 率型数据结构特点高效地插入和查询 可以用来告诉你 “某样东西一定不存在或者可能存在” 它是用多个哈希函数 将一个数据映射到位图结构中 此种方式不仅可以提升查询效率 也可以节省大量的内存空间 用多个哈希函数将字符映射到不同的位置 以此降低重复率查找时在所有映射的位置 查看是否均为1
查找一个值在与不在 在是不准确的存在误判 不在是准确的 比如美团本来不在 查找时每个映射的位置都跟别人冲突 导致认为它在
2.3 布隆过滤器的使用场景
能容忍误判场景 比如改名时快速判断昵称是否使用过 昵称在数据库而数据库在磁盘 如果去磁盘查找修改的昵称是否使用过 效率非常慢我们平时改昵称时 只要输入就能立即反馈昵称是否使用 这时可以把所有用户昵称放入布隆过滤器 即使误判修改昵称已使用用户也感知不到 (只要误判率不高还是可以接受的)
2.4 布隆过滤器的实现
如何选择哈希函数个数和布隆过滤器长度 k 为哈希函数个数 m 为布隆过滤器长度 n 为插入的元素个数 p 为误报率 代码实现
struct BKDRHash
{size_t operator()(const string s){size_t hash 0;for (auto ch : s){hash hash * 30 ch;}return hash;}};struct APHash
{size_t operator()(const string s) // 仿函数的作用把一个类当作对象去访问或把一个对象像函数去使用{size_t hash 0; // 加register放到最前面表示建议变量放到寄存器里面for (long i 0; i s.size(); i){size_t ch s[i];if ((i 1) 0) // i 是偶数走ifi 是奇数else.奇数二进制的低位一定是1按位与1得到的便是奇数hash ^ ((hash 7) ^ ch ^ (hash 3));elsehash ^ (~((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;}
};// N是key,插入值的个数
templatesize_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 * _X;size_t hash1 Hash1()(key) % len; // 用Hash仿函数转成可以取模的整型值模N是怕转出来的值超出N_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) // 判断3个位置有一个位置为0就是不在{size_t len N * _X;size_t hash1 Hash1()(key) % len; if (!_bs.test(hash1))return false;size_t hash2 Hash2()(key) % len;if (!_bs.test(hash2))return false;size_t hash3 Hash3()(key) % len;if (!_bs.test(hash3))return false;return true;}
private:static const size_t _X 6; // 比重为6冲突率5%以内.比重建议5-10(冲突率1%-10%)bitset_X * N _bs; // 开_X倍的空间,空间开得越大,冲突率越低
};2.5 布隆过滤器的应用 1、给两个文件分别有100亿个query我们只有1G内存如何找到两个文件交集分别给出精确算法和近似算法 100亿query假设每个query平均50byte 100亿就是5000亿byte也就是大约占用500G
可以把每个文件分成1000份读进内存 每份是0.5个G B文件的每一份在A文件的每一份里去找 但是这样时间复杂度太高了 于是可以用哈希函数来切分文件 哈希切分i HashFunc(query) % 1000 每个query算出i是多少就进入Ai小文件 B也是一样算出i放进Bi小文件 B0、B1……在对应的A0、A1…… 小文件里去找找到了就是交集
跟之前的哈希桶很像 进入同一个桶的都是冲突的值 在这里A和B相同的值用的同一个哈希函数 便一定会进入同一个编号的文件 会导致的问题 因为不是平均切分可能会出现冲突多 每个Ai、Bi小文件过大
单个文件大量重复query单个文件大量不同query
解决方法 直接使用unordered_set/set 依次读取文件query插入set中
如果读取整个小文件query 都可以成功插入set说明是情况1如果读取整个小文件query 插入过程抛异常则是情况2 换其他哈希函数再次分割求交集
说明set插入key如果已经有了返回false 如果内存不足抛bad_alloc异常 剩下的都会成功 2、如何扩展BloomFilter使得它支持删除元素的操作 删除一个元素可能会影响其它元素 用多个位图计数的方式表示每个位置被映射了几次 删除时减减该位置 3、哈希切割 给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址 与上题条件相同如何找到top K的IP 解决方法 哈希切分成500个小文件 依次读取数据i HashFunc(ip)%500 这个ip就是第i个小文件
依次处理每个小文件 使用unordered_map/map统计ip出现次数
统计过程抛异常说明单个文件过大 冲突太多需要重新换哈希函数 再次哈希切分这个小文件如果没有抛异常则正常统计 统计完一个小文件记录最大的 clear map再统计下一个小文件
总结特点 相同的ip一定进入相同的小文件 读取单个小文件就可以统计ip出现次数 本篇博客完感谢阅读 如有错误之处可评论指出 博主会耐心听取每条意见
