南宁网站建设公司电话,网站建设 知识产权,seo优化推广专员招聘,品牌推广的目的和意义哈希切割
给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址#xff1f; 与上题条件相同#xff0c;如何找到top K的IP#xff1f;如何直接用Linux系统命令实现
解决思路
找到出现次数最多的IP地址
要找到前TopK的IP地址#xff0c;就…哈希切割
给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址 与上题条件相同如何找到top K的IP如何直接用Linux系统命令实现
解决思路
找到出现次数最多的IP地址
要找到前TopK的IP地址就是要统计每个IP地址出现多少次 分割大文件:如果能将相同IP地址放到同一个文件中 哈希分割: 从源文件中获取一个IP地址----IP%文件份数
每拿到一个IP地址后用函数把IP地址转化为整型数据再%上文件分数就知道把IP地址放到哪个文件中去这样就可以统计每个IP地址出现多少次
//构建键值对
IP地址的整型数据次数统计哪个IP地址出现的次数比较多用unordered_map,m[ip];每拿到一个IP地址的。每个IP地址出现的次数已经在unordered_map中保存起来按类似的方法统计每个文件中的IP地址的次数最后用一个for()----找出出现最多的IP地址
top K的IP
堆----最多前K个IP地址—次数IP地址
位图
给40亿个不重复的无符号整数没排过序。给一个无符号整数如何快速判断一个数是否在这40亿个数中。
遍历时间复杂度O(N)排序(O(NlogN))利用二分查找: logN
位图解决
数据是否在给定的整形数据中结果是在或者不在刚好是两种状态那么可以使用一个二进制比 特位来代表数据是否存在的信息如果二进制比特位为1代表存在为0代表不存在。比如 40亿的整型数据大概是16G的数据 用位图来映射的话 大概就是232-23512M
解决
C中提供了位图的类bitset
位图的实现
#pragma once
#includevector
#includeiostream
using namespace std;
namespace LXY
{class bitset{public:bitset(size_t bitCount):_set(bitCount/8 1), _bitCount(bitCount){}//置1操作void set(size_t which){//如果位集合给出100个比特位那么你给100就表示不了范围为0~99if(which _bitCount)return;//计算对应的字节size_t index (which 3);//除以8size_t pos which % 8;//先将1移到对应的比特位上再或上对应位上的数字_set[index] | (1 pos);}//置0操作void reset(size_t which){if (which _bitCount)return;//计算对应的字节size_t index (which 3);//除以8size_t pos which % 8;//先将1的取反0移到对应的比特位上再与上对应位上的数字_set[index] ~(1 pos);}//检测which比特位是否为1bool test(size_t which){if (which _bitCount)return false;//计算对应的字节size_t index (which 3);//除以8size_t pos which % 8;//与上1不等于0就代表存在return 0 ! (_set[index] (1 pos));}//返回比特位总的个数size_t size(){return _bitCount;}//返回为1的比特位的总数size_t count(){//查表int bitCnttable[256] {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2,3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3,3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3,4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4,3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5,6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4,4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5,6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5,3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3,4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6,6, 7, 6, 7, 7, 8 };size_t szcount 0;for (size_t i 0; i _set.size(); i)szcount bitCnttable[_set[i]];return szcount;}public:std::vectorunsigned char _set;size_t _bitCount;};
}void TestBitSet()
{LXY::bitset bt(100);bt.set(10);bt.set(20);bt.set(30);bt.set(40);bt.set(41);cout bt.size() endl;cout bt.count() endl;if (bt.test(40))cout 40bite is 1 endl;elsecout 40bite is not 1 endl;bt.reset(40);cout bt.count() endl;if (bt.test(40))cout 40bite is 1 endl;elsecout 40bite is not 1 endl;
}int main()
{TestBitSet();system(pause);return 0;
}位图的应用
快速查找某个数据是否在一个集合中排序 (数据不能有重复)求两个集合的交集、并集等操作系统中磁盘块标记
位图的题
给定100亿个整数设计算法找到只出现一次的整数 用两个比特位表示一个数据8/24那么位图中一个字节只能表示4个数据232/221G。 取一个数据:哪个字节 哪两个比特位 if(00) //出现过0次01else if(01) //出现过多次10位图应用变形1个文件有100亿个int1G内存设计算法找到出现次数不超过2次的所有整数
布隆过滤器
位图哈希函数 特点是高效地插入和查询可以用来告诉你 “某样东西一定不存在或者可能存在”它是用多个哈希函数将一个数据映射到位图结构中。此种方式不仅可以提升查询效率也可以节省大量的内存空间。多个比特位代表数据的状态信息
布隆过滤器插入
如果向布隆过滤器中插入baidu我们用三个哈希函数将三个位置置为1 “baidu”----1 4 7 “tecent”----3 4 8 hash1,hash2,hash3-----三个位置 检测三个位置的状态 如果三个位置只要有一个为0说明数据一定不存在
布隆过滤器的查找
布隆过滤器的思想是将一个元素用多个哈希函数映射到一个位图中因此被映射到的位置的比特位一定为1。所以可以按照以下方式进行查找分别计算每个哈希值对应的比特位置存储的是否为零只要有一个为零代表该元素一定不在哈希表中否则可能在哈希表中 布隆过滤器如果告诉你数据不存在那么一定不存在如果告诉你存在则有可能存在。
布隆过滤器的插入和查找的实现
#pragma once
#includebiteset.hpp
#includeiostream
#includeCommon.hpp
using namespace std;//BloomFilter:位图多个哈希
templateclass T,class HF1 Str2INT ,class HF2 Str2INT2,class HF3 Str2INT3,class HF4 Str2INT4,class HF5 Str2INT5
//哈希函数给的越多将来产生误报的概率就也就越小
class BloomFilter
{
public:BloomFilter(size_t size 10):_bt(10 * size), _size(0){}bool Insert(const T data){//HF1()(data)可能回越界要%上位图的比特位数size_t index1 HF1()(data) % _bt.size();size_t index2 HF2()(data) % _bt.size();size_t index3 HF3()(data) % _bt.size();size_t index4 HF4()(data) % _bt.size();size_t index5 HF5()(data) % _bt.size();_bt.set(index1);_bt.set(index2);_bt.set(index3);_bt.set(index4);_bt.set(index5);_size;return true;}//检测是否存在每个哈希函数都得检测bool IsIn(const Tdata){size_t index HF1()(data) % _bt.size();if (!_bt.test(index))return false;index HF2()(data) % _bt.size();if (!_bt.test(index))return false;index HF3()(data) % _bt.size();if (!_bt.test(index))return false;index HF4()(data) % _bt.size();if (!_bt.test(index))return false;index HF5()(data) % _bt.size();if (!_bt.test(index))return false;//元素可能存在return true;}//存储多少个元素size_t count()const{return _size;}
private:LXY::bitset _bt;size_t _size;
};布隆过滤器的删除
布隆过滤器不能直接支持删除工作因为在删除一个元素时可能会影响其他元素 一种支持删除的方法将布隆过滤器中的每个比特位扩展成一个小的计数器整型数组插入元素时给k个计数器(k个哈希函数计算出的哈希地址)加一删除元素时给k个计数器减一通过多占用几倍存储空间的代价来增加删除操作。
缺陷
无法确认元素是否真正在布隆过滤器中存在计数回绕
布隆过滤器优点
增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数一般比较小)与数据量大小无关哈希函数相互之间没有关系方便硬件并行运算布隆过滤器不需要存储元素本身在某些对保密要求比较严格的场合有很大优势在能够承受一定的误判时布隆过滤器比其他数据结构有这很大的空间优势数据量很大时布隆过滤器可以表示全集其他数据结构不能使用同一组散列函数的布隆过滤器可以进行交、并、差运算
布隆过滤器缺陷
有误判率即存在假阳性(False Position)即不能准确判断元素是否在集合中(补救方法再建立一个白名单存储可能会误判的数据)不能获取元素本身一般情况下不能从布隆过滤器中删除元素如果采用计数方式删除可能会存在计数回绕问题
布隆过滤器
给两个文件分别有100亿个query我们只有1G内存如何找到两个文件交集分别给出精确算法和近似算法 答给一个布隆过滤器将一个文件的数据映射里面去。如果整体映射不完先映射一部分。从另外一个文件拿一个数据在布隆过滤器里面找如果有数据存在就算是两个文件的交集。
倒排索引
给上千个文件每个文件大小为1K—100M。给n个词设计算法对每个词找到所有包含它的文件你只有100K内存
哈希加密
