秋招总结(四)-海量数据处理问题归纳

柔光的暖阳◎ 2024-04-18 11:07 39阅读 0赞

## TOP N问题 ##

##  ##

### **1.如何在海量数据中找出重复最多一个** ###

*  通过hash映射为小文件
 *  通过hash\_map统计各个小文件重读最多的并记录次数
 *  对每个小文件重复最多的进行建立大根堆

### **2.上亿有重数据，统计最多前N个** ###

*  内存存不下
    
     *  通过hash映射为小文件
     *  通过hash\_map统计各个小文件重读最多的并记录次数
     *  对每个小文件重复最多的进行建立大根堆并重复N次取走堆顶并重建堆操作
 *  内存存得下
    
     *  直接内存通过hash\_map统计并建大根堆
     *  重复N次取走堆顶并重建堆操作

### 3.海量日志数据，提取出某日访问百度次数最多的那个IP ###

*  将IP % 1000映射到1000个小文件中
    
     *  相同IP会被映射到同一个文件
     *  不会出现累加和更大情况
 *  分1000次在内存处理小文件，得到频率最大IP（使用map统计）
 *  对这1000个IP建立大根堆

### 4.1000w查询串统计最热门10个（同2） ###

###  ###

### 5.1G的文件，里面1行1个不超过16字节的词。内存限制1M，返回频数最高前100 ###

*  将单词 % 5000存入5000小文件
    
     *  平均各文件约200K
     *  对超过1M的文件继续分割直到小于200K
 *  使用map统计各个词出现的频率
 *  对5000词使用堆排序或归并排序

### 6.分布在100台电脑的海量数据，统计前十 ###

*  各数据只出现在一台机器中
    
     *  先在独立机器得到前十
        
         *  若可以放入内存直接堆排序
         *  若不可全放入内存：哈希分块 -> map统计 -> 归总堆排
     *  再将100台计算机的TOP10组合起来堆排序
 *  同一元素可同时出现在不同机器中
    
     *  遍历所有数据，重新hash取模，使同一个元素只出现在单独的一台电脑中，然后采用上面方法先统计每台电脑TOP10再汇总起来

### 7.A,B两个文件各存放50亿url，每个为64Byte，限制内存4G找出公共url ###

*  遍历文件a，对每个url求取hash(url)%1000，然后根据所取得的值将url分别存储到1000个小文件(记为a0,a1,...,a999，每个小文件约300M)，为什么是1000？主要根据内存大小和要分治的文件大小来计算，我们就大致可以把320G大小分为1000份，每份大约300M（当然，到底能不能分布尽量均匀，得看hash函数的设计）
 *  遍历文件b，采取和a相同的方式将url分别存储到1000个小文件(记为b0,b1,...,b999)（为什么要这样做? 文件a的hash映射和文件b的hash映射函数要保持一致，这样的话相同的url就会保存在对应的小文件中)
 *  在问题转换成了：找出1000对小文件中每一对相同的url（不对应的小文件不可能有相同的url）
 *  每个hash大约300M，对每个小文件建立hash表，每次遍历查看url是否存在，重复的都写到另一个文件中

### 8.1000w有重字符串，对字符串去重 ###

*  先hash分为多个文件
 *  逐个文件检查并插入set中
 *  多个set取交集

### 9.在2.5亿数字中找出不重复的整数 ###

*  使用2-Bit位图法，00表示不存在，01表示出现一次，10表示出现多次，11无意义。这样只需要1G内存。
 *  或者hash划分小文件，小文件使用hash\_set检查各个元素，得到的。

### 10.如何在40亿数字中快速判断是否有某个数？ ###

*  位图法标记某个数字是否存在，check标记数组。