欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

海量数据处理问题分析

程序员文章站 2022-06-24 19:40:17
...

哈希切割top K问题

给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址?

100G的log file 哈希切分成1000份,为什么不切成100份
因为100份中不一定每个文件大小都是1G,有的文件可能要
5,6个G的,因为有哈希冲突,可能某个文件哈希冲突多
文件大小要10G左右了,因此哈希切分成1000份,每份100M
这样最多IP大小也就12个G,哈希表可以进行处理。
切分时:先把IP字符串转为整型,再取模Ip%1000
进行哈希切分存储。因为相同的IP一定会进入同一个文件
然后1000份中用哈希表KV模型进行统计每个IP的次数
用第一个文件中IP次数和第二个最多IP次数比较,大的保留
小的销毁,依次向后比较,直到统计完1000份中最大的IP次数。
如果某一个文件IP值过多,导致文件过大,可以用不同的哈希
算法进行切分来实现分流。

海量数据处理问题分析

位图应用

给定100亿个整数,设计算法找到只出现一次的整数

要知道100亿个整数占多少空间,10亿个整数大概占一个G
100亿大概占10个G,但是一百亿个整数,所以要大概占40个G
很明显内存中是存不下的,位图只需要用位来表示一个数在或者
不在,一个字节为8个比特,现在用32个比特位表示,则40G
用位图需要40/32=1.25G,因此我们需要用位图进行操作
一个数字用两位进行表示,需要消耗2.5G,一共三种状态
没有出现'00'表示,出现一次用'01'表示,出现2次出现
用'10'表示,两次以上出现依然保持'10'状态,位图一个整形
可以标记32个数,现在标记16个数,16个数中每个数存储
两个比特位。

海量数据处理问题分析

给两个文件,分别有100亿个整数,我们只有1G内存,如何找到两个文件交集

方法1.把100亿个整数放在一个位图中,开辟一个位图需要500M
从另一个文件中开始读取遍历,在就是交集,不在就不是
方法2.将两个文件分别放到两个位图中,将两个位图进行与操作
位图中是用数组进行存储,数组中存储的都是0,1整型
将两个位图依次与,1与1为1,1与0为0,与操作后
数组中为1的就是交集,为0的表示没有交集。

1个文件有100亿个int,1G内存,设计算法找到出现次数不超过2次的所有整数

与上一个算法类似,操作两个位进行表示所有整数出现的次数
共四种状态,没有出现'00'表示,出现一次用'01'表示
出现2次出现用'10'表示,出现两次以上的用'11'表示

海量数据处理问题分析

布隆过滤器+哈希切分

给两个文件,分别有100亿个query,我们只有1G内存,如何找到两个文件交集?分别给出精确算法和近似算法

近似算法:创建一个布隆过滤器,将一个文件所以字符串放入布隆过滤器中,将另一个文件中值依次再布隆过滤器中查找,不在的肯定不在,在的可能在,但在的几率大,因为布隆有误判效果。

精确算法:使用哈希切分进行精确计算,下图有算法分析
海量数据处理问题分析

如何扩展BloomFilter使得它支持删除元素的操作

为什么布隆过滤器不支持删除,是因为可以有不同的值映射
到相同的位置,如果你删除一个值可能会影响另一个值。
因此要加一个计数,用整型四个字节来计数。

如何扩展BloomFilter使得它支持计数操作

直接用一个整型指针计数,直接进行操作,相同位置每来一个
++一次,直接访问引用计数就行。

倒排索引

给上千个文件,每个文件大小为1K—100M。给n个设计算法对每个词找到所有包含它的文件,你只有100K内存

*中描述的倒排索引:
倒排索引(英语:Inverted index),也常被称为反向索引、
置入档案或反向档案,是一种索引方法,被用来存储在全文搜索
下某个单词在一个文档或者一组文档中的存储位置的映射。
它是文档检索系统中最常用的数据结构。
由上面的定义可以知道,一个倒排索引包含一个字典的索引
和所有词的列表。其中字典索引中包含了所有的Term
(通俗理解为文档中的词),索引后面跟的列表则保存
该词的信息(出现的文档号,甚至包含在每个文档中的位置信息)
下面我举一个简单的例子来说明倒排索引。

一共有四个文件,每个文件中都有自己的内容
如现在我们要对四篇文档建立索引(实际应用中,文档的数量是海量的)
建立好索引图如下:
海量数据处理问题分析
在上面的索引中,存储了两个信息,文档号和出现的次数。建立好索引以后,我们就可以开始查询了。查询时可以通过词找相关文件