海量数据中找出出现次数最多的前10个URL(如何找出访问最多的IP,如何从大量数据中找出高频词)

简介题目描述: 给定a、b两个文件,各存放50亿个url,每个url各占64B,内存限制是4GB,请找出a、b两个文件共同的url 分析: 由于每个url需要占64B,所以50亿个url占用空间大小为50亿×64=5GB×64=320GB.由于内存大小只有4GB,因此不可能一次性把所有的url加载到内存中处理。对于这种题目,一般采用分治法,即把一个文件中的url按照某一特征分成多个文件,使得每个文件的内容都小于4GB,这样就可以把这个文件一次性读入到内存中进行处理。

题目描述:

给定a、b两个文件,各存放50亿个url,每个url各占64B,内存限制是4GB,请找出a、b两个文件共同的url

分析:

由于每个url需要占64B,所以50亿个url占用空间大小为50亿×64=5GB×64=320GB.由于内存大小只有4GB,因此不可能一次性把所有的url加载到内存中处理。对于这种题目,一般采用分治法,即把一个文件中的url按照某一特征分成多个文件,使得每个文件的内容都小于4GB,这样就可以把这个文件一次性读入到内存中进行处理。

解答:

1、遍历文件a,对遍历带的url求hash(url)%500,根据计算结果把遍历到的url分别存放到a0,a1,a2,a3...,a499(计算结果为i的url存储到文件ai中),这样每个文件的大小大约为600MB。当某一个文件中的url的大小超过2GB时,可以按照类似的方法把这个文件继续分为更小的子文件(例如a1文件的大小超过2GB,则把文件继续分为a11,a12...)

2、使用同样的方法遍历文件b,把文件b的url分别存储到文件b0,b1,b2...b499中去。

3、通过之前的划分,与ai中的url相同的url一定在bi中。由于ai与bi中所有的url的大小不会超过4GB,因此可以把它们同时读入内存中进行处理。具体为:遍历文件ai,把遍历到的url存入hash_set中,接着遍历文件bi中的url,如果这个url在hash_set中存在,那么说明这个url是这两个文件共同的url,可以把这个url保存到另一个单独的文件中。当把文件a0~a499都遍历完成后,就找到了两个文件共同的url。

 

大数据面试题——如何找出访问最多的IP

问题描述:

现有海量日志数据保存在一个超大的文件中,该文件无法直接存入内存,要求从 中提取某天访问BD次数最多的IP

分析解读:

由于这个题目只关心某一天访问次数最多的IP,因此可以首先对文件进行一次遍历,把这一天访问的IP的相关信息记录到一个单独的文件中。接下来可以用之前的方法来进行求解。唯一需要确定的是把一个大文件分成多少个小文件比较合适。以IPV4为例子,由于一个IP地址占用32位,因此最多会有2^32=4G种取值情况。如果使用hash(IP)%1024值,那么把海量IP日志分别存储到1024个小文件中。这样,每个小文件最多包含4M个IP地址。如果使用2048个小文件,那么每个小文件会最多包含2M个IP地址。因此,对于这种题目来说,首先需要确定可用的内存的大小,然后确定数据的大小。由这两个参数就可以确定Hash函数应该怎么设置才能保证每个文件的大小都不超过内存的大小,从而可以保证每个小文件都能被一次性加载到内存中。
 

2.思考过程 :https://blog.csdn.net/tiankong_/article/details/77239501
(1)面试中若题目提到大文件等,其实就是告诉你数据量大,不能一次性加载到内存中,而实际中我们就需要估算。既然是要对访问百度次数的ip做统计,我们最好先预处理一下,遍历把访问百度的所有ip写到另一个文件a中

(2)ip用32位表示,所以最多有2^32个不同ip地址。同样的,当内存不能一次性加载数据时,我们就需要考虑分治法。

step1:采用hash映射(hash(ip)%1000)分别把结果保存到小文件a0....a999中。有人可能会问,这里一定要用1000吗?当然不一定,需要估算,比如若文件a总共320G远远大于4G内存,我们就需要分块(hash映射),若分为1000块,则每块大约300M,再读入内存就没问题了。

step2:可以采用hash_map进行频率统计,找出每个小文件中出现频率最大的IP。对于每一个小文件ai,具体操作如下:创建hash_map,遍历小文件中每条记录。对于每条记录,先在hash_map中搜索,若有,将hash_map中记录count+1,若没有,插入hash_map

step3:在这1000个最大的IP中,找出count最大的ip

本文转自:https://blog.csdn.net/qq_35858961/article/details/98848745